Question about retrograde analysis algorithm for endgame databases
mathpolymath
algorithms!)
Can someone help me with a question concerning the retrograde analysis
algorithm?
As I understand it, the retrograde analysis algorithm works something
like:
(1) Initialize each endgame positions with number of possible moves
from this position (children)
(2) Check each position in the database to see if the position score
is the best possible and then notify the parents. Best possible moves
either have the maximum possible score or are ones where all the
children have been fully evaluated (in an alpha-beta sense).
(3) Iterate #2 a certain number of times depending on the maximum
range of scores which are possible for positions in the database
(4) All remaining unsettled positions get a score of 0
Now I understand step #4 is based on the assumption that all repeating
positions have a certain score, which would be true in chess (where
repeats = draw so score = 0). But what about a game whose score would
depend on the exact position of the first (or for that matter N'th)
repeat? Imagine a game where the rules say the game ends whenever a
position is repeated twice (as in chess), but with the additional
caveat that the score might vary depending on the actual position when
this 2nd repeat occurs (in chess, the score of the 2nd repeat is
0=draw)?
How could the retrograde analysis algorithm be changed to take this
variable score on a repeat into account?
THANKS IN ADVANCE!
mathpolymath
> But what about a game whose score would
> depend on the exact position of the first (or for that matter N'th)
> repeat? Imagine a game where the rules say the game ends whenever a
> position is repeated twice (as in chess), but with the additional
> caveat that the score might vary depending on the actual position when
> this 2nd repeat occurs (in chess, the score of the 2nd repeat is
> 0=draw)?
Re-reading my message, I realize that I may not have made myself
clear.
Imagine an abstract zero-sum game where among all of the millions of
possible endgame positions happen to exist 3 positions, X, Y, and Z
where X->Y, Z->Y and both Y->X or Y->Z
If X has a score of 1, Y a score of 2, and Z a score of 3 if the game
draws by repetition on the respective position, then among possible
scenarios might be these two:
... X Y X Y Z Y (2nd repeat. score = 2)
... X Y X Y X (2nd repeat. score = 1)
In this type of game, how should the retrograde analysis algorithm be
set up to compute the endgame database for this type of game?
David Eppstein
math...@yahoo.com (mathpolymath) wrote:
> Imagine an abstract zero-sum game where among all of the millions of
> possible endgame positions happen to exist 3 positions, X, Y, and Z
> where X->Y, Z->Y and both Y->X or Y->Z
>
> If X has a score of 1, Y a score of 2, and Z a score of 3 if the game
> draws by repetition on the respective position, then among possible
> scenarios might be these two:
>
> ... X Y X Y Z Y (2nd repeat. score = 2)
> ... X Y X Y X (2nd repeat. score = 1)
>
> In this type of game, how should the retrograde analysis algorithm be
> set up to compute the endgame database for this type of game?
Tricky repetition prevention rules like this tend to have something to
do in theory with the boundary between PSPACE-complete and
EXPTIME-complete problems. I think the practical interpretation of this
is, you may not be able to solve the resulting problem with forward or
retrograde analysis, because the game states become too complicated --
you have to know not just where the pieces are on the game board, but
also which positions you've already encountered.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Jonathan R. Ferro
If there is an overall rule about how many repeats there can be, so that
the game actually has no infinite move chains, you can "terminalize" all
of the repeating positions by having the states keep track of how they
were reached. I.e., convert {X>Y, Z>Y, Y>X, Z>X} to
{X>XY, XY>XYX, XYX>XYXY, XYXY>XYXYX (terminal, score=1),
XYXY>XYXYZ, XYXYZ>XYXYZY (terminal, score=2),
XY>XYZ, ...
Z>ZY, ...
Y>YX, ...
Y>YZ, ...
}
So, the "Y" state is expanded into 19 different states internally (if I
have counted correctly), 10 of which are terminal, and 9 of which are
not yet "long enough" to end the game. These states do not have any
loopiness, so they can be analyzed normally.
-- Jon
R Gibert
Define the EGTB as an array of unsigned char. Each element has one of 3 types of meanings:
(1) 255: Unknown
(2) 254: Draw
(3) 0-254 : number of ply to mate
Step 1: First pass mark all the stalemates as 254, all the mates as 0 and the remainder as 255 for now.
Step 2: For the next pass over all the elements if the current element is 255 (unknown) make all the legal moves for the
corresponding position and look them up in the table. For all the ones that are mate, select the shortest mate of these. Add 1 to
the mate score and store in the table for the current element. If all of them are 254, mark the current element as 254.
Step 3: Repeat step 2 until a pass is made without making any changes to the table.
Now you have a complete EGTB for a particular type of ending. All the positions that remain with a value of 255 are draws or are
"broken", but for purposes of interpreting 255 when looking up a position legally arrived at, the 255 is interpreted as a draw only.
All the positions with a value of 254 are draws. The remainder give the DTM (=Distance To Mate).
A legal move can be a capture, so such positions must be looked up in another EGTB table.
The reason why we bother with marking positions with 254 as draws is to speed things up. Otherwise, you can simplify further by
ignoring this.
There are no complications with repetition of position and the 50 move rule is ignored.
I've left out the important issue of how to index the table with a given position. i.e. the positions Gödel number. This is a
non-trivial topic, that becomes important for 5-man and 6-man endings.
There is need to make "retrograde" moves.
mathpolymath
> If there is an overall rule about how many repeats there can be, so that
> the game actually has no infinite move chains, you can "terminalize" all
> of the repeating positions by having the states keep track of how they
> were reached. I.e., convert {X>Y, Z>Y, Y>X, Z>X} to
> {X>XY, XY>XYX, XYX>XYXY, XYXY>XYXYX (terminal, score=1),
> XYXY>XYXYZ, XYXYZ>XYXYZY (terminal, score=2),
> XY>XYZ, ...
> Z>ZY, ...
> Y>YX, ...
> Y>YZ, ...
> }
>
> So, the "Y" state is expanded into 19 different states internally (if I
> have counted correctly), 10 of which are terminal, and 9 of which are
> not yet "long enough" to end the game. These states do not have any
> loopiness, so they can be analyzed normally.
>
> -- Jon
This seems like a very good way in theory, but in practice, the number
of states would expand tremendously.
I wonder if there is a practical way once all positions which are part
of cyclical chains are identified. Could this type of state expansion
be applied to only part of an endgame database? For example, in the
conventional retrograde analysis algorithm, the last step is that
after N iterations of the retrograde analysis (where N depends on the
possible range of values for each position), any position which has
not attained a final value is set to 0 (for draw). Presumably, these
last positions have not attained their final value because they are
parts of cyclical chains or positions from which any move ultimately
leads to a cyclical chain. Would it be mathematically valid to apply
the state expansion to these positions only? And how would it work
since the expanded state may include positions with values?
mathpolymath
> The following is what I've worked out:
>
> Define the EGTB as an array of unsigned char. Each element has one of 3 types of meanings:
> (1) 255: Unknown
> (2) 254: Draw
> (3) 0-254 : number of ply to mate
>
> Step 1: First pass mark all the stalemates as 254, all the mates as 0 and the remainder as 255 for now.
>
> Step 2: For the next pass over all the elements if the current element is 255 (unknown) make all the legal moves for the
> corresponding position and look them up in the table. For all the ones that are mate, select the shortest mate of these. Add 1 to
> the mate score and store in the table for the current element. If all of them are 254, mark the current element as 254.
>
> Step 3: Repeat step 2 until a pass is made without making any changes to the table.
>
> Now you have a complete EGTB for a particular type of ending. All the positions that remain with a value of 255 are draws or are
> "broken", but for purposes of interpreting 255 when looking up a position legally arrived at, the 255 is interpreted as a draw only.
> All the positions with a value of 254 are draws. The remainder give the DTM (=Distance To Mate).
>
> A legal move can be a capture, so such positions must be looked up in another EGTB table.
>
> The reason why we bother with marking positions with 254 as draws is to speed things up. Otherwise, you can simplify further by
> ignoring this.
>
> There are no complications with repetition of position and the 50 move rule is ignored.
>
Even this version of the retrograde analysis algorithm doesn't handle
the case in an abstract game if repetition draws from different
positions have different values. This is not relevant in chess since
all positions ultimately have a value of -1 (loss), 0 (draw) or 1
(win). But imagine a case where you get 0.5 points if you draw when
you have a certain position, but -0.5 points if you draw in another
position...
Jonathan R. Ferro
> jfe...@nu.ece.cmu.edu (Jonathan R. Ferro) wrote:
> > So, the "Y" state is expanded into 19 different states internally (if I
> > have counted correctly), 10 of which are terminal, and 9 of which are
> > not yet "long enough" to end the game. These states do not have any
> > loopiness, so they can be analyzed normally.
>
> of states would expand tremendously.
Yep, you got that right. Welcome to the world of artificial intelligence.
-- Jon
R Gibert
"mathpolymath" <math...@yahoo.com> wrote in message news:98c3bc67.02042...@posting.google.com...
Evidently, I did not read your original question carefully.
Give a specific rule for scoring repetition draws and I will think about it. How you go about it depends on what the rule is.
R Gibert
"R Gibert" <gib...@cox.net> wrote in message news:VUmy8.11636$ab.7...@news2.west.cox.net...
I looked at some of the other posts in this thread and it seems you are including "history" information in the score. This "history:
information must be made a part of the indexing scheme, so that 2 otherwise identical positions with a different history will
generate a distinct index. I think this can be made to work, since the algorithm I gave can accomodate different kinds of draws with
different scoring. Unfortunately, including history information will blow up the EGTB size like crazy.
mathpolymath
Aha! I seem to have found a much simpler way, if my logic is correct.
Let me know if I have reasoned incorrectly.
Under the simple assumption that repetition of position in a game is a
draw and has the game-theoretic value of zero (as is the case with
chess), the last step of the retrograde analysis algorithm requires
that all remaining unsettled positions are set to 0.
Now, if we modify the assumption to a more complex one in some
unspecified abstract finite zero-sum game that says the game-theoretic
value of a draw-by-repetition depends on the actual position that
repeats (note that a dependence on the position does not automatically
imply that the game-theoretic value depends on the move history, which
would be a stronger condition!), then we have the following situation:
I assert that the last step of the retrograde analysis algorithm has
unsettled positions set to 0 because each unsettled position in the
database has the feature that either there is no move possible from
this position that leads to a non-repeating position *or* the value of
a draw-by-repetition (which is zero under the simple assumption) is
greater than the value obtainable through any non-repeating move.
As we use the endgame database then, the first time we come across
such a position that is unsettled in this way, we know that the best
move leads to a repeat and draw, whether the actual drawing condition
is:
(1) positions that only can repeat are automatically draws
(2) draw-by-repetition only take effect after N repetitions of a
position
So my thought is that in the case that draw-by-repetition does not
automatically lead to a value of 0, we only need to statically
re-examine the unsettled positions and the game-theoretic value of the
children positions and evaluate each of these unsettled positions as a
terminal position with a game-theoretic value of whatever is greater
of the game-theoretic value of a draw in the present position or
greatest child game-theoretic value of all positions which are
children to the present position under consideration.
The nuance is that we can not propagate the value of such
draw-by-repetition terminal positions onto it's parents, which could
be other draw-by-repetition terminal positions! For example, in the
case where draw-by-repetition position X has a game-theoretic value of
+2 and draw-by-repetition position Y has a game-theoretic value of +4,
then if we are presented with a repetition as:
... X Y X Y X (2nd repetition, terminal value = +2), but
... Y X Y X Y (2nd repitition, terminal value = +4)
We could have the situation that as we walk the endgame database
evaluating repeating positions as terminal values, that these values
could end up being passed on to their parents. In this case, if we
visit (and evaluated) position Y before position X, then we might
erroneously end up with both Y and X with a terminal value of +4! In
order to avoid this error, we have to copy unsettled positions and
update the values in our copy through evaluation in the original
database. Then when we are finished walking the values in our copy,
we can mirror these back into the original database.
In this way, I have addressed this complex-valued draw-by-repetition
problem with negligible additional effort and at the cost of only some
additional memory (for an intermediary copy of the unsettled values).
Are there any holes in my reasoning? Can other cases of state
expansion in game trees be solved similarly?
Jonathan R. Ferro
> jfe...@nu.ece.cmu.edu (Jonathan R. Ferro) wrote in message news:<r1znzqs...@nu.ece.cmu.edu>...
> > math...@yahoo.com (mathpolymath) writes:
> > > jfe...@nu.ece.cmu.edu (Jonathan R. Ferro) wrote:
> > > > So, the "Y" state is expanded into 19 different states internally (if I
> > > > have counted correctly), 10 of which are terminal, and 9 of which are
> > > > not yet "long enough" to end the game. These states do not have any
> > > > loopiness, so they can be analyzed normally.
> > >
> > > This seems like a very good way in theory, but in practice, the number
> > > of states would expand tremendously.
> >
> > Yep, you got that right. Welcome to the world of artificial intelligence.
> >
> > -- Jon
>
> Aha! I seem to have found a much simpler way, if my logic is correct.
> Let me know if I have reasoned incorrectly.
>
>
> In this way, I have addressed this complex-valued draw-by-repetition
> problem with negligible additional effort and at the cost of only some
> additional memory (for an intermediary copy of the unsettled values).
>
> Are there any holes in my reasoning? Can other cases of state
> expansion in game trees be solved similarly?
I would say that you have successfully convinced yourself that you can
deal with loopy positions algorithmically, but that you are fooling
yourself that it's simpler. As far as I can tell, the "intermediary
copies" that you are referring to are simply dynamically-generated
versions of the "expanded states" that I proposed above.
I think it is time to pick a simple game with a loopy endgame and try to
write out the analysis, either by hand or with computer assistance.
Winning Ways has several simple examples, and introduces the concept of
"sidling" as a generalization of "repeated positions cause the game to
end".
Here is a paper by another person who is working on other
loopy-to-non-loopy-conversion issues:
http://www.msri.org/publications/books/Book29/files/moloopy.pdf
which is included as a chapter in _Games of No Chance_
http://www.amazon.com/exec/obidos/ASIN/0521574110
A lot of the problems and trade-offs of different state-search
strategies and state-representation issues are discussed in Russel and
Norvig, chapter 3, and are then applied in chapter 5 specifically to
the searching of 2-player game trees.
http://www.amazon.com/exec/obidos/ASIN/0131038052
It sounds like you are having fun with this. I wish I had time to get
into it all again.
-- Jon
mathpolymath
Actually, the intermediary copies of the state is one static copy of
each state/position which is unsettled. Since there are no more
unsettled positions than positions in the entire database, this is
obviously no more than doubling the size of the original database for
a temporary period of time. Say for a 10GB endgame database, you will
never need more than 10GB of this so-called intermediary storage.
This additional step I have proposed to the normal retrograde analysis
algorithm has negligible time since it is simply a comparison of each
of the n nodes/positions in the original database with each of its
children and then updating the intermediary copy, which is definitely
a O(n) operation.
Now of course, my reasoning could be *completely* wrong and for some
reason this algorithm I have described will not work. But that's the
type of comment I am soliciting.
Note again, that I am trying to only address one aspect of loopiness.
That where the position can statically determine a unique
game-theoretic value when a game ends due to repetition in that
position. No move history is required to determine this value.
If you want an example of a real-world game to use as an example, take
some variants of the game Awari. This abstract game sees 48 identical
piece moved about in 12 containers (half assigned to each player) and
has in some rule variants the feature that a vicious cycle ends the
game (when either there are insufficient to total forces to effect
further captures or the pieces are in such a configuration that each
side can move in such a way during his turn so as to prevent the other
player from capturing any of his pieces) and that when such a vicious
cycle occurs, each player gets to keep the game pieces that happen to
be in his 6 containers. Since number of game pieces possessed by each
player determines the score in the game (game-theoretic value), and
since the number of pieces in each of the 12 containers and in the
players' possession at any point in the game can be statically
evaluated without considering the history of the game, clearly this is
an example of my more general case of draw-by-repetition values
depending on position when the draw-by-repetition occurs. Also, in
this example game, these positions where "vicious cycles" occur are
not necessarily end nodes in the game tree, but only loops where it is
preferable to remain in the loop than to exit (for example exiting by
moving so as to allow the opponent to make some more captures)... I'm
not sure that giving my problem a concrete target helps to address the
correctness of my modification to the retrograde analysis algorithm,
however.