The Tombs of Strategy
Every game here comes with a network that not only contains every possible game, but the truth,
the whole truth, and nothing but the truth, of every possible position, including the initial one.
A computer program based on a complete network doesn't need an evaluation function and will always
pick the best move (unless told not to). MiniMancala is such a program.
Networks are the things both players and computer programs are running around in, trying to evaluate
positions with limited vision and limited knowledge, each in its own way.
Players try to make sense of it by meaning and intent, and an
evasive quality called pattern recognition - our daily perception and understanding of
reality depends on it, yet nobody seems to know exactly what it is and how it works,
let alone how to implement it.
Whatever it is:
It allows us to play Havannah and make computers look stupid.
Computer programs use an evaluation function
(unless they have the complete network in a database) that assigns to a position the sum
of a number of aspects that can be measured against one another, like material, mobility, capture,
promotion, etc. It calculates the value for all positions up to a certain ply depth, its horizon.
Then it backtracks to find not so much the highest value, but the highest value the opponent
cannot prevent it from reaching. This is called a 'minimax' algorithm.
A refinement is the 'alpha-beta' algorithm, which introduces 'forward pruning', a way to ignore
certain branches without affecting the outcome.
Game mechanisms vary as much as the networks that result from them: Havannah's mechanism is utterly simple,
yet Havannah cannot be programmed. We wonder why that is.
Goals in Havannah are easy to visualize, yet there appear to be no aspects that can be measured,
no material imbalance, no movement, no capture, no promotion - so what
exactly do humans do when they play Havannah. That would seem to be an interesting question.
The networks of the games featured in the player section are HUGE. They're AWESOME in fact - to get
an estimate of the size of most of them we need a practical unit like the
NAU, the Number of Atoms in the Universe. The consensus appears to be around
1087. The question is not whether a network contains more of less positions, because
the NAU itself is still mere peanuts. Most estimates will concentrate on the power to
which it must be raised.
Fortunately size does not affect a network's properties. It allows us to use the complete networks of
very small games to illustrate how one can in principle arrive at the truth in any network.
Two processes are involved: forward tracking and backtrack coloring. We also need a small glossary:
- A ply consists off all positions that can be arrived at after
the number of moves by which it is identified
- A node is a position that has at least one move leading to it
and at least one leading from it
- A leaf is a position that has at least one move leading to it
and none leading from it
- A loop is a sequence of moves that leads to the same
sequence of positions over and over again
- A branch is a sub-network that takes a particular
position as its starting point
|
Forward tracking
The initial position is neither node nor leaf and its ply-number is zero. From it leave
all legal moves and the resulting positions taken together make up ply-1. The legal moves
leaving from each of these, all taken together, make up ply-2. Dare I say 'and so on'?
A few simple rules should be observed:
- All rotations and reflections of a position are considered the same
- Any position is represented only once, though different sequences of moves
may lead up to it
- If a position 'P' occurs that has occurred previously with the same player to move, the track is lead
back to that node. If there is at the same time a track from the node back to the position 'P',
we have a loop
Not all networks contain loops and if they do, they are of no concern to them. It is again in human terms
that they need to be resolved: the ko situation in Go, perpetual check in Chess, opposing kings on the
tric-trac lines in Draughts and similar situations. Go forbids loops and Chess and Draughts feature
'draw by 3-fold' - human decisions.
A game's object is of no concern to a network either: it feeds on legality only.
Imagine zillions of Chess games
in which players take care to avoid mate and content themselves with an endless choreography
of randomly moving pieces - its all in the network. Imagine a game of Go: there appear
to be no leaves! So forward tracking grinds on where players have long decided the outcome.
Their decision is object related and of no concern to a network. Legal play does not forbid a player to
eventually start filling his own eyes, having all groups captured, and still play on. In human terms
everything beyond say ply-250 is sheer nonsense but theoretically Go's network goes on
beyond ply-lightyears from here, totally inconsequential because the 'truth' found in the leaves -
there are leaves because the number of possible positions is finite and Go forbids loops -
has no bearing on the truth as perceived by humans lightyears before that.
In contrast, the network of Othello doesn't contain loops and is neat and tidy up to the leaves.
So much so that a complete network of the 6x6 game as a database for a program is quite possible
and killing the 8x8 version the same way is not impossible.
Backtrack coloring
However huge, networks are finite, so eventually every track not caught in a loop will end in a leaf.
Here the truth can be established beyond any doubt - for the moving player the move leading to the leaf was:
1. a win, |
in which case we color the move(s) leading to the leaf: |
green |
2. a draw, |
in which case we color the move(s) leading to the leaf: |
blue |
3. a loss, |
in which case we color the move(s) leading to the leaf: |
red |
 |
1. a win Here the mere presence of the one green move makes all tracks
to position 1 red, irrespective of other options. All of them may lose for that matter,
and if the last move was a checkmate following a sacrificial attack, they probably will.
| |
 |
2. a draw Here other options cannot be disregarded, so they must be
tracked to their respective leaves and backtracked to establish the color in exactly the same way
we're doing here. Only if none of the other options comes out green, the tracks to position 2
can be colored blue, as depicted on the right. |
 |
 |
3. a loss Here too other options cannot
be disregarded, so they must also be
tracked to their respective leaves and backtracked to establish the color.
Only if all other options come out red, the tracks to
position 3 can be colored green, as depicted on the right. |
 |
This way the truth of the positions immediately prior to the leaves can be established, and from there
of course the truth of the positions immediately prior to that. Dare I say 'and so on'?
And, yes indeed, all the way back to the initial position? Once completed, the network holds the truth
about every possible position:
- If a green line enters, only red ones leave
- If a blue line enters, at least one blue one and no green ones leave
- If a red line enters, at least one green one leaves
It reduces strategy to:
- If you see a green line, pick green
- If you see don't see a green line, pick blue
- If you see don't see a blue line either, you're screwed
|
The process can - in thought - be applied to any game featured here.
That's what it means that these games are "completely determined".
There are usually many more options to lose a game than to win one, but every red
line spawns a green one for the opponent, so red and green even out. More important is the
percentage of blue in the network: its called the 'margin of draws'.
Some games, the Glass Bead Game for instance, cannot end in a draw. Their networks are red-green
all over up to the initial position. In such a game
every move is either winning or losing, right from the start.
Games that can end in a draw may have largely different margins. Havannah has one so small that
for the 271 board the question whether the game is a determined draw or a white win
cannot even be approached.
Chess and Draughts on the other hand have a margins so forgiving that it starts weighing down on
them. These networks start out blue: its a conjecture of course but its hardly conceivable that either game
could have a winning or losing opening move. Being determined draws, increase of knowledge at
the current speed can only result in progressively more draws.
christian freeling
|
|