Author: Dan Newman
Date: 14:17:11 11/09/00
Go up one level in this thread
On November 09, 2000 at 15:15:49, Michel Langeveld wrote:
>Thank you very much for your response.
>You had a very similiar post of the idea I was thinking about.
>Although I have still some questions about your code additions...
>
>>My suggestion inserted:
>
>I have marked out your code changes and added some questions in it.
>
>>On November 08, 2000 at 05:45:42, Michel Langeveld wrote:
>>
>>>Does someone know a way to check for repetative moves in the correct way.
>>>To help a bit I added this piece of code.
>>>
>
>THashTable h;
>
>int negamax(int depth)
>{
> int best = -MAXINT;
> int score;
>
> //ML: changed this draw line a bit to make clear
> //what with this function is meant
> if ( stale_mate(board) || to_less_material(board) )
> {
> return 0;
> }
>
> hash_entry = obtain_hash_entry ( board, h );
>
> //what do you mean by isvalid.
> //is it possible that a an hashentry is not valid??
I think he means that the hash entry must be for this current
position and not be empty or be for some other position. It is
quite often the case that a hash entry will be for a different
position...
>
> //ML: Is it necesarry to put this line above the mate??
> if ( is_valid(hash_entry) && hash_entry.seen_before == 1 )
> {
> return 0;
> }
>
> if ( mate(board) )
> {
> return 9999; //ML: removed the minus
> }
>
> if ( depth == 0 ) //ML: added a depth == 0 the stop the recursion
> {
> return evaluate();
> }
>
> TMovelist m = makemovelist(board);
>
> for (int i=0; i<movecount; i++)
> {
> make_move(movelist[i], board);
>
> hash_entry.seen_before = 1; //ML: Is it necesarry to put this line
> //here or can it be also above to for?
>
> //ML: we have made a move... so the
> //hash_entry can't be the right value,
> //isn't it? Because the
> //hash_value, was one before
> //the move.
It seems like this could go outside the for-loop. I think you would
need to make sure that the entry can't be changed to be for a different
position inside the search below the current node. I, however, don't
use the hash table to detect repetition--so I might be missing something...
>
> score = -negamax(depth-1)
>
> if (score > best)
> {
> best = score;
> }
> hash_entry.seen_before = 0; /* if it had been seen before we wouldn't
> * get to this point */
>
> //ML: behint the next } ??
> undo_move(movelist[i], board);
> }
>
> return best;
>}
>
>>The idea behind this is that if we can force the opponent into a two-fold
>>repetition, we can also force her into a three-fold repetition. The only case
>>that is missed is a position that has occured twice before in the actual game,
>>so this needs to be taken care of separately.
>>W/o transposition tables it is virtually impossible to check for repetitions.
I use the hashcode itself for this. I keep an array of the hashcodes of the
positions already played on the board and along the current search path and
just do a comparison of the current node's hashcode with the appropriate ones
stored in the array.
1) You can ignore the hashcodes for the opponent's positions, ie, you skip
every other one as you iterate backwards through the hashcode array.
2) You can skip back by 4 at the start (instead of just 2) because you can't
get a repetition with just one move by each side.
3) You only have to go back as far as the last irreversable move (a capture,
promotion, or castling). You can just use the 50-move-rule counter for this
and ignore the castling.
Now the above might sound expensive, but it proves to be very cheap in
practice and very reliable. The chance of two identical hashcodes for
different positions appearing in the (very small) list of hashcodes is
miniscule. And most of the time an irreversable move isn't too far
back.
If you already have two occurances of a position in the already played
positions, then finding one in the search is all you need (obviously).
If you have zero or one in the already played positions, then typically
you let two in the search suffice.
-Dan.
>>
>>Sven
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.