Author: Roberto Waldteufel
Date: 04:28:46 10/04/98
Go up one level in this thread
On October 03, 1998 at 22:07:23, Robert Hyatt wrote: >On October 03, 1998 at 19:09:59, Roberto Waldteufel wrote: > >> >>On October 02, 1998 at 22:10:29, Robert Hyatt wrote: >> >>>On October 02, 1998 at 21:22:34, John Coffey wrote: >>> >>>>On October 02, 1998 at 20:47:47, Robert Hyatt wrote: >>>> >>>>>On October 02, 1998 at 19:35:26, blass uri wrote: >>>>> >>>>>> >>>>>>On October 02, 1998 at 18:39:04, Robert Hyatt wrote: >>>>>> >>>>>>>On October 02, 1998 at 15:06:17, blass uri wrote: >>>>>>> >>>>>>>> >>>>>>>>On October 02, 1998 at 13:12:02, Robert Hyatt wrote: >>>>>>>> >>>>>>>> >>>>>>>>>>I understand that tablebases provide -MatNN,+MAtNN and draw scores >>>>>>>>>>but I do not understand how can you go to positions that you use tablebases >>>>>>>>>>at depth 12 from the initial position because tablebases are for KPP against K >>>>>>>>>>or KP against KP and not for positions with more pieces. >>>>>>>>>>You need to calculate more than 16 plies to go to positions that you can >>>>>>>>>>use tablebases if you do not do special extensions in pawn endings. >>>>>>>>>> >>>>>>>>>>I thought that If you can see by tablebases that the position is -MatNN because >>>>>>>>>>it is KPP against K then you can see without tablebases that the position is not >>>>>>>>>>-0.xx because the static evaluation function without tablebases is not -0.xx >>>>>>>>>> >>>>>>>>>>Uri >>>>>>>>> >>>>>>>>> >>>>>>>>>You are misunderstanding how I use them. Imagine a position with KBN vs K. >>>>>>>>>You understand that in that position, crafty will play perfectly, and will win >>>>>>>>>with the KBN side, correct? >>>>>>>>> >>>>>>>>>IE in this position: >>>>>>>>> >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 8 | *K| | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 7 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 6 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 5 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 4 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 3 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 2 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 1 | K | B | N | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> a b c d e f g h >>>>>>>>> >>>>>>>>>crafty promptly says Kb2 Mat25... ok so far... >>>>>>>>> >>>>>>>>>now lets modify the position to this: >>>>>>>>> >>>>>>>>> >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 8 | *K| *R| *Q| | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 7 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 6 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 5 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 4 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 3 | | R | | | | | B | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 2 | | | | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> 1 | K | B | N | | | | | | >>>>>>>>> +---+---+---+---+---+---+---+---+ >>>>>>>>> a b c d e f g h >>>>>>>>> >>>>>>>>> >>>>>>>>>In this position. crafty says Be4+ Mat34, with a 2 second search. How did >>>>>>>>>it do that? like this: >>>>>>>>> >>>>>>>>> 8 2.03 Mat34 1. Be4+ Ka7 2. Bxb8+ Ka6 3. Bb7+ Qxb7 >>>>>>>>> 4. Rxb7 Kxb7 >>>>>>>>> 8-> 3.27 Mat34 1. Be4+ Ka7 2. Bxb8+ Ka6 3. Bb7+ Qxb7 >>>>>>>>> 4. Rxb7 Kxb7 >>>>>>>>> >>>>>>>>>What it did was to search deeply enough to see that it could trade bishop >>>>>>>>>and rook for the opponent's rook and queen, leaving it in a KBN vs K position. >>>>>>>>>And after searching the 8 plies into the future (as it did above) it then found >>>>>>>>>the endgame database position and said "aha, Mate in N from this point." >>>>>>>>> >>>>>>>>>This is why my current version (15.21) won't play Rxb2, because it can see >>>>>>>>>deeply enough into the future to see the white king eating the black pawns >>>>>>>>>and that gives "mate in N". Or in some variations it sees one black and one >>>>>>>>>white pawn being traded, and that also leads to mate in N. >>>>>>>> >>>>>>>>The difference is that in your example you have a line of 8 plies leading to the >>>>>>>>position that you use tablebases and >>>>>>>>you have not a line of 12 plies from the position before Rxb2 that can lead to >>>>>>>>KPP against K or KP against KP >>>>>>>> >>>>>>>>because the white king must do at least 9 moves to eat the black pawns >>>>>>>>Kxb2,Kc2,Kd3,Ke4,Ke5,Kf6,Kg7,Kxh7,Kxg6 >>>>>>>> >>>>>>>>Uri >>>>>>> >>>>>>> >>>>>>>I'm not sure what your point is, however. I do quite a few search >>>>>>>extensions, and the hash table has the effect of letting the search go >>>>>>>deeper than normal as well, in simple endings like this. 9 moves is >>>>>>>really 16 plies plus q-search, which means a 12 ply search only needs to >>>>>>>extend 4 plies to see that... not difficult at all... >>>>>> >>>>>>my point is that I do not understand why crafty without tablebases does the move >>>>>>Rxb2 at depth 12 >>>>>>If it can see the position of KPP against K then the evaluation without >>>>>>tablebases should prevent it to play it >>>>>>and if it cannot see the position of KPP against K then tablebases cannot help. >>>>>> >>>>>>Uri >>>>> >>>>> >>>>>because crafty doesn't evaluate KPP vs K or KP vs KP as won, in that >>>>>position. Which is the point here. If the black king couldn't get >>>>>into the square of the white pawn, it would say this is lost instantly, >>>>>or if it could get to KP vs K it can evaluate that perfectly. But not >>>>>KPP vs K or KPP vs KP or whatever... >>>>> >>>>>And tablebases introduce a new bit of data, namely that white is not a >>>>>pawn ahead, but that white is *mating* black. The difference is in the >>>>>value of the evaluation. With the tablebase it is perfect and says mate. >>>>>Without it, it just counts pawns and comes to the wrong position. Without >>>>>tablebases, my current version will play rxb2 at depth=10, because of the >>>>>new extension stuff I am doing. But with tablebases it won't play it ever. >>>> >>>> >>>>That is great. Don't tablebases involve a disk access? If so, how do you >>>>prevent them from slowing down your program? Are you checking the table-bases >>>>at every leaf of the tree? (assuming that it is the right kind of position.) >>>> >>>>Does the time saved not having to search the tree make up for the time it takes >>>>to access the tablebases? >>>> >>>>Thanks in advance, >>>> >>>>John Coffey >>> >>>there is a trick: You only probe *after* making a capture that takes the total >>>pieces to 3 or 4, or else 5 with the specific case of KR*KR left. Doing this >>>is slower than normal searching, but the perfect information it returns does >>>way more than offset the slower speed... >> >>Here's another trick. I don't know if anybody else has tried this, but it might >>help improve efficiency when there are large numbers of tablebase hits in the >>search. Normally the tablebase would store an evaluation like draw or +mate in N >>or -mate in N. Now the search only needs to know win/draw/loss except at the >>root, where the best move is also needed. We can store win/draw/loss in 2 bits >>per position, which is less than the space to store mate in n type scores. By >>making the tablebase very compact, we may be able to store it in RAM, increasing >>speed by avoiding many disk accesses. When we actually reach a tablebase >>position at the root, the 2 bits of information are insufficient, so we store a >>second, larger tablebase on disk with a move for each position, and just look up >>the move at the root (we could also store number of moves to mate, but that is >>not necessary). Does this make sense? >> >>Best wishes, >>Roberto > > >It really wouldn't help, because this would reduce the size of the current >tablebases by 1/4, because they use 8 bit values. And at 2+ gigs just >for KRPKR + promotions, such a savings wouldn't help as the resulting >databases would still be over 512mb. > >and the values would be very difficult to use > Well, at present 5-piece endings are too large for the RAM capacity of most machines even when shrunk to quarter size, but maybe the method would be usable for the smaller 4-piece endings? I don't see that it would be terribly difficult to implement. Consider for example KRPKR. I imagine you already reduce the size by half by reflecting the board to always have the pawn on a,b,c or d-files, and index the table by the piece positions: 24 pawn positions and 64 possible positions for each rook and king. So why not store a large array of 2^24 48-bit numbers, where you access the array by roo/king positions and examine the appropriate two bits according to the pawn position? If the size is too great still, how obout splitting it up into four tablebases, one for each pawn, to reduce by a further factor of four, since usually the hits will not involve the pawn being on different files in different positions. Or for a four-piece ending like, say, KQKR, where you can arrange by symmetry for one of the pieces (say White king) to be on a1,b1,c1,d1,b2,c2,d2,c3,d3 or d4. That gives 10x2^18 positions, so yo could store an array of 40960 128-bit vectors (10x2^12) accessed by WK,WQ,BK and then examine the two bits corresponding to the square for the BR. This bit table would require therefore 40960x16=640 KB, which is surely possible to store in RAM while the search progresses. Whatever the limit of your RAM storage for tablebase information, you will fit four times as much in with the bit-table data structure. Whether this can make the all-important difference to storing in memory or on disk will depend on your available RAM and the size of the particular tablebase in question, but I believe it might just tip the balance in critical cases. You could generate the bit-tables easily from your existing tablebases. Best wishes, Roberto
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.