speed up your engine part 4

[lauriet]

Ok, this is obvious in hind site, but for us first timers.........

You can generate all your moves and then sort them hoping that you get a beta cut early and dont have to search all the move list..........but generating moves is expensive time wise.
Hopefully you have have a few moves available that you can search before you generate all the others. E.G. Transposition table, killer moves......so you can try searching these looking for an immediate beta cut (and exit) just like you do with null move. You then search these moves late in your move list if they didnt cause a cut off.

So the princliple is Dont generate moves if you dont have to. This will save considerable time since the move gen proceedure can be quite time consuming in a non bitboard engine.

Obvious isnt it........well it is once you realise it.

[brtzsnr]

Reusing the hash-move is one of the reasons one should not spend too much time making the move-generation extremely fast at the expense of code complexity.

The other thing, you should have a way to generate only captures / promotions. because in QS hash-move doesn't help that much and you don't want to generate 40 quiet moves only to ignore them later.

I once experimented with generating a good hash-move (e.g. pawn captures a minor/major) if there isn't already one, but the overall speedup was not enough to show an Elo increase.

[flok]

The other thing, you should have a way to generate only captures / promotions. because in QS hash-move doesn't help that much and you don't want to generate 40 quiet moves only to ignore them later.

But what about the evaluation? Evaluation requires a full list of moves?
E.g. for standing pat.

[brtzsnr]

But what about the evaluation? Evaluation requires a full list of moves? E.g. for standing pat.

Stand-pat happens in QS and can be read as: if current evaluation is larger than beta, then return. The idea is that current player doesn't need to improve anymore the position via captures so it's a quiet position.

https://chessprogramming.wikispaces.com ... ding%20Pat

Code: Select all

    int stand_pat = Evaluate();
    if (stand_pat >= beta) return beta;

Evaluation doesn't need the moves, but the mobility. If you are using bitboards calculating the mobility is a requirement for move generation. Mobility is the set of squares that can be reached be a given piece.

[Sven]

The other thing, you should have a way to generate only captures / promotions. because in QS hash-move doesn't help that much and you don't want to generate 40 quiet moves only to ignore them later.

But what about the evaluation? Evaluation requires a full list of moves?
E.g. for standing pat.

The meaning of "stand pat" in the context of QS is different from "stalemate", in QS it means that we assume that the moving side can decide "not to move" if none of the captures improves the score.

You will never need to generate moves as a precondition for evaluation. Also calculating mobility is a different issue, it is not the same as generating moves since there are pieces for which mobility is irrelevant (king, pawns), and also since usually you will assign different weights to the mobility of different pieces so that you can't simply reuse the information from the move list.

At a playing strength level that is considerably below "world class engine" I would always vote for keeping the code as simple (and safe, and free of "unusual" things) as possible. This includes to do the obvious things and not to care too much about performance optimization issues. E.g. even for a non-bitboard engine where calculation of sliding attacks is not as cheap as with bitboards, thinking about reusing parts of the information obtained for generating sliding piece moves only for a possible minimal speedup of mobility evaluation would be a "no-go" for me due to the inherent increase of complexity and the additional code dependencies it would create.

[Sven]

But what about the evaluation? Evaluation requires a full list of moves? E.g. for standing pat.

Stand-pat happens in QS and can be read as: if current evaluation is larger than beta, then return. The idea is that current player doesn't need to improve anymore the position via captures so it's a quiet position.

For me stand-pat is not necessarily related to the beta cutoff based on the stand-pat score, I'd say the moving side also "stands pat" if none of the captures improves the score so it falls back to "not moving".

[Sven]

Ok, this is obvious in hind site, but for us first timers.........

You can generate all your moves and then sort them hoping that you get a beta cut early and dont have to search all the move list..........but generating moves is expensive time wise.
Hopefully you have have a few moves available that you can search before you generate all the others. E.G. Transposition table, killer moves......so you can try searching these looking for an immediate beta cut (and exit) just like you do with null move. You then search these moves late in your move list if they didnt cause a cut off.

So the princliple is Dont generate moves if you dont have to. This will save considerable time since the move gen proceedure can be quite time consuming in a non bitboard engine.

Obvious isnt it........well it is once you realise it.

What you describe is staged move generation which is already well-known for many years. Fruit 2.1 had it already in 2005, Stockfish of course, and I think it was even known much earlier. It is certainly a performance improvement but one should not expect too much from it since move generation is *not* one of the parts of a chess engine that consumes most of the time, as opposed to static evaluation. So saving half of the time that is consumed by a component that uses 10% of search time on average will be a 5% speedup and therefore improve strength by around 5 ELO points IF it has been done correctly and IF the additional complexity does not hurt you elsewhere.

It definitely requires a very stable state of an engine to even start thinking about such an optimization. Certainly many people have successfully done it, though ...

[bob]

Ok, this is obvious in hind site, but for us first timers.........

You can generate all your moves and then sort them hoping that you get a beta cut early and dont have to search all the move list..........but generating moves is expensive time wise.
Hopefully you have have a few moves available that you can search before you generate all the others. E.G. Transposition table, killer moves......so you can try searching these looking for an immediate beta cut (and exit) just like you do with null move. You then search these moves late in your move list if they didnt cause a cut off.

So the princliple is Dont generate moves if you dont have to. This will save considerable time since the move gen proceedure can be quite time consuming in a non bitboard engine.

Obvious isnt it........well it is once you realise it.

What you describe is staged move generation which is already well-known for many years. Fruit 2.1 had it already in 2005, Stockfish of course, and I think it was even known much earlier. It is certainly a performance improvement but one should not expect too much from it since move generation is *not* one of the parts of a chess engine that consumes most of the time, as opposed to static evaluation. So saving half of the time that is consumed by a component that uses 10% of search time on average will be a 5% speedup and therefore improve strength by around 5 ELO points IF it has been done correctly and IF the additional complexity does not hurt you elsewhere.

It definitely requires a very stable state of an engine to even start thinking about such an optimization. Certainly many people have successfully done it, though ...

It was known MUCH earlier. As in chess 4.0 (circa 1974 or so) where this all started. They took it much further back then, namely they generated one move at a time and searched it, which Belle later also did.


Bob

[lauriet]

How can you do move ordering if you generate one move at a time ?
(Except for what we have mentioned....null, tt, killer)

[lauriet]

How can you do move ordering if you generate one move at a time ?
(Except for what we have mentioned....null, tt, killer)