How do you generates moves ?

[mathmoi]

Hi,

I'm planning of rewriting my chess engine and i'm currently wondering how should I generates moves.

There is lots of possibilities :

We can generates all moves at once, I think Pro Deo do this. The principal advantage is that we can do a better move ordering, however lots of moves get generated, sorted, but never used.

On the opposite we can generate moves one by one. This way we do not generate any move that are not needed, but move ordering is more difficult (SEE and other heuristics can not be used).

A more popular way (I think) is to generates captures first (including promotions) then the others moves if no capture did cause a cutoff.

I currently used the last techniques. However I think this is not the most efficient way. There is probably some hybrid techniques that involve generatings only some moves at a times instead of only one. Or maybe you generates moves from one type of pieces at a time... things like that. I don't really know. I would'nt be asking if I knew.

So how do your engines (or other engines you know about) generates and order moves ?

Mathieu Pag

[Pradu]

Here's my order of generating moves:

1) Promotions
2) Castling
3) Pawn Moves
4) Knight Moves
5) Bishop Moves
6) Rook Moves
7) Queen Moves
8) King Moves

I generate moves all at once and then order them. I also do not see how moves can be generated one by one and played in the order of the move generation (except for mabe the hashed move).

[mathmoi]

Here's my order of generating moves:

1) Promotions
2) Castling
3) Pawn Moves
4) Knight Moves
5) Bishop Moves
6) Rook Moves
7) Queen Moves
8) King Moves

I generate moves all at once and then order them. I also do not see how moves can be generated one by one and played in the order of the move generation (except for mabe the hashed move).

Hi,

You do not order captures before normals moves ? I think this greatly reduce your branching factor. This is IMHO the least of move ordering.

About generating moves one by one : I think do not think anyone do this exactly like this, but it is possible. However I think it can not be really efficient since you can not even order your moves in anyway, other than the way you generate them.

So do someone really use a one by one move generations algorithm?

Mathieu Pag

[Pradu]

You do not order captures before normals moves ? I think this greatly reduce your branching factor.

I use SEE to order the moves. I'll have to experiment with capture moves ordered first before I implement it.

[mathmoi]

Partial move ordering can be done by using the followings:

1.Move in the hashtable or in the PV.
2.Promote to piece value.
3.Value of captured piece - value of capturing piece.
4.Piece square table delta value for the move.
5.Killers and history bonus.


I try hashed moves first and only generate moves when no cut-off occurs.

Normal move generation order:
Captures and promotions
Non-captures

Special move generation:
Check evasion


Good luck with you engine.


Andrew

Hi Andrew,

If I understand you what you do is :

Code: Select all

Try the hash move
If (no cutoffs occurs) then
   Generates all other moves and order them
endif

Is it this or the move are generated more incrementally ?

Mathieu Pag

[Thomas Mayer]

Hi,

well, at least theoretically you can also try another way to create moves:

you can update a move list incrementally. E.g. when you update your attack-tables in the deepening this can also be used to create moves. It might happen that I will try that once in the future. Of course it will cause me a lot of headaches, but still I like that idea - for now just as a kind of programming contest...

Greets, Thomas

P.S.: Anyway it will not play a big role, move generation is not a really big part of engine strength - whereas move ordering is for sure. I believe that move ordering is still a big field of possible improvements in computer chess. Of course I might be wrong...

[Pradu]

you can update a move list incrementally.

Won't the overhead of incrementing be more than the generation of new moves if using bitboards?

[Josu? Forte]

Hi,

I am curious if anybody there knows about an engine that update the move list incrementally. If so, please let me know.

Concerning the technic that generates one move at a time, I can mention that Matheus uses this approach. The advantage of this technic is that the engine can generate a high rate of NodesPerSecond. Probably, Matheus is the fastest UCI/Winboard engine in terms of NPS.
The disavantage is that the move ordering is not so efficient.

Regards,
Josu

[mathmoi]

you can update a move list incrementally.

Won't the overhead of incrementing be more than the generation of new moves if using bitboards?

I have ponder with this idea for quite a time now. I plan to do try this early in my next engine devellopment. I do think that it is possible that the overhead of being incremental can be smaller than to re-generete move list all the time, even if my generator is bitboard based.

One avantage of a bitboard-based-incremental move generator is that it is easy and fast to find for wich pieces the moves need to be regenerated. Say you move a piece from c1 to c4. You must regenerates the moves for:

1) That piece
2) All the pice attacking c1
3) All the piece attacking c4

2) and 3) can be easily found using the attack_from[] table that every bitboard program implent in a form or an other.

However, thoses moves that need to be re-generated must not be regenerated after MakeMove, but they need to be regenarated as late as possible (This behavior can be hidden in a OO structure) because then can never be used because 1) a cutoff occur 2) the search as reach is maxximum depth (Note that the moves from the last 2 plies do not need to be regenerated).

As always, I can not say if it will be faster or as fast (in wich case it's not worth the trouble) as a classical move generator before i try it, but it seem possible to me.

So, i'll try.

Mathieu Pag

[Pradu]

Also keep in mind updating the move list where there are illegal moves in the list. The accumulation of illegal moves in the move list might slow down the program a lot in certain positions.

And if you use rotated bitboards for move generation, your makemove will be slower than the actual generation of the move (in perft).

[Matthias Hartwich]

Outdated, but perhaps still a nice source is Chess 0.5, published in BYTE 27 years ago. You can get the source here: http://www.moorecad.com/standardpascal/Chess05.pas.
The moves are generated incrementally in small chunks.

Be careful, in the source are some bugs (I typed in the program in the early 1990s) and the scan might be not like the printed original.

Matthias

[Sven Schüle]

Hi Matthias,

the link is slightly wrong, remove the dot "." at the end. Nevertheless, a nice source, close to an assembler program!

The moves are generated incrementally in small chunks.

Do you mean "incrementally" in the sense of updating only that part of the move list which is affected by the most recent move, or in the sense of generating moves one (or few) at a time?

Sven

[Sven Schüle]

you can update a move list incrementally.

Won't the overhead of incrementing be more than the generation of new moves if using bitboards?

[...]
One avantage of a bitboard-based-incremental move generator is that it is easy and fast to find for wich pieces the moves need to be regenerated. Say you move a piece from c1 to c4. You must regenerates the moves for:

1) That piece
2) All the pice attacking c1
3) All the piece attacking c4

Hi Mathieu,

you will probably maintain one move list per colour. Each move may affect both move lists then, concerning your items 2+3. Furthermore, there are several special nontrivial cases, think of e.p., promotion or castling stuff. Then, checks are problematic, most replies become illegal but two plies later the same moves are legal again very often. Recalculate, or save the previously legal moves when detecting check? Pinning a piece is similar.

Also consider the effort for restoring the move list when unmaking a move.

Incrementally updating a move list may indeed require some tricky data structures to allow for efficient insert/remove operations. Instead of one linear move list, you might want to maintain a list of move lists, one per piece (consider capturing a queen, or moving a piece which was attacked by a rook and a bishop and defended by two rooks; much removing and inserting to be done).

Bitboards may help here partially but AFAIK you need a move list, too (please correct me if I'm wrong because I'm not an experienced bitboarder).

In my opinion all this produces a very large overhead, so I doubt whether this could be an improvement.

But I do not intend to discourage you, nor anyone else who is interested in trying incremental move generation. Feel free to show why I'm wrong!

Sven

[Reinhard Scharnagl]

SMIRF initially had used an incremental move generator. To make it work it is necessary that all piece lists will be restored 100% correctly after making and unmaking a move.

Actually SMIRF does no longer use that approach, because of questions of move ordering. Nevertheless I also had tried to generate an existing killer or probably optimal move first and to avoid move ordering. May be some day I go back to that sequential approach.

SMIRF is using a flat board representation using pieces implicitely constituting two double linked piece lists, where single pieces also provide bit encoded properties.

Smirf's move generator creates only valid moves bearing a lot of information as partially shown in the following Perft variation statistic (Intel P4, 2.8 GHz). (The information whether a move would be a mate or not could be switched off where not needed, because this costs about 1/8 of move generation speed.)

Code: Select all

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

  +-*--b--c--d--*--f--g--*-+ MS Vis.Studio C++ Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Aug 11 2005)
7 |[p][p][p][p][p][p][p][p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   |
4 |   :::   :::   :::   :::| (without caching)
3 |:::   :::   :::   :::   |
2 |<P><P><P><P><P><P><P><P>| Smirf Test No.: 00
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 5.0 Sec.

Ply      Nodes     all (x)   (e.p.)    all (+)      (#)  Prom.   Castl.    Sec.
-------------------------------------------------------------------------------
1           20           0        0          0        0      0        0       0
2          400           0        0          0        0      0        0       0
3         8902          34        0         12        0      0        0       0
4       197281        1576        0        469        8      0        0       0
5      4865609       82719      258      27351      347      0        0     0.2
6    119060324     2812008     5248     809099    10828      0        0     4.8
7   3195901860   108329926   319617   33103848   435767      0   883453   126.1
-------------------------------------------------------------------------------


FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25

  +-*--b--c--d--*--f--g--*-+ MS Vis.Studio C++ Vers. 13.10
8 |[r]:::   :::[k]:::   [r]| (Compilation: Aug 11 2005)
7 |[p]   [p][p][q][p][b]   |
6 |[b][n]   :::[p][n][p]:::| Perft Testseries
5 |:::   :::<P><N>   :::   |
4 |   [p]   :::<P>:::   :::| (without caching)
3 |:::   <N>   :::<Q>:::[p]|
2 |<P><P><P><B><B><P><P><P>| Smirf Test No.: 01
1 |<R>   :::   <K>   :::<R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 5.0 Sec.

Ply      Nodes     all (x)  (e.p.)   all (+)     (#)   Prom.    Castl.     Sec.
-------------------------------------------------------------------------------
1           48           8       0         0       0       0         2        0
2         2039         351       1         3       0       0        91        0
3        97862       17102      45       993       1       0      3162        0
4      4085603      757163    1929     25523      43   15172    128013      0.2
5    193690690    35043416   73365   3309887   30171    8392   4993637      8.2
-------------------------------------------------------------------------------


Regards, Reinhard.

[mathmoi]

you can update a move list incrementally.

Won't the overhead of incrementing be more than the generation of new moves if using bitboards?

[...]
One avantage of a bitboard-based-incremental move generator is that it is easy and fast to find for wich pieces the moves need to be regenerated. Say you move a piece from c1 to c4. You must regenerates the moves for:

1) That piece
2) All the pice attacking c1
3) All the piece attacking c4

Hi Mathieu,

you will probably maintain one move list per colour. Each move may affect both move lists then, concerning your items 2+3. Furthermore, there are several special nontrivial cases, think of e.p., promotion or castling stuff.

Effectively such a move generator will need a MoveList for each sides. As for en passant move, maybe they can be regenerated on the fly. Same things for the castling moves.

Then, checks are problematic, most replies become illegal but two plies later the same moves are legal again very often. Recalculate, or save the previously legal moves when detecting check? Pinning a piece is similar.

My actual move generator is a pseudo-legal move generator one. I though the incremental one could be one too.

Also consider the effort for restoring the move list when unmaking a move.

Incrementally updating a move list may indeed require some tricky data structures to allow for efficient insert/remove operations. Instead of one linear move list, you might want to maintain a list of move lists, one per piece (consider capturing a queen, or moving a piece which was attacked by a rook and a bishop and defended by two rooks; much removing and inserting to be done).

Bitboards may help here partially but AFAIK you need a move list, too (please correct me if I'm wrong because I'm not an experienced bitboarder).

In my opinion all this produces a very large overhead, so I doubt whether this could be an improvement.

Possible. I don't even except it to be lot faster than my current move generator, but I think it's worth a try.

But I do not intend to discourage you, nor anyone else who is interested in trying incremental move generation. Feel free to show why I'm wrong!

Sven

[Roman Hartmann]

Hi all,
I'm not sure how important a fast move generator really is. Probably a good move ordering is more important than just generating all of the moves fast. My move generator generates currently only a list of legal moves at every ply.
works like that:
-creating all legal moves in a certain position
they are created in a certain order:
--castling moves
--king moves
--knight moves
--pawn moves (includes ep, promotion moves)
--rook moves
--bishop moves
--queen moves
-sorting them according to square tables+material gain

That means I generate a lot of stuff I never need as soon as the engine starts to play chess. The perft values don't look that bad but it's hell as soon as it starts to search. There is no QS implemented yet btw, that's the reason the PV looks a bit funny.

Roman

Code: Select all

roce: setboard rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
roce: disp

8   {r}{n}{b}{q}{k}{b}{n}{r}
7   {p}{p}{p}{p}{p}{p}{p}{p}
6    .  .  .  .  .  .  .  .
5    .  .  .  .  .  .  .  .
4    .  .  .  .  .  .  .  .
3    .  .  .  .  .  .  .  .
2   [P][P][P][P][P][P][P][P]
1   [R][N][B][Q][K][B][N][R]

     a  b  c  d  e  f  g  h
ply: 1, turn: white
castling: QKqk
white king: e1 black king: e8

roce: perft 5
Perft (5): 4865609 nodes, Time: 0.407 s
roce: perft 6
Perft (6): 119060324 nodes, Time: 11.093 s

roce: setboard r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
0 25
roce: disp


8   {r} .  .  . {k} .  . {r}
7   {p} . {p}{p}{q}{p}{b} .
6   {b}{n} .  . {p}{n}{p} .
5    .  .  . [P][N] .  .  .
4    . {p} .  . [P] .  .  .
3    .  . [N] .  . [Q] . {p}
2   [P][P][P][B][B][P][P][P]
1   [R] .  .  . [K] .  . [R]

     a  b  c  d  e  f  g  h

ply: 25, turn: white
castling: QKqk
white king: e1 black king: e8

roce: perft 4
Perft (4): 4085603 nodes, Time: 0.281 s
roce: perft 5
Perft (5): 193690690 nodes, Time: 12.813 s

roce: analyze

depth     nodes   score time best line
  1          20   0.25  0.00 d2d4
  2         170   0.00  0.00 d2d4 e7e5
  3        1773   0.25  0.00 d2d4 d7d5 e2e4
  4       18282   0.00  0.01 b1c3 e7e5 e2e4 d7d5
  5      238934   1.05  0.23 e2e4 b8c6 f1b5 c6d4 b5d7
  6     2123001  -0.78  2.25 b2b3 e7e6 c1b2 d8h4 b1c3 h4f2
  7    15885018   0.99 17.27 b1c3 e7e6 e2e4 f8b4 c3b5 g8f6 b5c7
[quote][/quote]

[Roman Hartmann]

forgot about the hardware. I made the perft test on an AMD XP 3200+ which runs at 2.2Ghz.

Roman

[Pradu]

creating all legal moves in a certain position
they are created in a certain order:
--castling moves
--king moves
--knight moves
--pawn moves (includes ep, promotion moves)
--rook moves
--bishop moves
--queen moves
-sorting them according to square tables+material gain

I generate "regular" moves starting with pawns and moving my way up in material.

Mabe generating piece moves in a certain order will reduce branching factor even more. Is there any previous research done on branching factor and the order of generation according to piece? I am unable to do these tests currently because my engine is not complete enough yet.