Hardware Reference
In-Depth Information
Chapter 17
Synthesis of Strategies for Games
17.1
Formulating a Game as a Unknown Component Problem
Finding winning strategies of some combinatorial games, such as the NIM game,
tic-tae-toe, etc., can be formulated as solving the unknown component problem.
Therefore, BALM can be used to synthesize winning strategies of these combi-
natorial games. The strategy we take is to describe the dynamics and the state of
the game in the fixed component. The unknown component represents one of the
players of a two person game. Generally, we want to input the state of the game to
the unknown component, which will represent the strategy to be used by Player 2;
otherwise the unknown component would have to have many states just to remember
what state the game is in. The other player, Player 1, can be modeled as a random
player. The reason for this is that it is simpler to not have to describe the strategy
for making moves; we will allow it to make any move. If it makes an illegal move,
it loses the game immediately. In this way, Player 2 only has to have a strategy for
when Player 1 makes a legal move. A winning strategy is such that whatever move
Player 1 makes, Player 2 has the ability to make a move to continue the possibility
of winning. This can be ensured by requiring the solution to be an FSM, i.e., to
be expressed by a prefix-closed and progressive automaton. In this case, a winning
strategy can be implemented by a Boolean network. If the input to the unknown
component is the state of the game, then progressive means that, for every state that
the game can get into, there is always an input which leads to an accepting state.
Suppose we have a game for which on each move, there is always some
“progress”. This might be measured by some “energy” function, which always
decreases and is lower-bounded by 0. Examples of such games are NIM (see
Sect. 17.2 ), where the total number of coins in the three piles is always decreasing,
or tic-tac-toe, where the number of empty squares is decreasing. However, in games
like chess, there is no energy function because it is possible to stay in a loop forever.
For energy-decreasing games, the lowest energy states are states where the game
is over. In such cases, any accepting state must be able to progress, and eventually
Search WWH ::




Custom Search