cheaper search ?

[James F. Long]

Instead of doing the typical (at least I think it's typical) routine when searching, I
have an idea that could possibly save some computation time. By typical, I mean :

(1) selecting which move to try next from the current list
(2) updating the position by making that move
(3) recursively call search at depth N-1
(4) "undo" the move from step 2

In my program, Tristram, I simply duplicate the position, and when the result of the
search comes back, I discard the duplicate. This way I never have to undo a move.
Tristram doesn't even have an "undo" function. The down side of this is having to
pass an extra parameter, the chess position (or at least a pointer to one) to
the search routine.

The following illustrates this :

search (CHESS_POSITION* pos,int alpha,int beta,int ply,int depth)
{
CHESS_POSITION newpos;

.
.
.
while (c<num_moves && best<beta) {
newpos = *pos;
// select next move here.
// update newpos here.
.
value = -search(&newpos,-beta,-alpha,ply+1,depth-1);
.
.
.
}
return best;
}

Note that the chess move doesn't have to reflect any captured pieces using
the routine above.

Has this been tried before? Would it be more efficient to use one global
chess position, "unmaking" the move each time a search result comes back?

James

[Robert Hyatt]

James F. Long (wzrd...@fia.net) wrote:
: Instead of doing the typical (at least I think it's typical) routine when searching, I

: have an idea that could possibly save some computation time. By typical, I mean :

: (1) selecting which move to try next from the current list
: (2) updating the position by making that move
: (3) recursively call search at depth N-1
: (4) "undo" the move from step 2

: In my program, Tristram, I simply duplicate the position, and when the result of the
: search comes back, I discard the duplicate. This way I never have to undo a move.
: Tristram doesn't even have an "undo" function. The down side of this is having to
: pass an extra parameter, the chess position (or at least a pointer to one) to
: the search routine.

It's actually *much* worse than you suspect. I did this on very early versions
of Crafty, but it turns out you are beating on the weakest part of the PC's
hardware architecture, the memory system... when you "duplicate" a position,
you have to copy the old board information to a new place in memory. This
results in a lot of cache thrashing as well as cache misses, exactly what the
PC can least afford to have happen...

: The following illustrates this :

: search (CHESS_POSITION* pos,int alpha,int beta,int ply,int depth)
: {
: CHESS_POSITION newpos;

: .
: .
: .
: while (c<num_moves && best<beta) {
: newpos = *pos;
: // select next move here.
: // update newpos here.
: .
: value = -search(&newpos,-beta,-alpha,ply+1,depth-1);
: .
: .
: .
: }
: return best;
: }

: Note that the chess move doesn't have to reflect any captured pieces using
: the routine above.

: Has this been tried before? Would it be more efficient to use one global
: chess position, "unmaking" the move each time a search result comes back?

Yes, by a significant amount too... I don't recall when I converted to make/unmake
in crafty (you can check main.c to find out) but it was a significant improvement.
On the PC, cache hits are *all* important... Anything that interferes will only
hurt performance...

: James

[Shaun Press]

James F. Long wrote:
>
> Instead of doing the typical (at least I think it's typical) routine when searching, I
> have an idea that could possibly save some computation time. By typical, I mean :
>
> (1) selecting which move to try next from the current list
> (2) updating the position by making that move
> (3) recursively call search at depth N-1
> (4) "undo" the move from step 2
>
> In my program, Tristram, I simply duplicate the position, and when the result of the
> search comes back, I discard the duplicate. This way I never have to undo a move.
> Tristram doesn't even have an "undo" function. The down side of this is having to
> pass an extra parameter, the chess position (or at least a pointer to one) to
> the search routine.

<snip>

>
> James

The benefits: It's simple (as described above)
The problems: It's very slow

My early versions of Vanilla Chess used this method. However, profiling
the program showed that over 50% of execution time was involved in
_memcpy. Once I ditched the "save and restore" method and replaced it
with "move and unmove" that figures droped to about 20% and my program
ran twice as fast. I still save and restore the position flags at the
moment (50 move, kinside & queenside castling etc) but even they may
go in a future rewrite.
However, KnighCap (written by Andrew Tridgell) still uses "save and
restore" and his program does quite well. Of course he stores the
position in the smallest number of bits he can.

[Marcel van Kervinck]

James F. Long (wzrd...@fia.net) wrote:

> In my program, Tristram, I simply duplicate the position, and
> when the result of the > search comes back, I discard the duplicate.
> This way I never have to undo a move. > Tristram doesn't even have
> an "undo" function. The down side of this is having to

Duplicating the position is a bad idea. A move typically only changes
2 squares, which is much faster than copying. It may be, however,
beneficial to duplicate other info, such as partial evaluations,
attack tables and hash signatures. Attack tables may change enough
during a move to justify copying, but not always. For the other
information duplicated: keeping 'undo' simple helps to prevent
the instruction caches from trashing.

At the moment I'm using a hybrid approach: if it seems reasonable
that the attack tables won't change much, I don't bother to
copy and just have to remember to undo the changes at undo time.
Otherwise, I copy, and discard the copy later.

Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.nl

[Paul Rubin]

In article <5k0cji$f...@juniper.cis.uab.edu>,

Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>: In my program, Tristram, I simply duplicate the position, and when
>: the result of the search comes back, I discard the duplicate. This
>: way I never have to undo a move. Tristram doesn't even have an

>: "undo" function. The down side of this is having to pass an extra

>: parameter, the chess position (or at least a pointer to one) to the
>: search routine.
>

>It's actually *much* worse than you suspect. I did this on very
>early versions of Crafty, but it turns out you are beating on the
>weakest part of the PC's hardware architecture, the memory system...
>when you "duplicate" a position, you have to copy the old board
>information to a new place in memory. This results in a lot of cache
>thrashing as well as cache misses, exactly what the PC can least
>afford to have happen...

Since you only have to store one board per play, it basically takes a
fixed amount of memory to do this, and caches are getting larger. In
Crafty, the board is represented as what, a dozen or so bitboards of 8
bytes each? Say 100 bytes or so. That means 1k of cache should be
able to hold about 10 ply. Are these numbers reasonable? What kind
of cpu did early versions of crafty run on? Current high end Intel
x86 cpu's have 8k or 16k of on-chip data cache, and typically 256k
or more off-chip L2 cache.

[Robert Hyatt]

Paul Rubin (p...@netcom.com) wrote:
: In article <5k0cji$f...@juniper.cis.uab.edu>,

The slowest machine I used was a P5/133, with the usual
16kb on-chip + 256K PB cache. However, Crafty regularly probes to ply=50
during the search, so you need 100X50 bytes.. and that results in a lot of
data movement...

And remember that the cache is set-associative on chip, but typically
direct-mapped for L2.. so that you have little control over what gets
flushed from cache when you move data around like that... And when you modify
cache, and then that line is replaced, it is still written back to memory.
And the first reference to it later will then refill it...