Nim, Gametrees, and Minimax

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

In NIM,  a number of sticks (coins, stones, buttons, chickens, etc.)  are laid out on a surface and two players take turns removing 1, 2 or 3 items at each turn.  The player who takes the last item loses.   Write a program to play NIM.   

Background & Techniques

We're starting a new major topic here - game trees and the minimax search algorithm for determining game play.   I'll be learning with you, but I think I understand the basics.   I don't have space, time, or talent to cover the topic thoroughly here.  But here's an overview for starters. 

Nim

Nim probably originated in ancient China.  It was  given its name by Harvard math professor Charles Bouton who named it after a old  English or German verb meaning "to take away".    There is supposed  to be a fairly complete treatment of Nim in Martin Gardner's book Hexaflexagons and Other mathematical Diversions.  I don't have a copy yet, but it's on my wish list.

Game trees   

A game tree is a method  for showing the game positions for many two player games.   Basic game characteristics are:

bulletTwo players.
bulletIt is a sequential game - players  take turns moving.   
bulletThe game state can be represented by a board containing all the pertinent information. 
bulletBoth players have knowledge of of all possible next moves.  This is called a perfect knowledge game.   This excludes card games with hidden hands, for example, since we do not know all of our opponent's play choices. 
bulletGame  moves are not random - this usually excludes games involving dice or spinning dials.
bulletThe games are finite - they all reach some terminal configuration representing a win, loss or draw result.  

The initial game board is the root node of the tree.  The  children of any node are the board positions that can be reached in a single move.  Each branch of the tree terminates in a leaf node which has no further moves and represents a win for one of the players or a draw.

 Nim, Tic-Tac-Toe, Checkers, Go, and  Chess are typical games suitable for game tree representation.   Here's a portion of the game tree for Tic-Tac-Toe  (lifted without permission from a gamasutra.com page)

In this diagram "X" winning positions give a value of 1, "O" winning positions are given value -1 and ties have value 0.   We'll see why in a few minutes. 

One more item before we move on.  Call the player who moves first Player A, and the other player, Player B.  If we assign a level number of 1 to the root node and increment level numbers for a node's children that by 1, then Player A's moves will be from an odd numbered levels and Player B's will be from even numbered levels.

Minimax 

Minimax is a search method for game trees that provides guidance for good play.    The minimax algorithm assigns  values to game tree nodes. Higher values represent higher probabilities of winning for Player A.  This also means that  higher values reflect smaller probabilities of a win for B.  Conversely small numbers reflect small probabilities of A winning and high probabilities for  B winning.   When examining a Player A  node that has children,  the value assigned is the  maximum of its children's values.   When it is  Player B's turn,  we assume that he will choose the move which is optimum for him.  This is also worst choice for Player A.  That is, B will choose the child node with minimum value as his next move.  Applying this algorithm recursively, we can determine the optimum move for either player from any starting board popsition.

Assigning the lowest level  node values could be the trickiest part of implementing minimax.  For simple games like Nim and Tic-Tac-Toe,  we can afford to analyze the entire game tree and assign payoff values only for the terminal (leaf) nodes.  This simplifies things considerably.  We'll assign a value of +1 if the node represents a winning position for Player A (i.e. it's at an even level) and -1 if it is a winning position for Player B (an odd level).    For Tic-Tac-Toe, it is common to assign values of +1, 0, -1 for Player A win, draw, and lose respectively.   The game tree for Chess is estimated to have more than  10100 nodes, impossibly large,  so Chess playing programs typically search a few levels down, using a payoff function to evaluate the goodness of  future positions furthest down the chain.   The minimax technique is then applied to these values as if they were leaf nodes.  Not perfect,  but more practical than spending 1080 years to find the perfect move.   

If any non-programmers made it this far, you may want to jump to the download section now.

Programmer's Notes:

Let me remind  beginners, that even though it may seem that these programs spring full blown from the fingers of a genius, that's far from the truth.  The 200 or so lines of code in this program do not reveal that many lines lie on the cutting room floor. This is the third fairly complete  Nim rewrite.   For example, early attempts retained child nodes as part of the node structure,  and tried to build an actual tree structure - for no good reason as it turned out.   Terminal nodes were initially identified as a position with a single remaining stick.   That's OK unless someone deliberately loses by take the last two sticks in no move.   Ooops,  the 1 remaining stick node never exists.  Just two of many initial false starts.   

The final version  uses a simplified TNode  with only 3 variables object to define the game position:

bullet Sticks - the number of sticks remaining.
bullet Level  -number of levels deep into the tree, starting from level 1 for the root node).
bullet HighChildIndex  - the number of sticks to take to get to the child with optimum value.   This is the number of the child with maximum value for Player A and the number of the child with minimum value for Player B.   

Function Search is the critical routine in this program.  Pass it a node and it will return the node's value and also fills in HighChildIndex in the node.   It accomplishes this by generating nodes for each  of the valid children (nodes with 1, 2, and 3 sticks removed), recursively calling Search with each child and finding the maximum (for odd levels) or minimum (for even levels) values of the children.   If there are zero sticks remaining in the node passed,  there are no valid children and this is a terminal node.  The value for a terminal node is +1 if it is Player A's turn (It's A's turn and there are no sticks left, so B must have taken the last one, so A wins), and, conversely,  -1 if it is Player B's turn.    

CurrentNode is a global node variable that keeps track of where we are in the game.  

I decided to write Nim as a human vs. human game with a Suggest button to run the minimax search and suggest the best move for the current player.  This just saves a  radio box to choose whether the computer has the role of player A, B, neither or both.   The node variable HighChildIndex set by Search is only used by the top level call from the SuggestBtnClick exit.  It's used to report the best move back to the user.   

DrawBoard is a procedure that draws a simple image of the sticks remaining.   The image may be overlaid by  by a DebugBox listbox containing debugging messages from search routine.  DebugBox is normally invisible, unless a condition compiler symbol DEBUG is defined.   The conditional compiler directive IfDef is used to control  whether or not  debugging code is generated. 

Running/Exploring the Program 

bulletBrowse source extract
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

There are many places to go from this starting point:

Here's a link to an excellent page from a 1997 McGill University Computer Science class; Data Structures and Algorithms, Topic #11, Game trees and Alpha-Beta Search
There are reversed versions of many two-person games, called miseré games for some reason.  (My dictionaries say that the word means "misery" in German or French.)  In any event, in this  "reversed"  version of Nim, you win by taking the last stick.  It  should be a fairly simple enhancement to allow the user to select "normal" or "reversed" versions of play.  
Additional games -  I believe that I'll tackle Connect-4, a four-in-a-row game similar to tic-tac-toe.  There are also more complex versions of NIM with multiple piles of sticks but I can't recall the details. 
Partial evaluation - it would be fun t tackle a game complex enough that complete tree evaluation is not feasible. 
Alpha-Beta pruning  is a minimax search modification that speeds of solution searching by truncating searches when they cannot possibly lead to the best solution.   For example, assume were in Node N  looking for a maximum and child C1 returns a value of 10.  We know therefore  that the final value of N will be greater than or equal to (>=) 10.  Now consider the evaluation of child C2 - remember that since N is at a maximum level, it's children including C2 are at a minimum level -  final value of C2 will be the minimum of the values of all of its children.    So if C2's first child happened to return a level less than 10, say 9, we know that the final value of C2 will be less than or equal to (<=) 9, even if there were 100 more children that we haven't examined yet.   Since the final value of C2 will be <=9, it cannot affect the final value of N (we already know that N will be >=10).   We can thus "prune" the search and not even bother to evaluate any additional children of C2;  saving all those CPU cycles for more important work.  Whew!  This is a case where a picture would be worth 1000 words, so visit the McGill University link mentioned above if you want more information.   

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2017, Gary Darby    All rights reserved.