Handling 3-rep/50-move in hash tables

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Handling 3-rep/50-move in hash tables

Postby Pradu » 19 Feb 2007, 07:19

I came across a bug in my chess program which I believe concerns the technique of handling 3-rep and fifty move rules in the hash table:

[diag]8/8/8/8/2k5/1p6/8/1K6[/diag]
8/8/8/8/2k5/1p6/8/1K6 b - - 1 2
This is a drawn position that occured during the CCT9 game Chezzz-Buzz

Here is my default hash table probing code:
Code: Select all
#ifdef USE_HASH
if(tt_depth>=depth)
{
   if(tt_score>=MATE_MIN) tt_score-=dfr;
   else if(tt_score<=-MATE_MIN) tt_score+=dfr;
   switch(tt_flag)
   {
   case HASHFLAG_EXACT:
      return tt_score;
   case HASHFLAG_LOWER_BOUND:
      {
         if(tt_score>=beta) return tt_score;
         #ifdef UPDATE_BOUNDS
         if(tt_score>alpha) alpha=tt_score;
         #endif
         break;
      }
   case HASHFLAG_UPPER_BOUND:
      {
         if(tt_score<=alpha) return tt_score;
         #ifdef UPDATE_BOUNDS
         if(tt_score<beta) beta=tt_score;
         #endif
         break;
      }
   }
}
#endif //USE_HASH


Here are the results using hash table with the default probing code and not using the hash table.
Code: Select all
(Depth) (Score) (Time centi-seconds) (Nodes) (PV)
Using-Default hash probing:
128 159 817 2568428 Kb5 Ka1 Ka5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4

No-hash probing
14 0 137 633498 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kc3 Ka1 Kd3 Kb2 Ke2 Ka1 Kd1 Kb2 Ke1 Ka1 Kd1


I investigated the result by tracing the search that uses the hash table:

Code: Select all
Kb5 (-32000, 32000)
 Ka1 (-31998, 31999)
  Ka5 (-31997, 31998)
   Kb1 (-31996, 31997)
    Ka4 (-31995, 31996)
     Kb2 (-31994, 31995)
      Kb4 (-31993, 31994)
       Kb1 (159, 31993)
        Ka4 (-31991, -159)

After playing the move Kb4, the bounds were updated using the hash table to (-31993,-159) ... which is incorrect. After some investigation I realized that the hashed score was dependent on the path to the node when taking into account 3-rep and 50-move rules and therefore the hash table entry cannot be used to return/cut-off/update bounds at the position. How does one handle the path-dependencies from 3-rep and fifty-move rule in the hash table? I'm totally stumped.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 19 Feb 2007, 08:32

I found updating bounds from hashtable too dangerous. (I handle pv nodes slightly different)

Same for probing/cutting off in pv nodes (to avoid path depending stuff from entering the pv).

Both off these are aplied at pv nodes, making using both off them very dangerous.

Cheers,

Tony
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Pradu » 19 Feb 2007, 09:10

Tony van Roon-Werten wrote:I found updating bounds from hashtable too dangerous. (I handle pv nodes slightly different)

Same for probing/cutting off in pv nodes (to avoid path depending stuff from entering the pv).

Both off these are aplied at pv nodes, making using both off them very dangerous.

Cheers,

Tony


I realize now that it may be too dangerous if one does not handle 3-rep and fifty move properly, but perhaps we can find a way to do this? In fact, even returning exact scores is wrong if path dependencies aren't handled properly in any part of the search tree.

Correct me if I'm wrong. Avoiding bounds updating doesn't fix the path-dependency problem completely. Also, the speed bonus from updating bounds can be very impressive:

[diag]8/8/8/8/3k4/4R3/2K5/8[/diag]
8/8/8/8/3k4/4R3/2K5/8 w - - 0 1

Code: Select all
Buzz search (PVS with no pruning)
Pentium 4, 2.8 Ghz, 32-bits exe
1 530 0 1 Rc3
1 536 0 8 Kd2
1 539 0 14 Ra3
1 539 0 25 Ra3
2 536 1 32 Ra3 Ke4
2 536 1 111 Ra3 Ke4
3 542 1 150 Ra3 Ke4 Ra8
3 542 1 556 Ra3 Ke4 Ra8
4 539 1 798 Ra3 Kc4 Rf3 Kb4
4 542 1 1560 Re8 Kd5 Ra8 Kd4
4 542 1 2172 Re8 Kd5 Ra8 Kd4
5 542 3 2685 Re8 Kd5 Ra8 Kd4 Ra1
5 542 3 7509 Re8 Kd5 Ra8 Kd4 Ra1 Kd5
6 542 4 9205 Re8 Kd5 Re1 Kd4 Ra1 Kd5
6 542 6 22020 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
7 542 6 26793 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
7 542 9 55575 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
8 542 12 67591 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
8 542 17 118340 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
9 542 20 142668 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
9 542 28 223532 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
10 542 32 265126 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
10 542 45 394892 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
11 542 53 458839 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Rh1 Kd4 Ra1
11 542 70 641866 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
12 542 79 735311 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
12 542 103 989968 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
13 542 117 1121246 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
13 542 145 1432636 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
14 542 168 1651130 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
14 542 206 2050829 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
15 542 242 2381416 Re8 Kd5 Re1 Kd4 Ra1 Kd5 Ra2 Kd4 Ra1
15 31971 334 3348711 Re2 Kc5 Rd2 Kc6 Kb2 Kb6 Rc2 Ka6 Kc3 Kb7 Kb4 Kb6 Rc5 Ka7 Ka5 Kb7 Rc3 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
15 31971 340 3420766 Re2 Kc5 Rd2 Kc6 Kb2 Kb6 Rc2 Ka6 Kc3 Kb7 Kb4 Kb6 Rc5 Ka7 Ka5 Kb7 Rc3 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
16 31973 357 3594516 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
16 31973 437 4419794 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
17 31973 451 4556301 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
17 31973 557 5691304 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
18 31973 579 5914860 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
18 31973 725 7490560 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
19 31973 756 7807922 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Kb4 Kb6 Ka4 Ka7 Kb5 Kb7 Ka5 Ka7 Rb3 Ka8 Kb6 Kb8 Rc3 Ka8 Rc8#
19 31973 936 9758075 Re2 Kc5 Rd2 Kc4 Kb2 Kb4 Rc2 Ka5 Ka3 Kb5 Kb3 Ka5 Rc3 Kb5 Ka3 Ka6 Rb3 Ka5 Rb4 Ka6 Ka4 Ka7 Ka5 Ka8 Kb6 Kb8 Ra4 Kc8 Rd4 Kb8 Rd8#
20 31973 1021 10646326 Re2 Kc5 Rd2 Kb4 Rd4+ Kb5 Kb3 Kc5 Kc3 Kb5 Rc4 Kb6 Kb4 Kb7 Kc5
20 31975 1215 12777038 Kd2 Kc4 Rd3 Kb4 Rc3 Kb5 Kc2 Kb6 Kb3 Ka5 Kc4 Kb6 Kb4 Ka6 Kc5 Kb7 Kb5 Ka7 Rc7+ Ka8 Kc6 Kb8 Kb6 Ka8 Rc8#
20 31975 1248 13122340 Kd2 Kc4 Rd3 Kb4 Rc3 Kb5 Kc2 Kb6 Kb3 Ka5 Kc4 Kb6 Kb4 Ka6 Kc5 Kb7 Kb5 Ka7 Rc7+ Ka8 Kc6 Kb8 Kb6 Ka8 Rc8#
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 19 Feb 2007, 10:06

This is a bit worse and looks more like a bug.

You should never find a checkmate in x and then later find out it's a longer checkmate.

ie You say, there is no way for you to avoid a checkmate in 8, then in a later iteration you say that it is a longer checkmate.

That means that at the previous iteration there must have been moves that avoided the checkmate in 8.

Thinking of it, serious pruning could cause this, maybe making hashing of pruned positions questionable.

Tony
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Pradu » 19 Feb 2007, 10:26

Tony van Roon-Werten wrote:This is a bit worse and looks more like a bug.

You should never find a checkmate in x and then later find out it's a longer checkmate.

ie You say, there is no way for you to avoid a checkmate in 8, then in a later iteration you say that it is a longer checkmate.

That means that at the previous iteration there must have been moves that avoided the checkmate in 8.

Thinking of it, serious pruning could cause this, maybe making hashing of pruned positions questionable.

Tony

What are you talking about? The score always went up to mate in 13. If you are talking about the PV at ply 15, I extract PVs hash. If you are suggesting that I lied and actually did pruning... the source code to the entire program is here. Uncomment out line 71 in search.h to update bounds and comment it out to not update bounds for comparison. I'm more interested in a solution to the initial problem rather than unnecessary conflict.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 19 Feb 2007, 11:22

Pradu wrote:
Tony van Roon-Werten wrote:This is a bit worse and looks more like a bug.

You should never find a checkmate in x and then later find out it's a longer checkmate.

ie You say, there is no way for you to avoid a checkmate in 8, then in a later iteration you say that it is a longer checkmate.

That means that at the previous iteration there must have been moves that avoided the checkmate in 8.

Thinking of it, serious pruning could cause this, maybe making hashing of pruned positions questionable.

Tony

What are you talking about? The score always went up to mate in 13. If you are talking about the PV at ply 15, I extract PVs hash. If you are suggesting that I lied and actually did pruning... the source code to the entire program is here. Uncomment out line 71 in search.h to update bounds and comment it out to not update bounds for comparison. I'm more interested in a solution to the initial problem rather than unnecessary conflict.


I guess you have to make a choice here.

Either you accept you're in an international forum, with non native english speakers and people with different backgrounds/interpretations or you take everything you don't understand exactly as a personal attack.

I certainly do not wish to be spoken to in this manner.

Tony
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 19 Feb 2007, 12:53

Ok, now we've cleared this misunderstanding...


A while ago I posted some sample code here for recognizing sort of no progress scoring.

This (in combination with no hashtable cuttoffs at pv nodes) should at least be worth a try.

Unfortunately, I haven't got a clue how to search for my post.

Chees,

Tony
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 19 Feb 2007, 13:21

Hmm, we still might not be talking about the same.

What I meant: There is no problem taking a cuttoff from the hashtable, but adjusting (narrowing) alpha beta from hashtable seems a dangerous idea ( and should not give very much)

Tony
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Gerd Isenberg » 19 Feb 2007, 20:47

Pradu wrote:After some investigation I realized that the hashed score was dependent on the path to the node when taking into account 3-rep and 50-move rules and therefore the hash table entry cannot be used to return/cut-off/update bounds at the position. How does one handle the path-dependencies from 3-rep and fifty-move rule in the hash table? I'm totally stumped.

I think most ignore path dependencies while probing hash, but don't adjust bounds. One may avoid storing zero scores, or to store zero scores (or +-delta) with draft-2 (or -4). One may define a -X..0..+X value range for different draws, with abs( true eval) > X.

Move sorting is an issue as well. Delaying moves and tempo manouver versus forced moves (opposition) for the winning versus losing side.

Additionally, what about...

At nodes (likely all-leaves at depth==0, beta <= drawScore) with {opMove1,myMove1,opMove0} to this node (all three reversible), where opMove0 un-makes opMove1, one may return drawScore as well, since myMove0 == reverse(myMove1) forces a repetition?

(Conditional) stalemate detection, even in qsearch with a lonesome king left (eventually plus some blocked pawns and pinned pieces). Or is there at least one legal move?
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Handling 3-rep/50-move in hash tables

Postby mridul » 19 Feb 2007, 22:54

I was telling the exact same thing to Mark Lefler ... changing bounds, in my expiriments, has been found to be extremely unsound.


Mridul
mridul
 
Posts: 48
Joined: 09 Dec 2004, 11:34
Location: Bangalore , India

Re: Handling 3-rep/50-move in hash tables

Postby Daniel Mehrmann » 20 Feb 2007, 00:06

Hi Tony !

I fully agree here !
Updating bounds from Hashtable is to dangerous. I tested this as well, but the results was crap.

Best,
Daniel
User avatar
Daniel Mehrmann
 
Posts: 127
Joined: 02 Oct 2004, 06:10
Location: Germany

Re: Handling 3-rep/50-move in hash tables

Postby Pradu » 20 Feb 2007, 00:17

I just did some testing simulating history info in the hash table by extracting only exact/limited draft depth on the KPK position and by not updating bounds. It seems that the common approach of not updating bounds seem to work better than any sort of move history information:


Code: Select all
Exact Draft
1 159 0 1 Kc3
1 159 0 9 Kc3
2 159 0 12 Kc3 Ka1
2 159 1 26 Kc3 Ka1
3 178 1 41 Kc3 Ka1 b2+ Ka2
3 178 1 114 Kc3 Ka1 b2+ Ka2
4 181 1 151 Kc3 Ka1 b2+ Ka2 Kc2
4 181 1 253 Kc3 Ka1 b2+ Ka2 Kc2
5 159 1 397 Kc3 Ka1 Kb4 Kb2 Kc4
5 159 1 728 Kc3 Ka1 Kb4 Kb2 Kc4 Ka1 Kc3 Kb1 b2 Ka2 Kc2 Ka3 b1=Q
6 156 1 858 Kc3 Ka1 Kb4 Kb2 Kc4 Ka1 Kc3 Kb1 b2 Ka2 Kc2 Ka3 b1=Q
6 159 1 967 Kb4 Kb2 Ka4 Kb1 Ka3 Ka1
6 159 3 1296 Kb4 Kb2 Ka4 Kb1 Ka3 Ka1
7 178 3 1630 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2
7 178 3 2832 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2
8 181 3 3367 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2 Ka2 Kd1
8 181 4 5254 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2 Ka2 Kd1
9 156 4 6138 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Ka4 Kb1
9 159 4 7903 Kc3 Ka1 Kb4 Kb1 Kb5 Ka1 Ka4 Kb1 Ka5 Ka1 Ka4
9 159 6 11806 Kc3 Ka1 Kb4 Kb1 Kb5 Ka1 Kb4
10 156 6 14762 Kc3 Ka1 Kb4 Kb1 Kb5 Ka1 Kb4
10 156 7 23441 Kc3 Ka1 Kb4 Kb1 Kb5 Kb2 Ka4 Kb1 Ka5 Ka1 Ka4 Kb1
11 156 9 32153 Kc3 Ka1 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Kb5 Kb1 Kb4 Kb2
11 159 9 34688 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Kb5 Kb1 Kb4
11 159 10 40417 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Kb5 Kb1 Kb4
12 156 12 44618 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Kb5 Kb1 Kb4
12 156 15 70050 Kb4 Kb2 Ka4 Kb1 Ka5 Ka1 Kb5 Kb1 Kb4
13 156 20 81700 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kc3 Ka1 Kb4 Kb2
13 156 29 151527 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
14 0 35 169539 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
14 0 45 262708 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
15 0 70 329363 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
15 0 107 715052 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
16 0 154 840867 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
16 0 204 1317001 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
17 0 389 1806205 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4
17 0 525 3209743 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Kb5 Kb2 Ka4

No bounds updating
1 159 3 1 Kc3
1 159 3 9 Kc3
2 159 3 12 Kc3 Ka1
2 159 3 26 Kc3 Ka1
3 178 3 41 Kc3 Ka1 b2+ Ka2
3 178 3 114 Kc3 Ka1 b2+ Ka2
4 181 4 151 Kc3 Ka1 b2+ Ka2 Kc2
4 181 4 251 Kc3 Ka1 b2+ Ka2 Kc2
5 159 4 393 Kc3 Ka1 Kb4 Kb2 Kc4
5 159 4 637 Kc3 Ka1 Kb4 Kb2 Ka4 Kb1 Ka3
6 156 4 750 Kc3 Ka1 Kb4 Kb2 Ka4 Kb1 Ka3 Ka1
6 159 4 842 Kb4 Kb2 Ka4 Kb1 Ka3 Ka1
6 159 4 1046 Kb4 Kb2 Ka4 Kb1 Ka3 Ka1
7 178 4 1244 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2
7 178 6 1664 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2
8 181 6 2021 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2 Ka2 Kd1
8 181 6 2495 Kb4 Kb2 Ka4 Kb1 Ka3 Kc1 b2+ Kc2 Ka2 Kd1
9 156 6 3160 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2
9 156 7 5299 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
10 159 7 5804 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
10 159 7 6403 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
11 159 9 7168 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
11 159 9 7804 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
12 159 9 8874 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
12 159 11 9516 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
13 159 11 11221 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka4
13 159 11 11854 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Kc3 Ka1 Kb4 Kb2
14 159 12 14360 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Kb5 Ka1 Ka5 Kb1
Ka4
14 159 14 14993 Kb4 Kb2 Ka4 Kb1 Ka5 Kc1 Kb5 Kb1 Ka4 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2
15 0 15 20986 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2
15 0 18 65400 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2
16 0 20 70673 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2
16 0 21 71295 Kb4 Kb2 Ka4 Kb1 Ka5 Kb2 Kb4 Kb1 Ka3 Ka1 Kb4 Kb2


I will have to try it in more positions with lots of transpositions to make sure that not updating bounds can get rid of, or nearly get rid of path history bugs.

Thanks for your help Tony, Gerd, mridul, and Daniel. I apologize for my rudeness again Tony.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby Tony van Roon-Werten » 20 Feb 2007, 09:45

mridul wrote:I was telling the exact same thing to Mark Lefler ... changing bounds, in my expiriments, has been found to be extremely unsound.


Mridul


Yes, I remember now having this discussion with Richard a couple of years ago.

The problem with updating is the following:
You update the alpha bound with the score x. But the real score>=x
If the real score turns out to be exactly x, you will create a fail low ! ( and a research)

I suggested Richard back then, that if he insisted on updating the bounds, he should update it to x-1 (or x+1 in case of a beta bound)

It gave him a 5-10% improvement compared to updating to x, but I don't know how it compares to not updating at all.

I think my testing showed hardly a difference, but am not sure.

Tony

PS Pradu's testrun seems to confirm this. The "updating bounds version" seems to loose when the score stays constant. (Which would create a lot of researches)
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: Handling 3-rep/50-move in hash tables

Postby Mateusz Luksik » 20 Feb 2007, 10:00

Hi,
I added to Atak updating the bounds using the hash table and ...
in test WAC300 number of resolved positon increased by 5.

Mateusz.
Regards,
Mateusz.
User avatar
Mateusz Luksik
 
Posts: 19
Joined: 11 Oct 2005, 17:53
Location: Poland

Re: Handling 3-rep/50-move in hash tables

Postby Pradu » 20 Feb 2007, 11:34

Mateusz Luksik wrote:Hi,
I added to Atak updating the bounds using the hash table and ...
in test WAC300 number of resolved positon increased by 5.

Mateusz.
Yes, the speed up by updating bounds is promising. I did some tests of updating bounds with buffers and it doesn't work well:

Code: Select all
#ifdef USE_HASH
#ifdef USE_EXACT_DRAFT
if(tt_depth==depth)
#else
if(tt_depth>=depth)
#endif
{
   if(tt_score>=MATE_MIN) tt_score-=dfr;
   else if(tt_score<=-MATE_MIN) tt_score+=dfr;

   switch(tt_flag)
   {
   case HASHFLAG_EXACT:
         return tt_score;
   case HASHFLAG_LOWER_BOUND:
      {
         #ifdef UPDATE_BOUNDS
         #ifdef UPDATE_WITH_BUFFER
         tt_score-=UPDATE_WITH_BUFFER;
         #endif
         if(tt_score>alpha) alpha=tt_score;
         #endif
         break;
      }
   case HASHFLAG_UPPER_BOUND:
      {
         #ifdef UPDATE_BOUNDS
         #ifdef UPDATE_WITH_BUFFER
         tt_score+=UPDATE_WITH_BUFFER;
         #endif
         if(tt_score<beta) beta=tt_score;
         #endif
         break;
      }
   }
}
#endif //USE_HASH


Using big enough buffer solves the draw but using any buffer slows down the KRK mate in 13 by a lot. When I get the time, I'll trace the bugged 128 ply search in the drawn position a little further to perhaps get some insight on how to update bounds correctly.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby Daniel Mehrmann » 20 Feb 2007, 11:34

Mateusz Luksik wrote:Hi,
I added to Atak updating the bounds using the hash table and ...
in test WAC300 number of resolved positon increased by 5.

Mateusz.


The main problem of the most engines of today that you're searching with a null window 99,99% of your tree anyway. And in the few cases where you're using a open window you're changing the bounds with a result of a former search which might based on other conditions as your current search.

If you have path depends stuff included it might be work, otherwhise there is a high risk that you create you "dead" bound window area between original and changed bound.

I thinks since the most engines using PVS with null window after first move this stuff is to risky and just outdated. If you're using the original PVS idea or no PVS at all irt might be help you, but need a lot of testing in which cases it hurts...

Just my 2 cent :-P

Best,
Daniel
User avatar
Daniel Mehrmann
 
Posts: 127
Joined: 02 Oct 2004, 06:10
Location: Germany

Re: Handling 3-rep/50-move in hash tables

Postby Daniel Mehrmann » 20 Feb 2007, 11:42

Code: Select all
#ifdef USE_HASH
#ifdef USE_EXACT_DRAFT
if(tt_depth==depth)
#else
if(tt_depth>=depth)
#endif
{
   if(tt_score>=MATE_MIN) tt_score-=dfr;
   else if(tt_score<=-MATE_MIN) tt_score+=dfr;

   switch(tt_flag)
   {
   case HASHFLAG_EXACT:
         return tt_score;
   case HASHFLAG_LOWER_BOUND:
      {
         #ifdef UPDATE_BOUNDS
         #ifdef UPDATE_WITH_BUFFER
         tt_score-=UPDATE_WITH_BUFFER;
         #endif
         if(tt_score>alpha) alpha=tt_score;
         #endif
         break;
      }
   case HASHFLAG_UPPER_BOUND:
      {
         #ifdef UPDATE_BOUNDS
         #ifdef UPDATE_WITH_BUFFER
         tt_score+=UPDATE_WITH_BUFFER;
         #endif
         if(tt_score<beta) beta=tt_score;
         #endif
         break;
      }
   }
}
#endif //USE_HASH


btw I think you're setting up the wrong scores to alpha/beta.
If you do an update from your hashtable, be sure that search has a chance getting into the new window....

Best,
Daniel
User avatar
Daniel Mehrmann
 
Posts: 127
Joined: 02 Oct 2004, 06:10
Location: Germany

Re: Handling 3-rep/50-move in hash tables

Postby H.G.Muller » 20 Feb 2007, 12:34

I try to avoid any path dependence in the hash table completely, and I think I finally succeeded in finding a very simple way to do this:

For positions that have occurred in the game already twice, scoring them as a draw does not introduce path dependency, as the really are draws irrespective of path, the first time you encounter them in the tree.

If their scoring as a draw is dependent on an earlier occurence in the tree, though (i.e. they occur 0 or 1 time in the game), you have to be careful. What I do then is forbid hash probing of the second occurence and score the third occurrence in the tree as a draw.

So in particular there cannot be pruning based on the hashed score on a second occurrence, as the hash score was supposed to be a 'repetition-free' score, and thus not applicable to a state that is repeated. The search goes on beyond the second repetition (i.e. if the second occurrence was a leaf node, it receives evaluation if there are no better captures, etc.) There it will typically encounter only hash hits to positions that were already searched at much larger depth, from the first occurrence. Only the first move on the path between first and second occurrence will not be pruned by hash hits, as it is also a repetition.

This will remain true for larger depth: after reaching the second tree occurrence, the search can only retrace the path between first and second occurence, until it reaches the third occurrence. Every deviation will result in a hash hit with sufficient depth. The stored score of these positions will tell the search if it should continue to follow the path to the third occurrence, or if it is better to break the repetiton cycle.

Whatever it decides, the score of the second repetition will eventually be based on this. If either side finds it better to deviate, based on a hashed score, it will do so. If it is best for both to return to the position, it is a draw. Since all nodes on the path between second and third occurrence are (second) repetitions, their minimax score will not be stored in the hash (just as they were not probed either). Their earlier occurences on the path would overwrite such a hash anyway.

If the second occurrence receives the score, (draw or otherwise), this score is not hashed (the position being a repetition). But even if it is a draw, it is now not a path-dependent draw score, because it was based on the fact that this position was repeated later in the tree, not earlier. So if this score starts to propagate towards the root, it will not contaminate the positions below it (which are hashed) with path-dependence, even if it remains on the PV. So no path-dependent scores will ever be stored in the hash.

In summary:
* Do not allow pruning of tree-repetitions by hash hits
* Score positions that occurred twice in game or twice in tree before as draws (but not once game + once tree!).

The only disadvantage of this algorithm is that you need quite large search depth to recognize draws. If that bothers you, you can extend the search of a tree repetition by one ply. All moves lead to positons that were (or have to be) searched at least 4 ply deeper than the currently requested depth anyway, so even with extension the hash will satisfy the request. Only the move on the repetition path will thus be searched with this extension, and from there the next move on the repetition path, with its own extension. And so on, until the search has extended itself to the third occurrence, or saw a profitable point to break the repetition cycle before reaching that occurrence (by immediate hash hits).

I am not sure if such extensions are worth it. At least, before you are pretty sure that you don't want to deviate already before reaching the second occurence. So you might want to award such repetition extensions only if the remaining depth is at least 1 or two in the second occurence. If you do it at d=0, you might do a lot of such 'repetition verifications' on moves that lead to a repetition and happened to be sorted in front, before an alternative that could have been judged to be better without such a repetition verification, cutting the repetition move from the tree. An alternative would be to sort repetition moves (for the leading side) with the bad captures in the back.
User avatar
H.G.Muller
 
Posts: 3179
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Handling 3-rep/50-move in hash tables

Postby Pradu » 20 Feb 2007, 13:33

H.G.Muller wrote:I try to avoid any path dependence in the hash table completely, and I think I finally succeeded in finding a very simple way to do this:

For positions that have occurred in the game already twice, scoring them as a draw does not introduce path dependency, as the really are draws irrespective of path, the first time you encounter them in the tree.

Although the same position cannot occur twice, the move history is different for each and therefore the drawing moves and the depths are different. Eg, you do a 7 ply search and it is not a draw, but under a differenet move history, it is a draw for 3 ply search depth. When you reach the node and tt_depth>=depth, it will be assumed as not draw because the hash entry of depth 7 says it is not a draw, which is incorrect. For some reason I have a hunch there is more to updating bounds than just path history because path history bugs remain whether you update bounds or not.

If their scoring as a draw is dependent on an earlier occurence in the tree, though (i.e. they occur 0 or 1 time in the game), you have to be careful. What I do then is forbid hash probing of the second occurence and score the third occurrence in the tree as a draw.

So in particular there cannot be pruning based on the hashed score on a second occurrence, as the hash score was supposed to be a 'repetition-free' score, and thus not applicable to a state that is repeated. The search goes on beyond the second repetition (i.e. if the second occurrence was a leaf node, it receives evaluation if there are no better captures, etc.) There it will typically encounter only hash hits to positions that were already searched at much larger depth, from the first occurrence. Only the first move on the path between first and second occurrence will not be pruned by hash hits, as it is also a repetition.

This will remain true for larger depth: after reaching the second tree occurrence, the search can only retrace the path between first and second occurence, until it reaches the third occurrence. Every deviation will result in a hash hit with sufficient depth. The stored score of these positions will tell the search if it should continue to follow the path to the third occurrence, or if it is better to break the repetiton cycle.

Whatever it decides, the score of the second repetition will eventually be based on this. If either side finds it better to deviate, based on a hashed score, it will do so. If it is best for both to return to the position, it is a draw. Since all nodes on the path between second and third occurrence are (second) repetitions, their minimax score will not be stored in the hash (just as they were not probed either). Their earlier occurences on the path would overwrite such a hash anyway.

If the second occurrence receives the score, (draw or otherwise), this score is not hashed (the position being a repetition). But even if it is a draw, it is now not a path-dependent draw score, because it was based on the fact that this position was repeated later in the tree, not earlier. So if this score starts to propagate towards the root, it will not contaminate the positions below it (which are hashed) with path-dependence, even if it remains on the PV. So no path-dependent scores will ever be stored in the hash.

In summary:
* Do not allow pruning of tree-repetitions by hash hits
* Score positions that occurred twice in game or twice in tree before as draws (but not once game + once tree!).

The only disadvantage of this algorithm is that you need quite large search depth to recognize draws. If that bothers you, you can extend the search of a tree repetition by one ply. All moves lead to positons that were (or have to be) searched at least 4 ply deeper than the currently requested depth anyway, so even with extension the hash will satisfy the request. Only the move on the repetition path will thus be searched with this extension, and from there the next move on the repetition path, with its own extension. And so on, until the search has extended itself to the third occurrence, or saw a profitable point to break the repetition cycle before reaching that occurrence (by immediate hash hits).

I am not sure if such extensions are worth it. At least, before you are pretty sure that you don't want to deviate already before reaching the second occurence. So you might want to award such repetition extensions only if the remaining depth is at least 1 or two in the second occurence. If you do it at d=0, you might do a lot of such 'repetition verifications' on moves that lead to a repetition and happened to be sorted in front, before an alternative that could have been judged to be better without such a repetition verification, cutting the repetition move from the tree. An alternative would be to sort repetition moves (for the leading side) with the bad captures in the back.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: Handling 3-rep/50-move in hash tables

Postby H.G.Muller » 20 Feb 2007, 14:19

Pradu wrote:Although the same position cannot occur twice, the move history is different for each and therefore the drawing moves and the depths are different. Eg, you do a 7 ply search and it is not a draw, but under a differenet move history, it is a draw for 3 ply search depth. When you reach the node and tt_depth>=depth, it will be assumed as not draw because the hash entry of depth 7 says it is not a draw, which is incorrect. For some reason I have a hunch there is more to updating bounds than just path history because path history bugs remain whether you update bounds or not.

I am not sure we are communicating. Both in the 7 -ply search as in the 3-ply search, (and in fact in any search) the position will be a draw, because it already occured twice in the game.
User avatar
H.G.Muller
 
Posts: 3179
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Next

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 3 guests