Een Nim game

download Nim programma

Nim spel




Je speelt tegen de computer.
Per zet mag een "X" een willekeurig aantal kolommen naar links of naar rechts worden verschoven.
De stukken mogen elkaar niet kruisen.
Winnaar is degene die de ander klem zet.

Selecteer het aantal rijen door op een row knop te klikken.
Selecteer wie de eerste zet doet: jij of de computer.
Selecteer random (willekeurige) start positie of anders "O" links en "X" rechts uitgelijnd.
Muisklik op "new game" om de stukken "O" , "X" te plaatsen.
Muisklik op "start" om te beginnen.

Na de klik op "new game" staat het programma in de SETUP modus.
Stukken mogen dan worden verplaatst om een nieuwe beginstand te creeëren.
Een linker muisklik verplaatst de "X" naar het aangeklikte veld.
Een rechter muisklik verplaatst de "O".

Na de muisklik op "start" verplaats je een blauwe "X" door een muisklik op het veld van bestemming.

Nim games in het algemeen

Nim games zijn bordspelen die er uiterlijk heel anders kunnen uitzien
maar die dezelfde strategie, eigenschappen en onderliggende wiskunde bezitten.
Twee spelers verschuiven of verwijderen om beurten stukken (stenen) tot een speler niet meer kan zetten.
Hieronder staan drie typen Nim spelen afgebeeld:

fig1afig1bfig1c

Fig1a
Spelers verplaatsen om beurten de steen horizontaal naar links of vertikaal omlaag.
Winnaar is wie de steen in het groene veld linksonder plaatst.
De positie van de steen is (3,2).
(0,0) is de winnende positie.

Fig1b
Spelers pakken om beurten een willekeurig aantal stenen van een kolom.
Winnaar is wie de laatste stenen pakt.
Spel positie is hier (3,1,2), het aantal stenen per kolom geteld van links naar rechts.

Fig1c
Spelers (rood, blauw) verschuiven om beurten een steen van hun kleur een aantal kolommen links of rechts.
De stukken mogen elkaar niet kruisen.
Winnaar is wie de ander klem zet.
De spelpositie is (2,3,1), het aantal lege kolommen tussen de stenen van elke rij.

Opmerking: Spel a is twee dimensionaal. Spelen twee en drie zijn beide drie dimensionaal.
Elk aantal dimensies (vanaf twee) is mogelijk.

Nim game eigenschappen

Er zijn twee spelers. In dit project is één speler de computer.
Een bordpositie is altijd goed of slecht.
Een bordpositie is goed als er alleen zetten zijn die een slechte positie opleveren.
Een bordpositie is slecht als er een zet mogelijk is naar een goede bordpositie.

Een goede bordpositie is natuurlijk (0,0,0) in het geval van een driedimensionaal spel.

Dus posities (5,0,0) of (0,3,0) zijn slecht want met één zet is positie (0,0,0) te bereiken.
Goed posities zijn verder (1,1,0) , (1,0,1) en (0,1,1) omdat ze twee zetten van (0,0,0) verwijderd zijn.

Dit Nim game programma gebruikt type c met 12 kolommen en selecteerbare rijen van 2 tot 5.
Om alle goede bordposities te vinden heb ik een programma geschreven (NimResearch).

Het Nimresearch project

Het volgend plaatje toont output van het nimresearch programma:



64 goede posities zijn gevonden.
De cijfers geven per rij het aantal lege velden aan tussen de stukken.

Het Nimresearch programmma berekent goede posities op een numerieke manier.
Beginnend bij (0,0,0) is de volgende goede positie twee zetten hiervan verwijderd.
Dat levert posities (0,1,1) (1,0,1) (1,1,0)
(posities 1 zet verwijderd van een goede worden simpelweg genegeerd)
Array counter[1..5] {maximaal 5 rijen } telt de kolommen in elke rij.
De kolommen teller wordt met één verhoogd door: 
function CounterInc : boolean;
var carry,i : byte;
begin
 carry := 1;
 for i := 1 to rowcount do
  begin
   counter[i] := counter[i] + carry;
   if counter[i] < columns then
    carry := 0 else counter[i] := 0;
  end ;
 result := carry = 0;
end;
De volgende procedure test elke stand van de kolommen teller op goed:
procedure TestPoint;
var i : word;
    d,j : byte;
begin
 i := 0;
 repeat
  inc(i);
  j := 0;
  d := 0;
  repeat
   inc(j);
   if counter[j] <> GoodPoints[i,j] then inc(d);
  until j=rowcount;
 until (d=1) or (i=GPX);
 if d <> 1 then savePoint;
end;
Opmerking: GPX is het aantal goede posities opgeslagen in array GoodPoints[..,..].

Conclusie

Na bestudering van de Nimresearch output zien we de simpele truuk:
om te zien of een bordpositie goed is:
    - schrijf je de positie (X,Y,Z) binair uit
    - een positie is goed als geldt: X xor Y xor Z = 0.

Een analytisch bewijs

Schrijf de bord posities als groepen (G0,G1,G2...)
G0 : 0,1 positie in (2*2) groep
G1 : 0,1 positie in (4*4) groep...
G2 : 0,1 positie in (8*8) groep etc.

Voor een twee dimensionale G0 groep zijn (0,0) en (1,1) goede posities.
Maar voor G1, G2.. groepen geldt hetzelfde, ook hier zijn (0,0,) en (1,1) goede posities.

Voor een goede positie moeten alle groepen goed zijn.



Decimaal geteld is positie (6,6) binair (110,110) goed.
G0=(0,0) G1=(1,1) G2=(1,1) allemaal goede groepen.

Positie (2,6) binair (010,110) is fout omdat G0=(0,0) G1=(1,1) G2(0,1)
G2 is fout (links boven 4*4 groep)

In drie dimensies is de winnende positie (0,0,0).
In de 2*2*2 groep G0 zijn goede posities (1,1,0) (1,0,1) en (0,1,1).
Maar opnieuw, dit geldt ook voor de G1, G2, G3 ..groepen.

Is (4,5,3) a goede positie?

(4,5,3) is binair (100,101,011)
G0 = (0,1,1) OK
G1 = (0,0,1) fout
G2 = (1,1,0) OK conclusie: foute positie.



Volgende goede postis zijn te maken door optellen van goede groepen:
Als G0 = (1,1,0) en G1 = (0,1,1) dan
G0 + G1 = (.1, .1,.0) + (0.,1.,1.) = (01,11, 01) decimaal (1,3,2)

Opmerling: shift voor het optellen G1 1 plaats naar links, G2 2 plaatsen etc.

Het Nim project

Data formats

var GPos : array[1..2,1..5] of byte;  //1,2:computer,player; 1..5: row; value is column
    Game : array[1..5,1..12] of byte; //0:empty; 1:computer; 2:player                                
    rowcount : byte = 2;
    Gmap : Tbitmap;
    CHmap : array[0..2] of Tbitmap;
    movebusy : boolean; //prevents interruption of moving  
                        //stone

Het tekenen

Velden tellen 40*40 pixels.
De randen van het spel worden getekend op het canvas van form1.
Alle tekenwerk gebeurt op het canvas van bitmap Gmap.
Gedeelten van Gmap worden vervolgns gekopieerd naar paintbox1 op form1.
Dat om hinderlijk geknipper te vermijden wat zou ontstaan bij het wissen van paintbox1.
Bij de zetten van de "O" en "X" stukken glijden ze pixel voor pixel naar hun bestemming.
Een stuk schuift per 3 milliseconde een pixel op. De CPU klok controleert dit.
De Windows milleseconde klok kan dit niet omdat deze maar per 15 milliseconden ophoogt.
Zie de clock_unit voor details.

De "O" en "X" stukken zijn bij de start van het programma geteknd in bitmaps CHmap[1] en CHmap[2].
Gmap.canvas.draw(x,y,CHmap[2] ) plaatst een "X" op plek (x,y) van Gmap.
Ook is er een lege bitmap CHmap[0] gecreëerd om stukken te wissen.

De schuivende zetten zijn het werk van 
procedure moveto(p,row,column : byte);
//move piece p of row to column
var x,destx,y : word;
    dx : shortInt;
    r : Trect;
begin
 movebusy := true;
 if Gpos[p,row]-column > 0 then dx := -1 else dx := 1;
 destX := (column-1)*40;
 x := (Gpos[p,row]-1)*40;
 y := (row-1)*40;
 while destX <> x do
  begin
   clearField(x,y);
   x := x + dx;
   Gmap.Canvas.Draw(x,y,CHmap[p]);
   r := rect(x-1,y,x+41,y+40);
   form1.PaintBox1.Canvas.CopyRect(r,Gmap.Canvas,r);
   delay(3);
  end;
 Gpos[p,row] := 0;
 Game[row,column] := 0;
 Gpos[p,row] := column;
 Game[row,column] := p;
end;
p = 1 bij een computerzet, p = 2 voor een zet van de speler.
Rijen en kolommen tellen 1..5 en 1..12
dx = 1 voor een zet naar rechts, dx = -1 voor een zet naar links.
destX is x coordinaat van de (kolom) bestemming.
Y is de y coordinaat van de rij..
Procedure clearField[x,y] wist een 40*40 veld en herstelt overschreven lijnen.

Berekening van de Computerzet

procedure computerMove;
var d : array[1..5] of byte;
    dd : array[1..5] of byte;
    col,row,i,newColumn,sum : byte;
    OK : boolean;
begin
 row := 0;
 newColumn := 0;
 for i := 1 to rowcount do d[i] := Gpos[2,i] - Gpos[1,i] - 1;
 sum := 0;
 for i := 1 to rowcount do sum := sum xor d[i];
 if sum = 0 then
  begin
   col := 0;
   row := 0;
   for i := 1 to rowcount do
    if Gpos[2,i] > col then
     begin
      row := i;
      col  := Gpos[2,i];
     end;
   NewColumn := 1 + random(col-2);
   if NewColumn = Gpos[1,row] then inc(newColumn);
  end
  else begin
        for i := 1 to rowcount do dd[i] := d[i] xor sum;
        i := 0;
        repeat
         inc(i);
         OK := dd[i] < d[i];
        until OK or (i = rowcount);
        if OK then
         begin
          newColumn := Gpos[2,i] - dd[i] - 1;
          row := i;
         end;
       end;
 moveBusy := true;      
 delay(500);//msecs
 moveto(1,row,NewColumn);
 gamecontrol(gmCompMoved);
end;
Het aantal lege velden tussen "O" en "X" stukken worden opgeslagen in array d[ ].
Variabele sum is de xor van d[1..rowcount] .
Bij sum = 0 is geen goede zet mogelijk en de computer doet dan een willekeurige zet.
Anders wordt een goede zet berekend waardoor sum=0 wordt.
Dat gaat zo: dd[1..rowcount] := d[1..rowcount] xor sum.
Na keuze van een geschikte rij is newColumn := column – dd[..] – 1;

Spel controle

type TgameState = (gsIdle,gsSetUp,gsPlayer,gsComp);
     TgameMessage = (gmInit,gmNew,gmStart,gmPlayerMoved,gmCompMoved);

var gamestate : TGameState = gsIdle;
Gamestate
    - idle : geen spel of geïndigs spel
    - setUp : spel geselecteerd, wijziging beginstand mogelijk
    - Player : wacht op zet van de speler
    - Comp : computerzet is bezig
Messages naar procedure GameControl(gm : TGameMessage); controleren het spel.

Message
    - Init : als het spel wordt gestart.
    - new : knop ingedrukt
    - start : the knop ingedrukt
    - playermoved : de speler heeft een zet gedaan
    - compmoved : de computer heeft een zet gedaan

De clock unit

unit clock_unit;

interface

uses windows;

procedure startClock;
function getCPUtime : single;

implementation

var t1,t2 : int64;
    frequency : single;    //millisecs

function CPUCLOCK : Int64;
asm
 RDTSC;
end;

procedure initclock;
var a : longword;
begin
 a := gettickcount;
 repeat
 until gettickcount > a;
 t1 := CPUCLOCK;
 a := a + 500;
 repeat
 until gettickcount >= a;
 t2 := CPUCLOCK;
 frequency := (t2 - t1)*0.002;
end;

procedure startClock;
begin
 t1 := CPUclock;
end;

function GetCPUtime : single;
begin
 t2 := CPUCLOCK;
 result := (t2-t1)/frequency;
end;

initialization

 initclock;

end.
De RDTSC assembler code plaatst de 64 bit CPU clock counter in 32bit registers edx en eax.
Wacht daarna voor een update van de windows (milliseconde) klok.
Tel dan het aantal CPU cycles gedurende 500 milliseconden.
De klokfrequentie is CPU cycles * 0.002.
Verstreken tijd wordt geleverd door function GetCPUtime : single;

Hierbij eindigt de beschrijving vn hit Nim game project.

Voor details verwijs ik naar de source code.

Interesse in dit (Delphi7) project?

download nim game source code
download nimresearch program
download nimresearch source code