Author: Robert Hyatt
Date: 07:25:05 08/07/99
Go up one level in this thread
On August 06, 1999 at 22:37:42, KarinsDad wrote: >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 :) Not a bad idea, but hellishly complex. I think this is doable in reasonable time during a game. because if we start off in a > 5 piece ending, we don't have the quirk of needing to work out alternative 'conversions' to avoid draws. But if we inherit a game with sub-optimal moves, the 50-move avoiding moves are not very frequent... I think this could work although it will take a lot of work...
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.