Author: Roberto Waldteufel
Date: 12:56:21 10/04/98
Go up one level in this thread
On October 04, 1998 at 09:55:06, Robert Hyatt wrote: >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... OK, maybe the performance is already too good to benefit, but I don't understand why you need to distinguish between mate in N-1 and mate in N+1 **inside** the tree - mate is mate as far as the score is concerned - but you certainly need to distinguish them at the **root**. That is why I propose a large file with a move for every position, which would be accessed **only** at the root. For all nodes inside the tree, is it not sufficient to know win/loss draw only, without need to know how long the result will take to achieve. The point I am trying to make is that there is a fundamental difference between the root node and all other nodes. At the root node, the task is to find the best move. It does not matter how good or bad the position is, the problem is only "what do I play now?". At other nodes, the overiding concern is still the same: what is the best move at the root? The only reason we reach the other nodes in the search is to help answer this question, which we do by assigning and backing up evaluations of positions. Thus at non-root nodes, it is the evaluation of the node (or adequate bounds thereon), not the best move at that node, which we must determine. This is an idea that has many interesting consequences in terms of opportunities to trade speed for information, eg reducing the storage space for tablebases, but also in terms of design of algorithms using null width searches like PVS and MTDF. I have made some interesting discoveries in this direction, which I am still evaluating, but I can confirm a speed-up compared to PVS by directly tackling this division of root from other nodes and trying to find the best move in the shortest time, without necessarily ever finding out how good or bad the position actually is. Best wishes, Roberto
This page took 0.01 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.