Author: Nicolas Carrasco
Date: 12:40:46 11/19/99
Go up one level in this thread
Thanks
On November 18, 1999 at 07:06:34, Bas Hamstra wrote:
>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 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.