Legal move generator

[jwes]

you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

This works only for direct attacks, not discovered attacks.

You could use the from square to check for possible discovered attacks (with some additional fiddling).

[sje]

you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

This works only for direct attacks, not discovered attacks.

You could use the from square to check for possible discovered attacks (with some additional fiddling).

Yes, but even more fiddling is needed if that last move was an en passant capture, a castling, or a promotion. Or also if the position was set up and there was no last move.

With a bitboard program the fiddling is unnecessary. All that is needed is a single bit test of the king's square bit in the merged attack bitboard of the other color.

[trojanfoe]

I use the same scheme, and do discovered check removal within the move() function - all other legalities are checked in the move generator.

I don't implement unmove() however - I just blat the parent position over before each move() - as I don't see the point of the complexity involved in unmove(). Has anyone tried both and found unmove() to be better performance?

I get about 2-3Mnps on a 32-bit CPU, but about 6-7Mnps on a 64-bit CPU, so it seems about the same performance as yours.

Cheers,
Andy

[Roman Hartmann]

you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

This works only for direct attacks, not discovered attacks.

I'm not sure if you got me right.

This is what he's doing rightnow:

Code: Select all

legals := EmptyStack()
stack := GeneratePseudoLegalMoves(pos)
FOR ALL move IN Stack
    PlayMove(pos, move)
    IF NOT IsAttackedSquare(pos, pos.king_square[opponent(pos.side_to_move)])
        add(legals, move)
    END IF
    UndoMove(pos, move)
END FOR

And those are the additions I'm suggesting. (I changed the pseudocode slightly):

Code: Select all

legal_moves=generate_pseudolegalmoves(pos,moves);
for &#40;i=1; i <= legal_moves; i++) &#123;
	if&#40;I_m_not_in_check_already&#40;pos&#41;) &#123;
		if &#40;attack&#91;move&#91;i&#93;.from_square&#93;&#91;own_king&#93;==0&#41;
			add&#40;legal,move&#91;i&#93;);
		else &#123;
			PlayMove&#40;pos,move&#91;i&#93;);
			if &#40;I_m_not_in_check&#40;pos&#41;)
				add&#40;legal,move&#91;i&#93;);
			undoMove&#40;pos,move&#91;i&#93;);
		&#125;
	else &#123;
		PlayMove&#40;pos,move&#91;i&#93;);
		if &#40;I_m_not_in_check&#40;pos&#41;)
			add&#40;legal,move&#91;i&#93;);
		undoMove&#40;pos,move&#91;i&#93;);
		&#125;
	&#125;
&#125;

So you're actually checking if you're putting you're own king into check when you move one of your own pieces. After you have made sure that you're not already in check. Most squares have no connection with the square the own king is located on and in all those cases you don't need to call attack() (actually I named it I_m_not_in_check() in the pseudocode and attack[sq_from][sq_king] is the table).

This sheme pays off only if you're generating all legal moves in a certain position, of course.

best regards
Roman

[Samuele Giraudo]

Thanks for your replies.

I think it is nearly optimal to generate only legal moves by the methods that you describe.

Anyway, I have found a schema which seem efficient : in the search function (alphabeta with transposition table), I generate only pseudo legal moves and I test them by verifying that the move played do not leave the king to attack.

With this schema, I obtain an interesting node rate : about 300 000 nps versus 50 000 nps with the schema described in my first post.
I think that even if I improve my evaluation function, I will finally keep the same node rate because this numbers are given by a 32 bit processor and I use rotated bitboards.

Best regards,
Samuele Giraudo

[Tord Romstad]

you could add a precalculated array which tells you if two certain squares have any connection.
With such an array you would only need to call attack() if there is a connection between the square you're moving a piece and the square of the king.

This works only for direct attacks, not discovered attacks.

You could use the from square to check for possible discovered attacks (with some additional fiddling).

Yes, but even more fiddling is needed if that last move was an en passant capture, a castling, or a promotion. Or also if the position was set up and there was no last move.

Not really. You can just handle these cases in the most straightforward possible way: Test move legality by making and unmaking the move with an in-check test in between, find checking pieces by looping through all pieces and test whether they attack the enemy king, and so on. It will only add a handful of very simple lines to your code, and it doesn't matter that it is slow, because such situations are rare.

With a bitboard program the fiddling is unnecessary. All that is needed is a single bit test of the king's square bit in the merged attack bitboard of the other color.

This is only true if you assume that we have already generated all attack bitboards. Many programmers wouldn't want to do that at every node, for efficiency reasons. And if you do want to generate all attacks at every node, you may as well do the same in a non-bitboard program.

I have written both bitboard and non-bitboard programs, and in my experience, operations like move legality tests and check detection are easier and cleaner without bitboards. But in any case, the difference is very minor. People spend way too much time and energy discussing the merits of various board representations. The simple truth is that it hardly matters at all. Whether you use bitboards, 0x88 or something else is just a minor implementation detail, which has very little impact on the speed and strength of your program.

Tord

[Tord Romstad]

Anyway, I have found a schema which seem efficient : in the search function (alphabeta with transposition table), I generate only pseudo legal moves and I test them by verifying that the move played do not leave the king to attack.

That's similar to what I do, too: I generate pseudo-legal moves (except when the side to move is in check), and test each move for legality just before I make it.

Tord

[sje]

Before comparing the efficiency of bitboards vs non-bitboards, there has to be a definition of exactly what a bitboard program is. And there is no exact definition as different bitboard programs will employ bitboards differently.

Let's define a bitboard database as the set of those bitboards that describe the current position and that are updated or recalculated from poisoner to position as moves are executed or retracted.

Now, some bitboard programs might have only a single bitboard: the bitboard that represents occupied squares. A different bitboard program might also have bitboards for each color and each piece kind. A more advanced bitboard database as seen in a program like Crafty will have bitboard for all attacks from each square and bitboards for all attacks by each color. A program like Chess 4.x will also have bitboards for all attacks to each square. Some programs like Symbolic and the new CIL Toolkit have bitboards for merged sweep pieces, pinned pieces by color, and frozen pieces by color. And I've heard of programs that have bitboard databases that include data on x-rays and batteries.

Some truisms:

1) The more extensive the contents of a bitboard database, the more time will be used to update and the more storage will be needed for allocation. This is the "update slowdown" and the "data cache slowdown".

2) The more extensive the contents of a bitboard database, the more it can be used in various parts of the rest of the program. For example, having pinned piece bitboards helps significantly with supporting legal-only move generation. Having pinned piece bitboards along with a set of attacks-to-square bitboards is very useful for static exchange analysis and also for positional factor evaluation.

3) Having pervasive bitboards speeds up the rest of the program in the sense that quite often only one or two bitboard operations can replace a full board scan loop in a non bitboard program. This is the time savings, and it can be more than enough to justify the extra time used for bitboard database updates.

4) Being able to think in terms of sets can help with higher level code design issues, as it's a (slightly) higher level of abstraction than thinking in terms of squares.

My experience is that bitboards are the way to go, at least if the target machine is a 32 or 64 bit architecture. Maybe for some 16 bitters as well.

[hgm]

In Joker the only non-legal pseudo-legal moves that can get generated are King moves (including castlings) and e.p. captures. For those moves it is tested if the King is in check (through a 0x88 type test) after the move has been made.

All other moves that are generated are legal, which saves both time on not generating illegal moves, and on testing all non-king non-e.p. moves for legality.

[grant]

HG

Does Joker generate pseudo-legal king moves because it is non-bitboard?

If the king has a possible 8 squares it can move to, you would have to make/unmake and test if the king is in check for each move. Whereas I start with a bitboard of king moves and AND out the NEG of all opponent moves.

Grant