Just another movegen

[Joost Buijs]

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 & &#40;bbfrom << 8&#41;;
		bdt2 = 0xff000000 & ~pos->occupied & &#40;bbto << 8&#41;;

		while &#40;bbto&#41; &#123;
			to = LSB&#40;bbto&#41;;
			&#40;moves++)->Store&#40;to - 8, to, QuietMove | PawnMove&#41;;
			bbto &= bbto - 1;
		&#125;

		while &#40;bdt2&#41; &#123;
			to = LSB&#40;bdt2&#41;;
			&#40;moves++)->Store&#40;to - 16, to, QuietMove | PawnMove | PawnMove2, to - 8&#41;;
			bdt2 &= bdt2 - 1;
		&#125;

	if &#40;White == stm&#41; &#123; // white pawn captures and promotions

		// right direction

		// promotion with capture
		bbfrom = 0x7f000000000000 & pos->bitboards&#91;White&#93;.pawns;
		if &#40;bbto & bbfrom << 9&#41; &#123;
			&#40;moves++)->Store&#40;to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Queen&#41;;
			&#40;moves++)->Store&#40;to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Rook&#41;;
			&#40;moves++)->Store&#40;to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Knight&#41;;
			&#40;moves++)->Store&#40;to - 9, to, Promotion | Capture | PawnMove, WhitePiece | Bishop&#41;;
		&#125;

		// capture with pawn
		bbfrom = 0x7f7f7f7f7f00 & pos->bitboards&#91;White&#93;.pawns;
		if &#40;bbto & bbfrom << 9&#41;
			&#40;moves++)->Store&#40;to - 9, to, Capture | PawnMove&#41;;

		// enpassant capture
		if &#40;bbep & bbto << 8 & bbfrom << 9&#41;
			&#40;moves++)->Store&#40;to - 1, to + 8, Capture | Enpassant | PawnMove, to&#41;;

		// left direction

		// promotion with capture
		bbfrom = 0xfe000000000000 & pos->bitboards&#91;White&#93;.pawns;
		if &#40;bbto & bbfrom << 7&#41; &#123;
			&#40;moves++)->Store&#40;to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Queen&#41;;
			&#40;moves++)->Store&#40;to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Rook&#41;;
			&#40;moves++)->Store&#40;to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Knight&#41;;
			&#40;moves++)->Store&#40;to - 7, to, Promotion | Capture | PawnMove, WhitePiece | Bishop&#41;;
		&#125;

		// capture with pawn
		bbfrom = 0xfefefefefe00 & pos->bitboards&#91;White&#93;.pawns;
		if &#40;bbto & bbfrom << 7&#41;
			&#40;moves++)->Store&#40;to - 7, to, Capture | PawnMove&#41;;

		// enpassant capture
		if &#40;bbep & bbto << 8 & bbfrom << 7&#41;
			&#40;moves++)->Store&#40;to + 1, to + 8, Capture | Enpassant | PawnMove, to&#41;;

	&#125; // end white

Even though I use loops perft 6 takes 0,94 seconds on a 3.6 GHz. Haswell.
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.

[Henk]

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 ?

[Joost Buijs]

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 ?

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.
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.

[stegemma]

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.

[Henk]

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 ?

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.
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.

Are you the chess programmer that is still active and has written the oldest engine ?

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.

[Joost Buijs]

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 ?

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.
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.

Are you the chess programmer that is still active and has written the oldest engine ?

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.

With punch cards it is very difficult, at that time I already had a video terminal.
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.

[Joost Buijs]

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.

Of course, that is why we are busy with computer chess, to experiment.
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.

[stegemma]

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:

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...

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.