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

Problem Description

In this game, "Subtract-A-Square", a positive integer is written down and two players take turns subtracting squared integer values (1,4,9, etc.) until one player leaves zero, in which case he (or she) is the winner. 

What square should the first player subtract if the original number is 29?

Background & Techniques

This game is adapted from   Mathematical Bafflers, Angela Dunn, Dover Publications, 1980.  It is a two person zero-sum game;   "zero-sum" meaning that when I win, you lose and vice-versa.   It can be considered a variation of "Nim"; where users alternately take 1 to 3 sticks from a pile with the last stick taker winning or losing depending on which version is played.  In Subtracting Squares, the number taken must always be the square of an integer and the player who reduces the count to 0 is the winner.. 

I have generalized the original question to allow target values from 1 to 50 with allowable subtrahends (the number being subtracted) ranging from 1 though 6 squared.  (1, 4, 9, 16, 25, and 36).

This version of the program uses a technique called "Minimax" to evaluate outcomes for all possible
choices for the player whose turn it is. The algorithm chooses the move which minimizes the maximum
gain for the other player, which for zero-sum games like this one, also maximizes our minimum gain.

For human players, the result of the Minimax search is available as a suggested move. When the computer is a player and making a move, the  Minimax result is always the move it chooses.

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

I modified the Search procedure from the Nim program on the Nim, Gametrees, and Minimax page to perform the Minimax search here.  I originally extended the starting values to 100 but evaluating the complete game tree for   large numbers takes too long.  The current limit of 50 calls Search 225,000 times and takes  15 seconds or so to evaluate.  That seems like a long time for the number of calls but I haven't yet investigated why. 

My original version did not implement computer play and always displayed the Suggest button, but I decided that made it too tempting to "cheat" by always letting the program tell you which move to make.  Now the human can play against the computer and a check box controls whether to display or hide the Suggest button for the Human player.  (The computer as player always has access to the suggested move, and uses it!) 

One other strategy that is partially implemented stretches the game by taking the smallest move that will not affect the result if both players take Minimax recommendations.  The idea is that, for the player destined to lose, stretching the game will allow more opportunities for the destined winner to make a mistake and lose the game.  A late addition is the MaximizeBox checkbox which tells Search to generate children from high to low values with the lowest optimal value being returned.    A better implementation would use the CheckIfAWins function tells which returns true if the first  player will win an optimally played game.  The function computes the complete game tree in advance which can take 15 or 20 seconds for starting values of 50.   (In a test, starting  value of 55 took 2 minutes to compute the winner!)    If compute time were acceptable, the "maximize game length" strategy could be applied only for the player that CheckIfAWins says was destined to lose anyway and at least give him a sporting chance.          

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.