Author: Robert Hyatt
Date: 06:55:06 10/04/98
Go up one level in this thread
On October 04, 1998 at 07:28:46, Roberto Waldteufel wrote: > >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 The question is, what does this buy us? For the 3-4 piece files, I don't see significant performance loss anyway, because of internal buffering I do and further caching by the operating system.. And as I mentioned, it can be a problem if you don't know the actual mate score, because you have to choose between moves inside the tree, and there is a difference between mate in N-1 and mate in N+1 when making decision...
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.