NIM

We could use unchanged much of Gary Darby's Delphi code (including comments and downloaded from Nim, Gametrees, and Minimax) in this online preview of the game Nim. Follow the link for the background to the application. We renamed HighChildIndex to BestChildIndex - the number of the child with maximum value for Player 1 or the minimum value for Player 2. We have included the debug code so that you can follow some of the program's working to provide a suggestion for the next move.

The arrows on the spin edit boxes show permanently in Firefox, on mouseover in Opera and Chrome, and not at all in Internet Explorer or Edge. The display of text showing in the yellow simple labels depends on the browser and its zoom setting. Please be patient if you request a suggestion for more than 12 sticks; processor-intensive tasks and recursion are not ideally suited to JavaScript. Please let us know if you spot a deficiency in the code. You could easily write a much quicker way of making the suggestion for a single pile of sticks, but the purpose of the program is to demonstrate the use of the minimax algorithm.

The Smart Pascal code and XML code of the form follow the program in action. The theme is Smart-Blue.css.

NIM.html

If the program does not work, try another browser such as Chrome. If you see no display at school, the security system might have blocked it. You can try instead this direct link to the program running on its own page.

Smart Pascal Code

unit Form1;

{Copyright 2002, Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org

 This program may be used or modified for any non-commercial purpose
 so long as this original notice remains in place.
 All other rights are reserved
 Converted to Smart Pascal by PPS, 2016
 }

interface

uses 
  SmartCL.System, SmartCL.Graphics, SmartCL.Components, SmartCL.Forms, 
  SmartCL.Fonts, SmartCL.Borders, SmartCL.Application,
  SmartCL.Controls.PaintBox, SmartCL.Controls.Label, SmartCL.Controls.Memo,
  SmartCL.Controls.Button, SmartCL.Controls.EditBox, SmartCL.Controls.SimpleLabel;

type
  TNode = class(TObject)
    Sticks: integer; // how many sticks remain
    level: integer; // what level are we at
    bestchildindex: integer; // the child number of the best move from this node
    procedure assign(n: TNode);
  end;

  TForm1 = class(TW3Form)
    procedure NbrSticksChanged(Sender: TObject);
    procedure H1TakesChanged(Sender: TObject);
    procedure NewGameBtnClick(Sender: TObject);
    procedure TakeBtnClick(Sender: TObject);
    procedure SuggestBtnClick(Sender: TObject);
  private
    {$I 'Form1:intf'}
    lblDescription, lblInstructions: TW3SimpleLabel;
  public
    FirstNode, CurrentNode: TNode;
    NextPlayer: string;
    y1, y2, x1, incr: integer; // stick drawing parameters
  protected
    procedure InitializeForm; override;
    procedure InitializeObject; override;
    procedure newgame;
    procedure drawboard;
    function search(B: TNode): integer;
  end;

implementation

procedure TNode.assign(n: TNode);
begin
  sticks := n.sticks;
  level := n.level;
end;

{ TForm1 }

procedure TForm1.InitializeForm;
begin
  inherited;
  firstnode := TNode.create;
  firstnode.level := 1;
  newgame;
end;

procedure TForm1.InitializeObject;
begin
  inherited;
  {$I 'Form1:impl'}
  lblInstructions := TW3SimpleLabel.Create(Self);
  lblInstructions.Left := 5;
  lblInstructions.Top := 160;
  lblInstructions.Width := 140;
  lblInstructions.Height := 80;
  lblInstructions.Caption := 'Enter 1 to 3 sticks and click "Take". Click "Suggest" for a suggestion';
  lblInstructions.Autosize := false;
  lblInstructions.Handle.style.background := 'yellow';
  lblInstructions.Handle.style.fontSize := '12px';

  lblDescription := TW3SimpleLabel.Create(Self);
  lblDescription.Left := 5;
  lblDescription.Top := 5;
  lblDescription.Width := 210;
  lblDescription.Height := 75;
  lblDescription.Caption := "To play NIM, sticks are laid out and two players take turns removing 1, 2 or
                             3 sticks. The player who takes the last stick loses.";
  lblDescription.Autosize := false;
  lblDescription.Handle.style.background := 'yellow';
  lblDescription.Handle.style.fontSize := '11px';
  lblNbrSticks.Handle.style.fontSize := '14px';
  lblTitle.Handle.style.fontSize := '36px';

  H1Takes.InputType := itNumber;
  H1Takes.SetMax(3);
  H1Takes.SetMin(1);
  NbrSticks.InputType := itNumber;
  NbrSticks.SetMax(15);
  NbrSticks.SetMin(2);
  PlayList.ScrollH := soNone;
  DebugBox.ScrollH := soNone;
end;

procedure TForm1.newgame;
begin
  // Initialize a new game
  if assigned(currentnode) then
    currentnode.free;
  NextPlayer := '1';
  lblPlayer.caption := 'Player ' + nextplayer;
  firstnode.sticks := strtoint(NbrSticks.text);
  currentnode := TNode.create;
  CurrentNode.assign(firstnode);
  playlist.text := '';
  if currentnode.sticks > 1 then
    incr := 8 * W3Paintbox1.width div (10 * (currentnode.sticks - 1)) // distance between sticks
  else
    incr := 0;
  x1 := W3Paintbox1.width div 10;  // 1st stick distance from left
  y1 := W3Paintbox1.height div 10; // stick top end
  y2 := 9 * W3Paintbox1.height div 10; // stick bottom end
  drawboard;
  DebugBox.text := '';
end;


{*********************** Search ***********************
 ************* The meat in this sandwich! *************
recursive minimax search of children of passed node to determine node values}
function TForm1.search(B: TNode): integer;
{Evaluates the payoff for node B for  player Player.  Returns the payoff and
 sets property bestchildindex in TNode to the index of the highest child. }
var
  C: TNode; // temporary child node
  value, temp, i: integer;
begin
  if b.sticks = 0 then
    begin // computing the payoff of this leaf for player 1
      if  b.level mod 2 = 1 then // player 1's turn
        result := +1  // and no sticks left, that's good
      else // player2 level
        result := -1 // that's bad
    end
  else
    begin
      // initialize minimum or maximum value for children
      if b.level mod 2 = 1 {player1} then
        value := -1000000
      else
        value := 1000000;
      c := TNode.create;  // make a child
      c.level := b.level + 1;
      for i := 1 to 3 do
      begin
        c.sticks := B.sticks - i;
        if c.sticks >=0 then // search until all sticks are gone
          if b.level mod 2 = 1 {player1} then
            begin  // find the max value of children
              temp := search(C);  // recursive call for 2's turn
              if temp > value then
                begin
                  value := temp;
                  b.bestchildindex := i;
                end;
            end
          else
            begin  // player 2, find min value of children
              temp := search(C); // recursive call for player 1's turn
              if temp < value then
                begin
                  value := temp;
                  b.bestchildindex := i;
                end;
            end;
      end;
      c.free;
      result := value;
    end;
  Debugbox.text  := DebugBox.text + #13#10 + 'Level: ' + inttostr(b.level) +
                   ', Player: ' + inttostr(2 - b.level mod 2) +
                   ', Sticks: '+ inttostr(b.sticks) + ', Value: ' + inttostr(result);

end;

procedure TForm1.drawboard;
// Draw a simple image of the sticks from parameters set in Newgame procedure
begin
  W3PaintBox1.OnPaint :=
    procedure (Sender: TObject; Canvas: TW3Canvas)
    begin
      Canvas.FillStyle := 'white';
      Canvas.FillRect(0, 0, W3Paintbox1.Width, W3Paintbox1.Height);
      Canvas.FillStyle := 'blue';
      for  var i := 0 to currentnode.sticks - 1 do
        Canvas.FillRect(x1 + i * incr - 2, y1, 4, y2 - y1);
      W3PaintBox1.Invalidate;
    end;
end;

procedure TForm1.SuggestBtnClick(Sender: TObject);
var
  bestindex: integer;
  stickword: string;
begin
  DebugBox.text := 'Recursive search results';
  search(currentnode);
  bestindex := currentnode.bestchildindex;
  stickword := ' stick';
  if bestindex > 1 then
    stickword := stickword + 's';
  PlayList.Text := PlayList.Text + #13#10 + 'For Player ' + nextplayer + ': I suggest taking '
                   + inttostr(bestindex) + stickword;
  h1takes.value := bestindex; // Make suggestion the default amount for next move
end;

{************** TakeBtnClick ****************}
procedure TForm1.TakeBtnClick(Sender: TObject);
// User clicks to take some sticks
begin
  // Make the next board position
  inc(currentnode.level);
  if h1takes.value > currentnode.sticks then
    h1takes.value := currentnode.sticks; // can't take more than remain
  currentnode.sticks := currentnode.sticks - h1Takes.value;
  drawboard; // draw it
  Playlist.text := Playlist.text + #13#10 + 'Player ' + nextplayer + ' takes ' + inttostr(h1Takes.value)
                   + ', Remaining: ' + inttostr(currentnode.sticks);
  if currentnode.sticks = 0 then
    showmessage('Player ' + nextplayer + ' took last stick and loses!')
  else
    begin
     if nextplayer = '1' then
       nextplayer := '2'
     else
       nextplayer := '1';
     lblPlayer.caption := 'Player ' + nextplayer;
   end;
end;

procedure TForm1.NewGameBtnClick(Sender: TObject);
begin
  newgame;
end;

procedure TForm1.NbrSticksChanged(Sender: TObject);
begin
  if NbrSticks.Value > 15 then
    NbrSticks.Value := 15;
end;

procedure TForm1.H1TakesChanged(Sender: TObject);
begin
  if H1Takes.Value > 3 then
    H1Takes.Value := 3;
end;

initialization
  Forms.RegisterForm({$I %FILE%}, TForm1);
end.    

XML Code of Form

<SMART>
  <Form version="2" subversion="2">
    <Created>2016-11-28T20:07:37.702</Created>
    <Modified>2016-12-01T11:25:03.635</Modified>
    <object type="TW3Form">
      <Caption>W3Form</Caption>
      <Name>Form1</Name>
      <object type="TW3PaintBox">
        <Width>216</Width>
        <Top>40</Top>
        <Left>224</Left>
        <Height>104</Height>
        <Name>W3PaintBox1</Name>
      </object>
      <object type="TW3Memo">
        <Width>312</Width>
        <Top>152</Top>
        <Left>144</Left>
        <Height>152</Height>
        <Name>PlayList</Name>
      </object>
      <object type="TW3Button">
        <Caption>Suggest</Caption>
        <Width>96</Width>
        <Top>296</Top>
        <Left>8</Left>
        <Height>32</Height>
        <Name>SuggestBtn</Name>
        <OnClick>SuggestBtnClick</OnClick>
      </object>
      <object type="TW3Button">
        <Caption>Take</Caption>
        <Width>96</Width>
        <Top>336</Top>
        <Left>8</Left>
        <Height>32</Height>
        <Name>TakeBtn</Name>
        <OnClick>TakeBtnClick</OnClick>
      </object>
      <object type="TW3EditBox">
        <Value></Value>
        <Text>1</Text>
        <Range></Range>
        <Width>56</Width>
        <Top>248</Top>
        <Left>8</Left>
        <Height>40</Height>
        <Name>H1Takes</Name>
        <OnChanged>H1TakesChanged</OnChanged>
      </object>
      <object type="TW3Label">
        <Caption>Player 1</Caption>
        <Width>112</Width>
        <Top>136</Top>
        <Left>8</Left>
        <Height>32</Height>
        <Name>lblPlayer</Name>
      </object>
      <object type="TW3Button">
        <Caption>New Game</Caption>
        <Width>96</Width>
        <Top>120</Top>
        <Left>128</Left>
        <Height>32</Height>
        <Name>NewGameBtn</Name>
        <OnClick>NewGameBtnClick</OnClick>
      </object>
      <object type="TW3EditBox">
        <Value></Value>
        <Text>7</Text>
        <Range></Range>
        <Width>56</Width>
        <Top>80</Top>
        <Left>168</Left>
        <Height>40</Height>
        <Name>NbrSticks</Name>
        <OnChanged>NbrSticksChanged</OnChanged>
      </object>
      <object type="TW3Label">
        <Caption>Initial number of sticks</Caption>
        <Width>176</Width>
        <Top>89</Top>
        <Height>18</Height>
        <Name>lblNbrSticks</Name>
      </object>
      <object type="TW3Label">
        <Caption>NIM</Caption>
        <Width>128</Width>
        <Left>224</Left>
        <Height>40</Height>
        <Name>lblTitle</Name>
      </object>
      <object type="TW3Memo">
        <Text>W3Memo</Text>
        <Width>344</Width>
        <Top>312</Top>
        <Left>112</Left>
        <Height>80</Height>
        <Name>DebugBox</Name>
      </object>
    </object>
  </Form>
</SMART>
Programming - a skill for life!

Challenges from the DelphiForFun Website