Author: KarinsDad
Date: 19:37:42 08/06/99
Go up one level in this thread
On August 06, 1999 at 20:01:16, Robert Hyatt wrote: [snip] >> >>I now understand the difficulties involved (the "take over" case is probably not >>even worth discussing). >> >>My recommendation: punt. > >I agree... but note that many are not going to like this, perhaps yourself >included, when you want to analyze some endgame you played to see what will >happen after the game is resumed... But I don't see a real solution to this >problem... > Actually, I thought of a possible partial solution this afternoon, but it is real nasty and might not be possible with the speed of disk (or other media) reads and possible memory limitations in today's technology. The idea is to add graphs to the current TBs. Assuming a current 5 piece TB is about 100 MB max, you add a pointer to each of the next positions in the TB and another pointer to each of the previous positions. Assuming 50 moves average per position and 4 million positions maximum, this would require 4 bytes * 50 moves * 2 directions * 4 million positions or 3.2 GB extra memory to store each table or 3.3 GB (you could drop this to 2.4 GB more if you used 3 byte "pointers" and calculated the locations in memory since 3 bytes can represent up to 16 million positions). Note: I am guessing on average number of moves in the endgame and number of positions in the worse case TB. These numbers are probably high and Eugene or someone could figure it out more accurately based on their work with the 5 piece TBs. The reason you would read this humongous thing into memory all at once is that you want to modify it. You want to add a flag to each position which effectively removes it from the graph IF that position is one found so far in the current set of moves. You would need some form of hash technique to quickly get to the position you want (this would be built into the TB). You would then work your way back up the graph from that position, removing all mate in x, mate in x + 1, etc. until you find a position who has a second child that is also mate in y (i.e. you are removing a mate in y at some point, but if a sibling also has a mate in y or fewer, you can stop going back up the graph). This would only have to be done for those positions that led up to the first TB move. Effectively what you are doing is removing all possible positions (i.e. paths) that could force the draw via move by rep. Additionally, this huge TB would have to have all of the win preserving pointers in it as well (which would take up about the same amount of space). Each 5 piece TB could be compressed down to a GB or less. But, I do not know how long this would take to read in. And, of course, this would only be used for standard time games since it would take too long to read in a given TB. Note: All pawn pushes would be within the given TB, so any capture done would drop it to a 4 piece TB. Note: The reason I said that it is a partial solution is that you could have the case where either you hit the same position twice in the main game and the TB has no solutions that do not repeat it, OR you could have a situation where you have mate in 100+ and there are no win preserving moves from the start point in the TB to the mate, OR you could have a choice of positions to start in the TB and some could lead to case 2 and some do not and you do not know which is which. Also, this will only work for 5 and smaller piece TBs, not 6 or greater due to the hardware limitations. So, you need 3 or 4 GB of memory and a fast way to upload this into memory from some form of media. And finally, since you mentioned that you do not recall Crafty every running into one of these two problems (for a normal program game, not supplied by a human), it seems that this is WAY too much overkill. However, it was a fun thought experiment while I was doing it. Have fun and keep smiling! KarinsDad :)
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.