Author: KarinsDad
Date: 11:04:52 04/16/99
Go up one level in this thread
On April 16, 1999 at 13:13:33, Will Singleton wrote: > >On April 16, 1999 at 11:37:38, KarinsDad wrote: > >>I think it would be easy to have special code for endgames. There would just >>have to be ALOT of special cases, so the creation of the more complex algorithms >>may be difficult (depending on whether you could build complex ending >>calculations based on simple ending code). >> >>One could have a 32 bit value for all of the pieces and the evaluation routine >>could check to see if at any point in the search whether that value is in the >>subset of special endgame ones. If so, it could use a series of special endgame >>code for those endgame pieces. For example: >> >>p = 1 >>n = 16 >>b = 128 >>r = 1024 >>q = 8192 >> >>Since the kings are not needed (they are always on the board), this structure >>allows up to 8 pawns, 7 knights, 7 bishops, 7 rooks, and 7 queens for each side >>in a 32 bit structure (however, the down side is that you have to count up the >>number of each type of piece for each side, but if you are calculating the >>"tree" on the stack, then this would at least be a delta calculation). >> >>In the case of KR vs. K, this value would have to be checked against 1024 for >>one color and 6815744 (1024 * 64K or 1024 shifted 16 bits to the left) for the >>other color. Those would be the only two legitimate KR vs. K values. >> >>The special endgame code could be placed into multiple DLLs that only get >>uploaded into memory if the search engine comes across one of the special cases. >>This would be similar to the current tablebases, however, if it was done >>properly, the more complex endings would be set up to use code from multiple >>less complex endings in order to calculate the proper set of moves. In other >>words, unlike the tablebases which are exhaustively searched for the best moves, >>this system would use a building block type of approach to calculate the best >>move. >> > >This sounds like a pretty straightforward approach, but I don't understand the >need for DLL's. Why not just call a procedure for each case? It depends on how many cases there are. Currently, there are several Gig of tablebase files, so if 95% is just the listing of the positions and the result(win, draw, or loss) and the other 5% is the best move to make from that position, it would still require several gig to just have all of the positions and the associated result. However, this could be pruned considerable. In the KR vs. K solution, it is only a draw if the opposing king can take the rook immediately, otherwise, it is a win. Therefore, one would just have the positions in there where it is a draw (and of course, the search engine could easily have figured this out anyway for this simple example) and all other positions would be considered a win. In the KR vs. K case, all of the positions are wins if the side to move is the same as the side that has the rook (therefore, none of these positions have to be listed and they can all default). If the other side is to move, then there are approximately 222 thousand positions out of which only about 22 thousand are draws. If there are ALOT of cases (200 for example), then it would be beneficial to only pull up into memory those algorithms that are needed, hence the reason for multiple DLLs. This would also be greatly beneficial if a mechanism could be used to determine more complex cases from simple ones (especially on the fly). > > >>Additionally, each simple endgame DLL could have a list of all possible >>positions with the corresponding list of results (i.e. 1-0, 1/2-1/2, or 0-1) for >>each of them. This would enable the search engine (similar to how tablebases are >>used today) to instantly determine if the position is a win, a draw, or a loss. >>It would only use the algorithm to figure out HOW to play. >> > >How does this differ from tablebases? As per my previous statement, the greatest number of positions would default (e.g. in the KR vs. K case, most positions would default to a win, in the K vs. KR case, most positions would default to a loss). The other positions would have to be listed. However, unlike tablebases, the default positions would not have to be listed NOR would the solution (i.e. the next move) have to be listed. The algorithm code could be in a separate file than the "minimized" tablebase data file. The search engine does not need to know HOW to win at a given position, but it would be important to know that it is a forced win, draw, or loss from there. The bottom line of all of this is that if you can save 40% or more of the tablebase size by not having the "next move" in the tablebase (this would be calculated by the code) and you would not have the positions for the largest number of results in the table (for any given case), then it should take a lot less time to access the tablebase and that space can be used for the algoritms (i.e. the DLL code). The problem is making the code such that A) it is accurate and B) it is not TOO difficult to create in the first place. Additionally, it would be nice if this could be used as a mechanism to calculate complex endgame positions from simple ones (however, this may be too lofty of a goal). Of course, another possible solution would be to take the current tablebase mechanism and create this "minimized" tablebase (probably at least 40% or more smaller in most cases). Then the minimuzed tablebase is used until the current position is actually a tablebase position. At that point, you could use the full blown tablebase (of course this could probably be done cheaper within the current tablebase framework and if you had 2 tablebases, you would need more hard disk space, the only idea here is to have less hard disk access). KarinsDad :) > >Will
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.