speed up your engine part 4

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

speed up your engine part 4

Post by lauriet » Wed Aug 03, 2016 12:32 am

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
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: speed up your engine part 4

Post by brtzsnr » Wed Aug 03, 2016 9:55 am

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

Re: speed up your engine part 4

Post by flok » Wed Aug 03, 2016 10:36 am

brtzsnr wrote: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
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: speed up your engine part 4

Post by brtzsnr » Wed Aug 03, 2016 10:54 am

flok wrote: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
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: speed up your engine part 4

Post by Sven » Wed Aug 03, 2016 11:41 am

flok wrote:
brtzsnr wrote: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
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: speed up your engine part 4

Post by Sven » Wed Aug 03, 2016 11:44 am

brtzsnr wrote:
flok wrote: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
Posts: 3819
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: speed up your engine part 4

Post by Sven » Wed Aug 03, 2016 11:52 am

lauriet wrote: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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: speed up your engine part 4

Post by bob » Wed Aug 03, 2016 12:34 pm

Sven Schüle wrote:
lauriet wrote: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
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: speed up your engine part 4

Post by lauriet » Wed Aug 03, 2016 12:43 pm

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

lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: speed up your engine part 4

Post by lauriet » Wed Aug 03, 2016 12:43 pm

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

Post Reply