Author: Robert Hyatt
Date: 09:11:48 10/01/98
Go up one level in this thread
On October 01, 1998 at 10:07:45, James Robertson wrote: >On October 01, 1998 at 08:27:47, Robert Hyatt wrote: > >>On October 01, 1998 at 03:18:58, Bruce Moreland wrote: >> >>> >>>On October 01, 1998 at 00:25:44, James Robertson wrote: >>> >>>>How do programs detect draws by repetition in a search? I can think of many >>>>possible ways, but they all seem really slow. How do most programs quickly >>>>detect draws by repetition? >>> >>>You have a hash key. You have a transposition table. >>> >>>1) You can set a flag in your transposition table when you enter a node, and >>>clear it when you leave the node. If you encounter a flag that's already set, >>>it's a rep draw. You have to be careful not to kill your hash entry somehow, >>>there is tremendous potential for bugs. >>> >>>2) You can make a new hash table, a small one, and store the hash key in that >>>when you enter a node, and clear it when you leave. >>> >>>3) You can create a list of hash keys that represent positions that have >>>occurred between now and between the capture or pawn move, and iterate. This >>>isn't as slow as it sounds, for reasons that I don't understand, but it may get >>>really bad in some pathological cases such as when you are near a 50-move draw. >>> >>>You have to be careful to take into account the en-passant square and the >>>castling flags in some circumstances. >>> >>>Without castling and en-passant, chess would be a lot simpler to program. >>> >>>You will get bugs no matter what you do. >>> >>>bruce >> >> >> >>I did this in an early version of Cray Blitz, but it has one *huge* problem >>when you go to a parallel search. Such a table of "active" positions >>becomes useless when you have multiple threads that can reach these >>positions independently of each other, so that suddenly you can't tell >>what has actually been seen before in reality and what has only been seen >>once before by a different processor. >> >>I had to toss this out when Cray Blitz went parallel in 1983, and have >>used a simple "list" of repeated positions ever since... > >Yeah..... this sounds terribly slow, but it seems really a lot eaisier to >program. How much of the search time does it take to do this repetition search >if you have a list? > >James The code that does this is RepetitionCheck() in crafty... here is a recent profile made over several consecutive moves in a game: % cumulative self self total time seconds seconds calls ms/call ms/call name 16.49 47.87 47.87 17150992 0.00 0.00 Evaluate 7.46 69.52 21.65 15753832 0.00 0.00 MakeMove 6.11 87.25 17.73 5589902 0.00 0.00 GenerateCaptures 5.78 104.02 16.77 3071 5.46 72.60 Search 5.25 119.26 15.24 AttacksRookFunc 5.13 134.15 14.89 FirstOne 4.90 148.37 14.22 15753802 0.00 0.00 UnMakeMove 4.61 161.74 13.37 AttacksBishopFunc 4.48 174.76 13.02 5502491 0.00 0.00 EvaluatePawns 4.17 186.86 12.10 17150992 0.00 0.00 EvaluateKingSafety 4.08 198.71 11.85 9118140 0.00 0.00 Swap 3.65 209.32 10.61 11957708 0.00 0.00 NextMove 3.53 219.57 10.25 11128825 0.00 0.01 Quiesce 3.41 229.47 9.90 8933056 0.00 0.00 EvaluateDevelopment 2.88 237.84 8.37 25848292 0.00 0.00 Attacked 2.29 244.48 6.64 PopCnt 2.14 250.68 6.20 LastOne 1.71 255.63 4.95 10568769 0.00 0.00 AttacksTo 1.47 259.89 4.26 14203212 0.00 0.00 SwapXray 1.41 263.97 4.08 2318394 0.00 0.00 LookUp 1.23 267.53 3.56 359481 0.01 0.01 GenerateNonCaptures 1.05 270.59 3.06 437455 0.01 0.01 GenerateCheckEvasions 0.96 273.39 2.80 MobilityDiaga1Func 0.90 276.00 2.61 MobilityDiagh1Func 0.89 278.58 2.58 25 103.20 103.20 InitializeHashTables 0.80 280.90 2.32 1769200 0.00 0.00 StoreRefutation 0.44 282.18 1.28 2320397 0.00 0.00 RepetitionCheck based on that, .44% of the time (less than 1/2 of one percent) of the total search time is spent there... not enough to worry about...
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.