Author: Bas Hamstra
Date: 04:06:34 11/18/99
Go up one level in this thread
Nicholas,
About your question about the precomputed table in GNU chess:
There is a table that contains for a certain piece, at a certain square, all
squares that piece can move to (if the board were emtpy), in the form of a
linked list.
What is the use of this? Well, supose a queen is on a1. Then you look into
Table[0] to fetch the first item of the linked list containing all move-to
squares.
Now each record of the linked list had two pointers:
. *NextDirection
. *Continue
*Continue contains the squares of all sliding moves in one specific direction.
NextDir contains the first square of the next direction.
No testing needed if you are off the board and no adding of offsets. Simply
"dereferencing" pointers which is pretty quick. If a sliding direction is
blocked, you can switch to the next square in the next direction at once.
Regards,
Bas Hamstra.
On November 17, 1999 at 10:14:45, Antonio Dieguez wrote:
>On November 16, 1999 at 14:27:37, Eugene Nalimov wrote:
>
>>Unroll the outer loop, so that iDelta[iDir] become a compile-time constant in
>>the inner loop. Also, you now have 2 calls to AddMove - replace it by one, write
>>something like that:
>>
>> for (iTarg = x+17; ONBOARD(iTarg); iTarg += 17) {
>> iTargContents = PIECE_AT(psPos, iTarg);
>> if (IS_YOUR_COLOR(iTargContents))
>> break;
>> AddMove(psPos, x, iTarg);
>> if (!IS_EMPTY(iTargContents))
>> break;
>> }
>
>for (iTarg = x+17; ONBOARD(iTarg) &&
>!IS_YOUR_COLOR(iTargContents=PIECE_AT(psPos, iTarg)); iTarg += 17) {
>
> AddMove(psPos, x, iTarg);
> if (!IS_EMPTY(iTargContents))
> break;
> }
>
>just a bir shorter.
>
>bye.
>
>>I suspect that ONBOARD(), PIECE_AT(), IS_EMPTY(), etc. are macro. Right? Also,
>>try to inline AddMove().
>>
>>In any case the move generation performance is not very important - but you know
>>that yourself :-).
>>
>>Eugene
>>
>>On November 16, 1999 at 00:26:17, Scott Gasch wrote:
>>
>>>Hi,
>>>
>>>I have been rewriting my engine from the ground up and trying to "do it right"
>>>this second go 'round. For instance, I pruned the move data struct from a huge
>>>56 byte struct down to an int to increase performance ;)
>>>
>>>I have recently been doing Vincent Diepeveen's test of move generation speed to
>>>clock how fast my generator is. In the prior version it generated at about 3
>>>million nodes/sec whereas in this version (with the much smaller move
>>>representation) it is up to about 6 million nodes/sec on my AMD K6-3 450.
>>>
>>>Vincent's test is to generate all successors of:
>>>rnbqkbnr/ppp2ppp/8/3pp3/3PP3/8/PPP2PPP/RNBQKBNR b KQkq e6 0 0
>>>
>>>in a loop, 2000000 times and keep track of how long it takes... then compute
>>>nodes/sec. Vincent gets 15 million in the same position with a slower
>>>processor!
>>>
>>>I have profiled my code and determined that the bottleneck is in my generation
>>>routines (as opposed to AddMove) So my question is this: I currently generate
>>>moves for a specific piece something like this:
>>>
>>> //
>>> // Figure out how the rook can move.
>>> //
>>> for (iDir = 0; iDir < 4; iDir++)
>>> {
>>> iTarg = x + iDelta[iDir];
>>> while (ONBOARD(iTarg))
>>> {
>>> iTargContents = PIECE_AT(psPos, iTarg);
>>>
>>> //
>>> // The rook can move if the square is empty.
>>> //
>>> if (IS_EMPTY(iTargContents))
>>> {
>>> AddMove(psPos, x, iTarg);
>>> }
>>>
>>> //
>>> // Or if there is an enemy piece there to capture.
>>> //
>>> else
>>> {
>>> if (COLOR(iTargContents) != COLOR(iRook))
>>> {
>>> AddMove(psPos, x, iTarg);
>>> }
>>> break;
>>> }
>>> iTarg += iDelta[iDir];
>>> }
>>> }
>
>wow! thats looks exactly extracted of my program.
>
>>>However I see in GNUChess they use some kind of precomputed table. I am not
>>>sure I understand exactly how this works. Also, does anyone else have any other
>>>tricks to speed up move generation? I know that in the long run this really
>>>doesn't make TOO much of a difference but I want my new version to be lean and
>>>mean...
>>>
>>>As always, I appreciate the help.
>>>Scott
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.