Graph problem

Hi! This may be wrong place for this post, but I know that there are a lot of fellow nerds on this site. :-)

I wonder if anyone here knows a good way to solve the following problem. It feels like the solution should be both simple and well known, but after thinking for a while I decided to ask for help.

Assume we have a game graph from, let’s say chess. All leaf nodes have a known value, and we want to know the value for the root node. In an acyclic graph the task would be a straight forward one, but for chess we need a way to deal with loops. Since move repetition leads to a draw game in chess, a loop has the value of 0.

In the example below all values are from white’s perspective, so white wants to maximize the value and black wants to minimize it. The white circles are positions where white is to move, and the other way around for the dark circles.

It’s easy to see that white can force a loop, and that this is preferable to the alternatives. But how to solve this for an arbitrary graph?

!http://javerberg.se/images/figure1.png!

I seem to recall that the way to handle this is to assign an upper and lower bound to each node (initially plus/minus infinity), then iterate until nothing changes. At that point, any node where the two bounds are not equal depends on a loop.

Given your rules, the score would be the point in the range which is closest to 0.

Let me work my way through your example (and the related example where -1 is replaced by +1), to make sure I've got it right.

The terminal nodes will not change.

All other nodes start at (-99,+99).

The nodes above the terminals become (-1,+99) and (-2,+99).

Black's nodes (from top to bottom) become (-2,+99) (-1,+99) (-2,+99).

Both of whites become (-1,+99).

All of black's become (-1,+99).

Nothing changes.

Since 0 is in the range (-1,+99), the score for all 5 nodes is 0.

If we replace "-1" with "+1" it goes the same way up to the resolution step, then we note that 0 is no longer in the range, and that +1 is the value closest to 0.

Hope that helps.

That's why most games have anti-repetition rules. Without the rules the game would be flawed because it is possible to find situations where both players have more to lose abandoning the loop and neither would unless forced. (Not for all games, but true at least for chess and go.)

In practice, what defines the game state (and therefore the node) is not only the board position but also the set of moves made illegal by anti-repetition rules. When this is implemented it is no longer a loop since the same board position with different legal moves is no longer the same game state (or node).

That is how most programs implement repetition. (This way or not at all which is also an option not merging identical states at all, defining the games state only by the sequence of moves producing it. I.e., pure tree search without hash tables.) Sometimes the term "situational" hash (board + legal moves) vs. "positional" hash (only the board) is used as a difference between both approaches.

That's why chess has this threefold repetition rule.

Also, forgive me if I'm wrong, but it seems like you could for computer purposes replace the threefold repetition rule with a onefold repetition rule. I.e. a move that would cause a repetition of position is regarded as leading to a new terminal (draw) node, thus making the graph acyclic.
Hmm...
Maybe not. If the graph is a lattice due to possible transpositions, it may be impossible to determine if a position is a repetition.

New results in loopy games, by Aaron N. Siegel, 215-232

in: Games of No Chance 3,
Edited by Michael H. Albert and Richard J. Nowakowski

http://library.msri.org/books/Book56/contents.html

actually, also in the same volume:

Coping with cycles, by Aaron N. Siegel, 91-123

WOWza, look at all those free books! I start a thread in the Hex forum...

Without intending to drift too far off topic, I once heard the game of Trax might never end, although not technically because of loops, since every move adds a tile or tiles to the position. Contrived positions have been constructed where it can be demonstrated that best play for both sides would result in a never-ending game. Maybe such a position could be "distilled" to a representation where this could be regarded as a repetition. It is relevant to note that Trax has a "cascade" rule whereby in a single move, multiple tiles can be added. So a move which "completes a row" might be regarded as functionally equivalent to a move which adds a row on top of that later in the game. Of course, if one considers sub-optimal moves as one should, the branching tree of possibilities would not seem to be identical at these functionally equivalent positions. Does this have any relevance?

Thanks a lot Shark! Haven’t have time to try to prove the algorithm but it seems to work. Johannes thanks for the links! Especially "Coping with cycles" looks promising. Will try to read it within the next few weeks.

Hello,
there are some (nontrivial) games in the Mancala game family
which allow for very long cycles. Looking at human players
it also says something about the characters of those who
like such games.

Ingo.

In the original problem, the graph's nodes correspond to board positions (and whose turn it is and, for chess, the castling statuses and pawn, if any, subject to en passant capture). I think you can address the issue by having the graph nodes represent game states that include the current board position, whose turn it is, and the set of board positions that have occurred in the game (so as to be able to recognize repetitions) and the set of board positions that have been repeated (so as to be able to recognize third occurrences). By using different nodes for a board position's first, second and third occurrences in the game, the graph becomes a tree, and hence acyclic.

Hi MarleysGhost,
theoretically you are right. However, in the Mancala variants I have
in mind, there are unbelievably many different board configurations.
For a human it is almost impossible to keep record (and, keeping
record would destroy the game feeling).

Ingo.