AI LECT 8

NIM
There are three forms of Nim which we shall call NIM I  NIM II and NIM III for ease.
The rules for each are different although there is a certain degree of commonality.
NIM I
1	There are two players.
2	There is a single pile of matches.
3	Moves are made by alternate players.
4	Each player in a move can take up to half the number of matches in the pile.
5	Whoever takes the last match loses.
THEORY
There are safe and unsafe positions.
If a player leaves a pile with N matches where N is in the sequence 
1,   3,   7,   15,   31, . . .     , 2n-1    for positive  n then that player can force a win.
EXAMPLE
Suppose there are 53 matches initially then in binary
53  =  1  1  0  1  0  1 
By removing the most significant digit and adding the least significant digit we get

0  1  0  1  0  1   +   
0  0  0  0  0  1    =
0  1  0  1  1  0    which is 22.  

Thus 22 matches must be withdrawn to leave a safe position and to enable the player to force a win. 
NIM II

1	There are two players.
2	There are several  piles of matches.
3	Moves are made by alternate players.
4	Each player in a move can take any number of matches from a single pile.
5	Whoever takes the last match wins.
THEORY
Charles Bouton of Harvard University around 1900 showed that safe and unsafe positions also exist in this form of the game.  The principle of the method lies in binary non-equivalence.

EXAMPLE
Suppose there are five piles initially and the number of matches in each pile are 1,  3,  5,  7,  11 and expressed in binary

0   0   0   1	1
0   0   1   1	3
0   1   0   1	5
0   1   1   1	7
1   0   1   1	11
1   0   1   1	≠  2

In binary non-equivalence columns are added with no carry.  Since the result is non-zero  the position is declared to be unsafe and it can be made safe by removing a number of matches from one pile.  To identify the pile form the binary non-equivalence of the sum and each pile.

1	0001	3	0011	5	0101	7	0111	11	1011
	1011		1011		1011		1011		1011
	1010		1000		1110		1100		0000

as can be seen the answers in the first four cases are greater than the original piles and so the only 
valid move is the last one which achieves a safe position.
NIM III
1	There are two players.
2	There are several  piles of matches.
3	Moves are made by alternate players.
4	Each player in a move can take any number of matches from an agreed number of piles, strictly 	less than the actual number of piles.
5	Whoever takes the last match wins.
THEORY
E H Moore has shown  that safe and unsafe positions also exist in this form of the game.  The principle of the method lies in  non-equivalence but using P + 1 where P is the number of piles from which  a player can take matches in any turn.

EXAMPLE
Suppose there are five piles initially and the number of matches in each pile are 1,  3,  5,  7,  11. A player can pick up matches from two plies.  The piles are expressed in ternary.

0   0   0   1	1
0   0   1   1	3
0   1   0   1	5
0   1   1   1	7
1   0   1   1	11
1   2   0   2	≠  3

As the result is nonzero and the sum contains a digit 2 it indicates that two piles need to be changed.  In order to find which piles the attached tables below are needed.  The piles are taken in turn and paired off and the digits are split into ordered pairs.

		a	b	c	d
TOTAL	1 	2	0	2
SUM of 7&11	1	1	2	2

giving the ordered pairs (1,1)  (2,1)  (0,2)  (2,2)  and the result (0,0)  (1,1)  (1,1) and (0,0)
yielding 0110  and 0110  ie 6 in each case.   The two piles 7 and 11 become 6 and 6.

 

AUTOMATIC GAME PLAYING

Mechanised game playing is studied partly for fun and partly as a model for real world events involving decision making.  A game is a sequence of choices each choice being made from a number of discrete alternatives .  Each sequence ends in an outcome and every outcome has a value in terms of the opening player.  This can be a win +1 or a loss -1 and sometimes a draw 0.  In other games the game can be scored for example Othello where there are 64 counters the scores could be registered as 63-1 or 33-31.  The games we shall consider are called two-person games with perfect information and they are games played on boards or tables by two people who can both see all the board at all times and also the games do not involve chance as card games and backgammon do.

Game Representation

We can use directed graphs as shown for NIM in the diagram below or trees as also shown.  Trees are used if the path is needed and so for the games we shall consider in this short course trees will be largely used.  Graphs can be of use as they involve less nodes and this is illustrated in Grundy’s game considered below.

Minimaxing
Every terminal node is given a value in terms of the opening player.  This leaves all the other nodes without a value.  If we assume that each player plays optimally and makes the best possible move on each occasion then we can introduce the concept of minimaxing.  Here the opening player plays as though to maximise the value of the position and the opponent minimises and tries to make the position worse for the opening player.  In any situation the opening player chooses the best of all possible nodes to go to and this is maximising whereas  the opponent chooses the best position from the opponent’s point of view which is the worst from the opening player’s.  In this way the nodes above the terminal ones can be scored provided it is known which player is in play.  Thus we can back up  the values to all of the nodes and this is shown in the tree diagram.
Foregone conclusion Theorem and a Fallacy
It would appear that from considering the tree that every game is a foregone conclusion.  If we assume that both players follow an optimal strategy and that the value of the root node is the value of the game then it can be seen at the outset who the winner will be.  Unfortunately for some games such as Chess there are more moves than there are particles in the universe 10120 and so we are unable to follow this prescribed course of action and find the optimal moves at each stage.
Strategies
It is possible that intelligence can be introduced by considering abstract features that are known by experts or regular players to be useful concepts, for example the parity in NIM and the use of binary non equivalence.  Turing initiated this discussion.  The term lookahead can be used to indicate the numberr of future possible moves analysed by either player.  Clearly there is a limit for most players and if the computer is unrestricted no moves made be made because of resource difficulties and so pruning at 3 ply is often introduced.
Heuristics and possible solutions
If the number of possible moves are restricted to 2 by the player in play and one by the opponent then the terminal nodes are not true ones.  Those nodes that lie beyond the lookahead are termed dead positions as they are beyond the radar screen and can only be observed by changing the ground rules.  The terminal nodes produced will have no natural value and so an estimate of their value will be required to enable the ‘best’ move to be determined.   This involves the development of an evaluation function which makes use of the accumulated  knowledge of the game culled from books and experts.