Hi Stefano,
I think in the move generator readability of code should come first. If this requires some "if" that's not so bad.
In iCE I even have the luxury of a fully legal move generator, because I find it messy to generate illegal moves. Probably I could speed up my move generator by a few % but iCE spends very little time in move generation overall so a small speedup here won't make a difference.
As reference iCE takes 1.1 secs for perft 6 on my laptop even with some "if" statements. (legal move generators don't need to execute the moves on the last ply but just count them so they are fast)
Thomas
Just another movegen
Moderators: hgm, Rebel, chrisw
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Just another movegen
stegemma wrote: Just to have a reference, in Satana i get perft 6 in:
without test for check at last leave: <4 seconds
with test for check at last leave: >12 seconds
In Nightmare the move generator is very bulky, I don't like to use macros and I want to avoid as many templates as possible.
I generate captures/promotions and quiet moves separately because I do staged move generation.
For pawns I do:
Code: Select all
// pawn moves for white excluding promotions
bbfrom = 0xffffffffff00 & pos->bitboards[White].pawns;
bbto = ~pos->occupied & (bbfrom << 8);
bdt2 = 0xff000000 & ~pos->occupied & (bbto << 8);
while (bbto) {
to = LSB(bbto);
(moves++)->Store(to - 8, to, QuietMove | PawnMove);
bbto &= bbto - 1;
}
while (bdt2) {
to = LSB(bdt2);
(moves++)->Store(to - 16, to, QuietMove | PawnMove | PawnMove2, to - 8);
bdt2 &= bdt2 - 1;
}
if (White == stm) { // white pawn captures and promotions
// right direction
// promotion with capture
bbfrom = 0x7f000000000000 & pos->bitboards[White].pawns;
if (bbto & bbfrom << 9) {
(moves++)->Store(to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Queen);
(moves++)->Store(to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Rook);
(moves++)->Store(to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Knight);
(moves++)->Store(to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Bishop);
}
// capture with pawn
bbfrom = 0x7f7f7f7f7f00 & pos->bitboards[White].pawns;
if (bbto & bbfrom << 9)
(moves++)->Store(to - 9, to, Capture | PawnMove);
// enpassant capture
if (bbep & bbto << 8 & bbfrom << 9)
(moves++)->Store(to - 1, to + 8, Capture | Enpassant | PawnMove, to);
// left direction
// promotion with capture
bbfrom = 0xfe000000000000 & pos->bitboards[White].pawns;
if (bbto & bbfrom << 7) {
(moves++)->Store(to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Queen);
(moves++)->Store(to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Rook);
(moves++)->Store(to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Knight);
(moves++)->Store(to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Bishop);
}
// capture with pawn
bbfrom = 0xfefefefefe00 & pos->bitboards[White].pawns;
if (bbto & bbfrom << 7)
(moves++)->Store(to - 7, to, Capture | PawnMove);
// enpassant capture
if (bbep & bbto << 8 & bbfrom << 7)
(moves++)->Store(to + 1, to + 8, Capture | Enpassant | PawnMove, to);
} // end white
This is with checking for legality and fully updated hash keys etc.
The speed is not very important anyway because move generation only takes about 5% of the total time spent in the program.
Normally I avoid promotions to bishops and in quiescence I only promote to queens.
-
- Posts: 7216
- Joined: Mon May 27, 2013 10:31 am
Re: Just another movegen
I saw in the history of computerschaak a chess engine called nightmare that played in a tournament around 1985. Is your engine really that old ?
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Just another movegen
The current version of the engine is not that old of course. The current version stems from 2001 with some improvements from the last few years.Henk wrote:I saw in the history of computerschaak a chess engine called nightmare that played in a tournament around 1985. Is your engine really that old ?
I wrote my first engine in assembler for the 8080, this was during the fall of 1977 and spring of 1978. In 1981 I switched from assembler to C.
Since that time I have written it 6 times from scratch, the current one is v7.
A couple of weeks ago I started again with a complete rewrite, because I was not very happy with the performance at the last TCEC.
This will probably be the last version, after that I'm getting too old for this stuff. I'm not like Bob.
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: Just another movegen
For me writing a branchless generator is a kind of puzzle, so it is interesting despite from the results. In fact, the speed is far from ideal but i don't use bitboard, i like to experiment new ways.
-
- Posts: 7216
- Joined: Mon May 27, 2013 10:31 am
Re: Just another movegen
Are you the chess programmer that is still active and has written the oldest engine ?Joost Buijs wrote:The current version of the engine is not that old of course. The current version stems from 2001 with some improvements from the last few years.Henk wrote:I saw in the history of computerschaak a chess engine called nightmare that played in a tournament around 1985. Is your engine really that old ?
I wrote my first engine in assembler for the 8080, this was during the fall of 1977 and spring of 1978. In 1981 I switched from assembler to C.
Since that time I have written it 6 times from scratch, the current one is v7.
A couple of weeks ago I started again with a complete rewrite, because I was not very happy with the performance at the last TCEC.
This will probably be the last version, after that I'm getting too old for this stuff. I'm not like Bob.
Writing a chess engine in assembler. That must have been difficult. I remember at school I had to implement the Ackermann function in assembler for the PDP11 using punch cards. That was in 1984.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Just another movegen
With punch cards it is very difficult, at that time I already had a video terminal.Henk wrote:Are you the chess programmer that is still active and has written the oldest engine ?Joost Buijs wrote:The current version of the engine is not that old of course. The current version stems from 2001 with some improvements from the last few years.Henk wrote:I saw in the history of computerschaak a chess engine called nightmare that played in a tournament around 1985. Is your engine really that old ?
I wrote my first engine in assembler for the 8080, this was during the fall of 1977 and spring of 1978. In 1981 I switched from assembler to C.
Since that time I have written it 6 times from scratch, the current one is v7.
A couple of weeks ago I started again with a complete rewrite, because I was not very happy with the performance at the last TCEC.
This will probably be the last version, after that I'm getting too old for this stuff. I'm not like Bob.
Writing a chess engine in assembler. That must have been difficult. I remember at school I had to implement the Ackermann function in assembler for the PDP11 using punch cards. That was in 1984.
I remember a lot of students from one of our local universities coming by to test their Fortran programs on my system, on the university they still used punch cards.
Bob Hyatt started much earlier than me and is still very active, and there must be others as well. So I'm not the one who has written the oldest engine and is still active.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Just another movegen
Of course, that is why we are busy with computer chess, to experiment.stegemma wrote:For me writing a branchless generator is a kind of puzzle, so it is interesting despite from the results. In fact, the speed is far from ideal but i don't use bitboard, i like to experiment new ways.
I have no clue how to write a branchless move generator, at first it seems impossible, but you have done it, probably with combinatorial logic only.
I didn't study the code fragment you showed earlier.
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: Just another movegen
The onyl branchless part is the move generation but still i need loops to store moves and for the other things. Theorycally you can store moves with a branch-less code, but it more than experimental... it would be paranoic
To store moves in a branch-less mode, you can enroll the classical "while Extract Lsb" function, that gives you to destination squares, then store in memory pointed by the move pointer; then you have to increment the pointer if and only if there are other bits set, you can do it branch-less with something like:
The pointer get incremented only if there are moves to store, in fact storing nothing if there are no moves.
In a true program, you repeat useless istruction just to avoid a branch but it is something that maybe could give an hint, maybe in other problems.
The branch-less part of Satana doesn't have such useless instructions and i've compared the "branch-less" with the "if version", getting an interesting improvement.
The branch-less move generator could be changed to use it only as a perft generator, removing all of the stuff related to the full chess-engine and i suppos ethat it could run about from 5 to 10 times faster, but that's not my goal.
To store moves in a branch-less mode, you can enroll the classical "while Extract Lsb" function, that gives you to destination squares, then store in memory pointed by the move pointer; then you have to increment the pointer if and only if there are other bits set, you can do it branch-less with something like:
Code: Select all
get destination square
reset bit
store move
delta = (0-bit_moves)>>63
pointer += delta
get destination square
reset bit
store move
delta = (0-bit_moves)>>63
pointer += delta
...repeat...
In a true program, you repeat useless istruction just to avoid a branch but it is something that maybe could give an hint, maybe in other problems.
The branch-less part of Satana doesn't have such useless instructions and i've compared the "branch-less" with the "if version", getting an interesting improvement.
The branch-less move generator could be changed to use it only as a perft generator, removing all of the stuff related to the full chess-engine and i suppos ethat it could run about from 5 to 10 times faster, but that's not my goal.