Winboard Forum

by **Reinhard Scharnagl** » 07 Dec 2004, 10:11

Hi all,

because Uri Blass remembered me to publish some thoughts on caching I will try to start a serious dicussion on that again. But because of it would not make much sense to only philosophically talk about different ideas around that theme it seems to be good to have an objectivating test scenario to proof ideas and stategies.

It has always been said that hash collisions would be generated only rarely and therefore simply could be ignored. This is a very bad idea if wanting to test, whether more or less collisions will happen depending on different key creating strategies.

Additionally different replacement schemes could be compared very badly, because of mostly being embedded in different search tree pruning ideas etc..

Both aspects could be objectivly tested when using an approach to calculate perft values storing position results into the cache using the program typical key generating and replacement scheme. If there would be hash collisions the results would differ especially in higher plys. If the replacement scheme would have a good quality, the speed of generating results would be high.

I have posted such Smirf results several times, but never ever seen comparable figures. May be that could be changed if you are interested in comparing your caching to mine.

Reinhard.

Code: Select all: FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][k][b][n][r]| (Compilation: Nov 24 2004) 7 |[p][p][p][p][p][p][p][p]| 6 | ::: ::: ::: :::| Perft Testseries 5 |::: ::: ::: ::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: ::: :::| TT Access Success 48.3% 3 |::: ::: ::: ::: | 2 || Smirf Test No.: 00 1 |<R><N><Q><K><N><R>| =>+-*--b--c--d--*--f--g--*-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 20 0 0 0 0 2 400 0 0 0 0 3 8902 34 12 0 0 4 197281 1576 469 0 0 5 4865609 82719 27351 0 0.1 6 119060324 2812008 809099 0 1.3 7 3195901860 108329926 33103848 883453 16.1 8 84998978956 3523740106 968981593 23605205 226.1 ---------------------------------------------------------------------------- FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]::: :::[k]::: [r]| (Compilation: Nov 24 2004) 7 |[p] [p][p][q][p][b] | 6 |[b][n] :::[p][n][p]:::| Perft Testseries 5 |::: :::<N> ::: | (With TT Caching 256.0 MB / 4-fold) 4 | [p] :::::: :::| TT Access Success 50.7% 3 |::: <N> :::<Q>:::[p]| 2 || Smirf Test No.: 01 1 |<R> ::: <K> :::<R>| =>+-*--b--c--d--*--f--g--*-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 48 8 0 2 0 2 2039 351 3 91 0 3 97862 17102 993 3162 0 4 4085603 757163 25523 128013 0.1 5 193690690 35043416 3309887 4993637 3.2 6 8031647685 1558445089 92238050 184513607 75.8 ---------------------------------------------------------------------------- FEN: 8/PPP4k/8/8/8/8/4Kppp/8 w - - 0 1 +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| (Compilation: Nov 24 2004) 7 | ::: :::[k]| 6 | ::: ::: ::: :::| Perft Testseries 5 |::: ::: ::: ::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: ::: :::| TT Access Success 61.2% 3 |::: ::: ::: ::: | 2 | ::: :::<K>[p][p][p]| Smirf Test No.: 02 1 |::: ::: ::: ::: | =>+-a--b--c--d--e--f--g--h-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 18 1 0 0 0 2 290 0 52 0 0 3 5044 144 310 0 0 4 89363 194 15360 0 0 5 1745545 46745 161249 0 0.1 6 34336777 406616 6021556 0 0.5 7 749660761 22632801 87618216 0 5.2 8 16303466487 337063298 2990354989 0 47.9 ---------------------------------------------------------------------------- FEN: 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1 +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| (Compilation: Nov 24 2004) 7 |::: [p] ::: ::: | 6 | ::: [p] ::: :::| Perft Testseries 5 |<K>::: ::: :::[r]| (With TT Caching 256.0 MB / 4-fold) 4 | <R> ::: [p] [k]| TT Access Success 69.7% 3 |::: ::: ::: ::: | 2 | ::: :::::::::| Smirf Test No.: 03 1 |::: ::: ::: ::: | =>+-a--b--c--d--e--f--g--h-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 14 1 2 0 0 2 191 14 10 0 0 3 2812 209 267 0 0 4 43238 3348 1680 0 0 5 674624 52051 52950 0 0 6 11030083 940350 452473 0 0.2 7 178633661 14519036 12797406 0 1.2 8 3009794393 267586558 135626805 0 7.5 9 50086749815 4208748290 3440345177 0 42.6 ---------------------------------------------------------------------------- FEN: 8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - - 1 67 =>+-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| (Compilation: Nov 24 2004) 7 |::: :::<K>::: ::: | 6 | :::[p]::: ::: :::| Perft Testseries 5 |[p] :::[b]::: [r] | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: [k] :::| TT Access Success 74.2% 3 |::: ::: ::: ::: | 2 | ::: ::: ::: :::| Smirf Test No.: 04 1 |:::[q]::: ::: ::: | +-a--b--c--d--e--f--g--h-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 50 0 5 0 0 2 279 7 0 0 0 3 13310 0 1465 0 0 4 54703 1417 0 0 0 5 2538084 0 303975 0 0 6 10809689 391329 0 0 0.2 7 493407574 0 58927342 0 0.8 8 2074492344 76527631 0 0 4.2 9 93718646102 0 11464464778 0 11.5 0 397773803207 15954546937 0 0 55.3 ---------------------------------------------------------------------------- FEN: 8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28 =>+-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10 8 | ::: ::: ::: :::| (Compilation: Nov 24 2004) 7 |::: ::: ::: :::[p]| 6 |[p]::: ::: :::[p][b]| Perft Testseries 5 |::: ::: [k] ::: | (With TT Caching 256.0 MB / 4-fold) 4 |:::[p][n]::: :::| TT Access Success 55.9% 3 |::: ::: * ::: ::: | 2 |::: ::: :::| Smirf Test No.: 05 1 |:::[r] :::<R><K> | +-a--b--c--d--e--f--g--h-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 5 2 0 0 0 2 117 5 12 0 0 3 3293 269 148 0 0 4 67197 4279 6019 0 0 5 1881089 151494 99957 0 0.1 6 38633283 2758216 3357855 0 0.8 7 1069189070 85602380 58008914 0 8.8 8 22488501780 1700604632 1927497345 0 90.5 ---------------------------------------------------------------------------- FEN: rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][k][b] [r]| (Compilation: Nov 24 2004) 7 |[p][p][p][p][p] [p][p]| 6 | ::: ::: :*: [n]| Perft Testseries 5 |::: ::: [p]::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: ::: :::| TT Access Success 51.4% 3 |::: ::: ::: ::: | 2 | | Smirf Test No.: 06 1 |<R><N><Q><K><N><R>| =>+-*--b--c--d--*--f--g--*-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 31 1 1 0 0 2 570 9 0 0 0 3 17546 411 598 0 0 4 351806 13979 704 0 0 5 11139762 460500 391791 8622 0.2 6 244063299 14386441 1831869 181851 3.0 7 7930902498 458901248 289376682 12288205 36.7 ---------------------------------------------------------------------------- FEN: rnbqckabnr/pppppppppp/0/0/0/0/PPPPPPPPPP/RNBQCKABNR w KQkq - 0 1 +-*--b--c--d--e--*--g--h--i--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][c][k][a][b][n][r]| (Compilation: Nov 24 2004) 7 |[p][p][p][p][p][p][p][p][p][p]| 6 | ::: ::: ::: ::: :::| Perft Testseries 5 |::: ::: ::: ::: ::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: ::: ::: :::| TT Access Success 53.4% 3 |::: ::: ::: ::: ::: | 2 || Smirf Test No.: 07 1 |<R><N><Q><C><K><A><N><R>| =>+-*--b--c--d--e--*--g--h--i--*-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 28 0 0 0 0 2 784 0 0 0 0 3 25283 387 120 0 0 4 808984 14812 4019 0 0 5 28946187 907953 304360 0 0.5 6 1025229212 36740962 11052055 0 8.7 7 39532257395 1838308392 621202264 120 149.8 ---------------------------------------------------------------------------- FEN: r1b1c2rk1/p4a1ppp/1ppq2pn2/3p1p4/3A1Pn3/1PN3PN2/P1PQP1BPPP/3RC2RK1 w - - 0 15 +-a--b--c--d--e--f--g--h--i--j-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]:::[b]:::[c]::: [r][k]:::| (Compilation: Nov 24 2004) 7 |[p] ::: :::[a]:::[p][p][p]| 6 | [p][p][q] :::[p][n] :::| Perft Testseries 5 |::: :::[p]:::[p]::: ::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: <A> [n]::: :::| TT Access Success 43.3% 3 |:::<N> ::: <N>::: | 2 |:::<Q>:::| Smirf Test No.: 08 1 |::: :::<R><C> :::<R><K> | =>+-a--b--c--d--e--f--g--h--i--j-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 50 6 1 0 0 2 2801 191 2 0 0 3 143032 18799 2215 0 0 4 7917813 680548 45116 0 0.2 5 412224167 56838308 5549854 0 5.2 6 22846373778 2289332857 218647805 0 163.4 ---------------------------------------------------------------------------- FEN: r1b2k2nr/p1ppq1ppbp/n1Pcpa2p1/5p4/5P4/1p1PBCPN2/PP1QP1BPPP/RN3KA2R w KQkq - 6 12 +-*--b--c--d--e--*--g--h--i--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r]:::[b]::: [k] :::[n][r]| (Compilation: Nov 24 2004) 7 |[p] [p][p][q] [p][p][b][p]| 6 |[n]:::[c][p][a] :::[p]:::| Perft Testseries 5 |::: ::: :::[p]::: ::: | (With TT Caching 256.0 MB / 4-fold) 4 | ::: ::: ::: :::| TT Access Success 48.6% 3 |:::[p]:::<C><N>::: | 2 | <Q>:::| Smirf Test No.: 09 1 |<R><N>::: :::<K><A> :::<R>| =>+-*--b--c--d--e--*--g--h--i--*-+ Break Time 32.0 Sec. Ply Nodes all (x) all (+) Castl. Sec. ---------------------------------------------------------------------------- 1 41 3 0 0 0 2 2107 292 5 0 0 3 93962 9434 1258 146 0 4 4869569 732934 71559 5375 0.1 5 228645312 27763729 5362814 538292 3.5 6 11962047524 1912281008 278541908 21162954 99.9 ----------------------------------------------------------------------------

by **Brian Richardson** » 07 Dec 2004, 18:12

While I always look for your posts, and I think the formatted data you provide looks neat, I must confess I have no idea what the data is all about. You may have posted a legend for your format some time ago, but perhaps you could do so again. What does TT Access Success 48.3%
really mean?

Most engines do not use any hashing with the perft command, AFAIK, so I'm not clear on how you added it. Also, do the times you list include evaluation (assuming no), nor alpha/beta, since that would miss the point of perft valid move counting, I suppose.

I have experimented with several hashing methods in Tinker. Believe it or not, single entry depth-preferred seems to work best, in addition to a separate pawn hash. I have tried two level (depth and always replace), and separate q-search hashing, and all seem slower.

The older papers on hashing that showed 2 level better I think are more a result of much smaller tables back then. Once you get beyond about 1 million entries, I don't think it matters all that much.

Also, I recall Hyatt mentioning some hashing tests where "errors" in the tables did not seem to impact the search results much at all, somewhat surprisingly.

by **Reinhard Scharnagl** » 07 Dec 2004, 18:29

Hi Brian,

What does TT Access Success 48.3% ...

the meaning of that is, that from all trials to read position related data from the cache has been 48.3% successful.

Most engines do not use any hashing with the Perft command, AFAIK, so I'm not clear on how you added it

In this case the goal is to test the performance of caching itself, whether the replacement scheme could be optimized, and whether hash collisions would happen. (For the last point the results have to be compared with some others calculated with a more conventional uncached but therefore slower Perft).

The older papers on hashing that showed ...

I do not rely on old papers, so I cannot judge on that. I probably have a very different replacement scheme. But that does not make it impossible to compare its efficiency, e.g. using such a test as I have provided.

"errors" in the tables

Concerning Perft results such errors are relevant. Concerning a search tree analyse it seems to be a philosophical point of view to handle that problem by declaring it for irrelevant.

Reinhard.

by **Brian Richardson** » 07 Dec 2004, 18:41

Lets back up a bit.

How do you use hashing with perft?
My perft just generates all moves and makes them one at a time and does this recursively.

When do you store and when do you probe?
I don't see how this would impact the speed of perft, other than to slow things down.

Is your definition of a collision a duplicate hash table index (subset of full key) or the full hash key (typically 64 bits)?

Thanks,
Brian

by **Uri Blass** » 07 Dec 2004, 18:53

Hi Brian,I never thought much about storing perft in the hash inspite of understanding that it is possible but I will start to think about it now that is first step before programming it and I decided to share my thoughts here.

The idea of using hash for perft is clear because perft is sum of perfts.

The problem is that in order to do it I need first before storing the information in the hash to get the relevant numbers that are candidates to store.

Let take an example.

opening position in chess.

perft 4 is perft3(a3)+...
perft3(a3) is perft3(a3 a6)+...
perft1(a3 a6 b3)+ and perft1(a3 a6 b3) is calculated and stored in the hash.

basically when you calculate perft(n) every time after making a move at ply i you can store in some
array totalnodes[i] and after you undo ply i you can get the value of
perft(n-i) by substracting and store it in the hash table.

It means that if you get in the future the same position again you can save calculation of perft and simply add perft(n-i).

You can expect to get in the future the same position again because a3 a6 b3 is the same as b3 a6 a3.

I think that from this point I can start to write some code and later continue to think from the code what to write in the hash.

Uri

by **Uri Blass** » 07 Dec 2004, 19:18

To be more correct you store information before undoing a move and get the information on perft to store based on the difference between the total number of nodes before undoing a move and the total number of nodes after making a move.

I have 2 options:
1)To use the code that I have for perft that is not recursive and add somethings for it to calculate perft with hash.

2)To use recursive code for perft that is probably more simple so I hope I will have less bugs if I generalize that code to use hash and I do not have to substract in order to calculate perft of smaller numbers.

I guess that I will use option 2 so I will rewrite my perft function.

Uri

by **Brian Richardson** » 07 Dec 2004, 20:35

Ahhh, no, I don't think so.

Perft is not about the total number of positions, but moves,
so a3,a6,b3 is not the same as b3,a6,a3 for perft purposes.

Most perft's simply walk the entire move tree counting each move
made, not each position reached.

by **Dann Corbit** » 07 Dec 2004, 20:50

Brian Richardson wrote:Ahhh, no, I don't think so.

Perft is not about the total number of positions, but moves,
so a3,a6,b3 is not the same as b3,a6,a3 for perft purposes.

Most perft's simply walk the entire move tree counting each move
made, not each position reached.

The order of move generation is irrelevant. We only need a count.
So if I visit a node I have counted before, there is no need to generate and count again.

The network project used to count nodes used this idea.

by **Uri Blass** » 07 Dec 2004, 20:51

Hi Brian,

I will try to explain better.
perft 5 in the opening position is the number of possible games of 5 plies.

You can divide these games based on the first 3 plies.

The number of games of 5 plies that begin with 1.a3 a6 2.b3 is the same as the number of games of 5 plies that begin with 1.b3 a6 2.a3.

The idea is that there is no reason to calculate the same number twice and it is possible to save the number of games that begin with 1.a3 a6 2.b3 in the hash and when you get the position after 1.b3 a6 2.a3 you simply add this number.

Uri

by **Uri Blass** » 07 Dec 2004, 21:12

Here is the code that I have so far for perft with hash(I still did not write some functions about hash and I will probably think about it later)

I do not think that it is the best use of hash tables for perft but I think that it is a start of productive use for perft.

You can see that hash functions are still empty at this moment.

void recordhash(BitBoard result,int depth)
{
}
int probehash(int depth)
{
/*return 0 in case of no hash and 1 in case that perft(depth is stored in the hash*/;
}
BitBoard getvalue(int depth)
{
/* should return perftvalue*/;
}
BitBoard perftahash(int depth)
{
int i;
BitBoard result=0;
if (probehash(depth))
return getvalue(depth);
if (depth==1)
{
gen();
result=first_move[ply+1]-first_move[ply];
recordhash(result,1);
return result;
}
gen();
for (i=first_move[ply];i<first_move[ply+1];i++)
{
makemove(gen_dat[i].m);
result+=perftahash(depth-1);
undomove();
}
recordhash(result,depth);
return result;
}

Uri

by **Reinhard Scharnagl** » 07 Dec 2004, 21:34

Hi Brian,

Is your definition of a collision a duplicate hash table index (subset of full key) or the full hash key (typically 64 bits)?

my position identification consists of two 32 bit numbers. One is generated to compute the storing address, the other combined with the unused part of the first is stored within the cached data as a verification key. Thus the total length of my position identification is 64 bit.

If you are not storing additional information e.g. a FEN string or an extended 96 bit key you will not be able to detect a hash collision (the 64 bit keys are identical but the position is not). But in the testing scenario I have descripted the Perft sum will then contain errors. This errors could be detected by comparing Perft results to those generated conventionally or by a complete different program.

When do you store and when do you probe?

When in normal Perft you would expand a node it would here be recommended to check the cache whether those situation already has been calculated. But be aware that following problem exists:

A position may because of move repetition occur at different levels within the same cache. Thus data from different levels for the same position has to be stored using different hash keys. The hash key therefore has to be overlayed by an additional xored level-key. Ommitting this procedure will lead to very different perft results which not have been caused by hash collisions.

Reinhard.

by **Reinhard Scharnagl** » 07 Dec 2004, 22:01

Hi all interested,

you will have noticed that Smirf's cached Perft is not counting only moves, but also captures, checks and castlings. For that it uses four short counters (16 bit). If you use only one counter (e.g. 64 bit for moves) you probably would be faster than Smirf. But if you would use counters shorter than 64 bit like I do, be aware that following problem would exist: if the local perft sum exceeds that storing length, you will not be able to store that result within the cache at all, even when remaining counters still would have sufficient length.

Reinhard.

by **milix** » 07 Dec 2004, 23:31

Hi!
What is the point of cashing perft? I thought perft was for
1. measuring move generator's speed and
2. find bugs in movegen+make/unmake moves.
Cashing is 'cheating' in 1 and hides possible bugs in 2.

by **Reinhard Scharnagl** » 07 Dec 2004, 23:48

Hi milix,

you obviously misunderstand my intentions. This here is not to push up Perft results - would I else have added some new counters? It is done for to test the purposes matching the thread title.

Measuring a move generator's speed is not the main goal of Perft but to verify the generators correctness and to direct the view to special positions if differences to verified numbers would happen. Thus my additional counters will be supplied.

How a cached Perft should hide possible bugs in the move generator should be commented, because I cannot see this.

Reinhard.

P.S.: for those who are interested in "uncheated" figures:

Code: Select all: FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10 8 |[r][n][b][q][k][b][n][r]| (Compilation: Nov 7 2004) 7 |[p][p][p][p][p][p][p][p]| 6 | ::: ::: ::: :::| Perft Testseries 5 |::: ::: ::: ::: | 4 | ::: ::: ::: :::| (without caching) 3 |::: ::: ::: ::: | 2 || Smirf Test No.: 00 1 |<R><N><Q><K><N><R>| =>+-*--b--c--d--*--f--g--*-+ Break Time 250.0 Sec. Ply Nodes all (x) (e.p.) all (+) all (++) Promot. Castl. Sec. ------------------------------------------------------------------------------- 1 20 0 0 0 0 0 0 0 2 400 0 0 0 0 0 0 0 3 8902 34 0 12 0 0 0 0 4 197281 1576 0 469 0 0 0 0 5 4865609 82719 258 27351 0 0 0 0.2 6 119060324 2812008 5248 809099 46 0 0 4.5 7 3195901860 108329926 319617 33103848 1628 0 883453 116 8 84998978956 3523740106 7187977 968981593 147215 0 23605205 3116 -------------------------------------------------------------------------------

by **Uri Blass** » 08 Dec 2004, 09:41

milix wrote:Hi!
What is the point of cashing perft? I thought perft was for
1. measuring move generator's speed and
2. find bugs in movegen+make/unmake moves.
Cashing is 'cheating' in 1 and hides possible bugs in 2.

Cashing is not cheating because the purpose of cashing is not to test speed of move generator.

Cashing cannot hide bugs in move generator and make unmake moves because all the idea is to compare between results with cashing and results without cashing and find that they are the same.

In theory it is possible to get correct result with cashing and not correct results without cashing if you have bugs that happens only after many make and unmake moves but in any case if the results are not the same it suggest that your hash numbers are not good or that you have another bug and I do not see how having more information can hide bugs.

Uri

by **Reinhard Scharnagl** » 08 Dec 2004, 09:57

Hi Uri,

In theory it is possible to get correct result with cashing and not correct results without cashing if you have bugs that happens only after many make and unmake moves ...

I cannot understand this. Why in the situation you describe should make and unmake of moves work correctly only with caching? Caching would not be able to repair such elementary errors. Thus caching is not able to cover such a misbehaviour.

Reinhard.

by **milix** » 08 Dec 2004, 12:37

Hi Reinhard,
It is very easy for me to generate a bug in my prog (say by adding a new feature :-)

but is really difficult to generate a bug to proove something! But I will try: I remember in the early days of developing I had a bug in my move generator releated with ep-captures. The unmake move didn't restore correctly the ep-square. Suppose we have only this ep-capture in our tree and we visit this node again in a second (third etc) time for perft purposes. Without cashing, the makemove will not generate the ep-capture. With cashing, we will get the correct result because the ep-capture generated only once (but the bug still remains)...

by **Uri Blass** » 08 Dec 2004, 12:59

Hi milix,

I do not see why the program will not make the ep capture with hashing.
It may make it less times but if the program without hashing need to make ep capture then the program with hashing also needs to do it at least in the first time that it visits the relevant position.

Note that having perft with hash is a seperate function to having perft without hash and I do not see how generating more information is bad.

Uri

by **Reinhard Scharnagl** » 08 Dec 2004, 13:10

Hi milix,

well, I think I understand your intentions now, but nevertheless they are not matching in this case. I will try to make that more clear:

a) If the make and unmake funktion (or in Smirf: Move and ReMove) would not work properly, the whole tree walk will be errornous. There is no way to repair a wrong rebuilt position, neither with or without caching. Thus the cached Perft result also would be wrong, and no failure would be hidden. A cached Perft would never come back to that failing position, because your make and unmake would not rebuild it at all.

b) Generally spoken: if there would be any wrong behaviour which would be hidden by the cached Perft, that would mean, that one of your functions would have another result for a position when repeated. But without having any type of caching your routines would never been able to distinguish between a first and second occurence of a special position. Thus such a wrong behaviour could not have existed before. The conclusion is, that even such more general cases never ever could happen.

So a cached Perft is not able to hide any prior existing error only by caching positions and reusing stored calculations.

Reinhard.

by **Uri Blass** » 08 Dec 2004, 13:12

Reinhard Scharnagl wrote:Hi Uri,
In theory it is possible to get correct result with cashing and not correct results without cashing if you have bugs that happens only after many make and unmake moves ...

I cannot understand this. Why in the situation you describe should make and unmake of moves work correctly only with caching? Caching would not be able to repair such elementary errors. Thus caching is not able to cover such a misbehaviour.

Reinhard.

Hi Reinhard,
The point is that it is possible that some variables are updated not correctly during the process of making moves so the program can generate correct moves in the first time that it get position X but generate not correct moves in the second time that it gets it.
If you skip the second time you may not discover bug.

Note that I expect in this case to have errors also with caching because I cannot think of a bug that is relevant only when you go back to position that you visited but the point is that if you got correct result for perft(n) with caching you generated and made less moves so you have smaller probability that some bug will cause wrong results.

Uri

Winboard Forum

The Quality of Caching and Hash Keys

The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Re: The Quality of Caching and Hash Keys

Who is online