[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionIn 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 & TechniquesWe'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. NimNim 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 treesA game tree is a method for showing the game positions for many two player games. Basic game characteristics are:
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. MinimaxMinimax 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:
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
Suggestions for Further ExplorationsThere are many places to go from this starting point:
Modified: May 15, 2018 |
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |