Author: Bruce Moreland
Date: 10:16:19 04/16/99
Go up one level in this thread
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.
>
>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.
>
>Does this approach seem reasonable (I realize that the building block approach
>part of it is complex and would take a lot of work)?
This kind of thing sounds good in principle, but it has a hard time getting past
basic realities. It is certainly possible and useful to quickly recognize some
endings. Sometimes you can return an accurate draw score (KN vs K), and other
times you can return a heuristic score (KR vs KR).
But there are problems with even simple 4-man cases:
a b c d e f g h a b c d e f g h
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
8 | |///| |///| |/R/| |///| 8 | |///| |///| |///| |///| 8
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
7 |///| |///| |///| |///| | 7 |///| |///| |///| R |///| | 7
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
6 | |///| |///| |///| |///| 6 | |///| |///| |///| |///| 6
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
5 |///| |///| |///| |///| | 5 |///| |///| |///| |///| | 5
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
4 | |///| |///| |///| |///| 4 | |///| |///| |///| |///| 4
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
3 |/k/| |///| |///| |///| | 3 |/k/| |///| |///| |///| | 3
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
2 | |///| |///| n |///| |///| 2 | |///| |///| n |///| |///| 2
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
1 |///| |/K/| |///| |///| | 1 |///| |/K/| |///| |///| | 1
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
a b c d e f g h a b c d e f g h
White to move in both cases. The position on the left is won, the position on
the right is drawn (you can also put the rook on g8, that's drawn as well).
I think it would be pretty hard to statically evaluate these KR vs KN positions.
And this is only a 4-man class, it would have to be even harder to do stuff
like KRP vs KR.
If you do manage to make a rule-base for an ending, it would be trivial to check
that it can do either of the following:
1) Distinguish with accuracy between drawn and won cases.
2) Make progress in won cases.
I believe that Marsland did KP vs K, which is the easiest non-trivial case. I
think people have tried KR vs KN, but I've never seen anything that would
indicate that anyone succeeded.
bruce
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.