Mancala - školský projekt

Novú hru začnete kliknutím na menu Hra -> Nová hra. V okne, ktoré sa objaví môžete nastaviť: mená hráčov kto bude začínať počet kamienkov v jamke (na začiatku) hru proti počítaču - Hoci sú na výber tri možnosti obtiažnosti (začiatočník, pokročilý, závislák) - počítač hraje vždy rovnako Pokiaľ ste už hrali, uloženú hru môžete kedykoľvek načítať cez Hra -> Načítaj hru. Počas hry môžete hru tiež uložiť - Hra -> Uložiť hru

Na obrázku vľavo je odfotený obrázok z hry. V spodnom riadku sa zobrazuje kto je ďalší na ťahu, v krúžku v pravo počet kameňov v jamke, nad ktorou sa zrovna nachádza kurzor myši. Pokiaľ je hráč na ťahu, ťahá tak, že klikne ma jamku (kurzor sa zmení na ruku). Nie je možné ťahať prázdnymi jamkami. Hráčovi 1 patrí spodných 6 jamiek a domček vpravo, hráč 2 ovláda horných 6 jamiek a patrí mu domček vľavo. Pomocou menu Nastavenia je možné tiež nastaviť: Animácie - ak je zakliknuté, pohyb kameňov sa bude animovať (spravené len pomocou Delphi Timera - čiže môže sekať) Zobr. počty kameňov - zapne/vypne krúžok vpravo dole Obrys jamiek - ak je zakliknuté, okolo jamiek sa zobrazí šedý obrys V pravom hornom rohu sa môžu objaviť dve ikonky. Šipka slúži na vrátenie posledného ťahu (tzv. "Undo"). Po kliknutí na otáznik počítač poradí, ktorou jamkou by bolo vhodné ťahať (volanie GetBestMove).

Ako hraje počítač

Primitívne :-)

Všeobecný princíp hrania podobných hier založených na striedaní hráčov je založený na počítaní ťahov dopredu a vyberaní "najlepšieho" ťahu. Jediným problémom je, že množstvo ťahov enormne narastá v závislosti od toho, ako "ďaleko počítač rozmýšľa". Pokiaľ si odmyslíme možnosť, že hráč môže ťah opakovať, a taktiež že nemôže ťahať prázdnymi jamkami, dostaneme:

ťah:	kto je na ťahu:	počet možností:
1	hráč 1	6
2	hráč 2	36
3	hráč 1	216
4	hráč 2	1296
5	hráč 1	7776
...	...	...
10	hráč 1	60466176

Keby sa počítač snažil "myslieť" len 10 ťahov dopredu, musel počítať viac ako 60 miliónov možností - to je skutočne veľa. Preto sa počítanie ťahov zužuje na takzvané "najlepšie" ťahy. Je to metóda, kedy nám síce niektoré víťazné postupy môžu uniknúť, ale stále dokážeme hrať veľmi dobre. Veľmi ľahko pochopiteľný Kalahový algoritmus (napísaný v Jave) je napr. tu - http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/Kalah.java.

Pôvodne som chcel obdobný algoritmus implementovať aj v mojej hre. Kvôli nedostatku času a blížiacemu sa termínu odovzdania som ho zjednodušil do miery - počítač rozmýšľa len nad vlastným ťahom, nie nad ťahom súpera. Nakoniec to teda vyzerá takto:

function TBoard.GetBestMove : integer;
var x          : TBoard;
    i          : integer;

begin
  bv := -6000;                     // bv - Best Value
  if NP = 1 then                   // hráč 1 (ovláda jamky 1..6)
    for i := 1 to 6 do begin         // pre každú jednu neprázdnu jamku:
      if Pit[i] > 0 then begin
        x := TBoard.CopyOf(self);      // vytvoríme si pomocnú hraciu dosku
        x.SowPit(i);                   // vykonáme ťah jamkou i
        x.Value(1);                    // ohodnotíme výsledok ťahu (uloží sa do x.bv)

        if x.NP = 1 then begin         // ak to bol taký ťah, že ťahám ešte raz (tzv. "Kalah move")
          x.GetBestMove;                 // tak to zopakujeme rekurzívne
        end;

        if x.bv > bv then begin        // ak bv pomocnej hry je zatiaľ najlepšie
          bv := x.bv;
          bp := i;                       // tak si poznačím ktorou jamkou bol ťah spravený
        end;

        x.Free;
      end;
    end
  else                             // to isté pre hráča 2 (rovnaké komentáre)
    for i := 8 to 13 do begin
      if Pit[i] > 0 then begin
        x := TBoard.CopyOf(self);
        x.SowPit(i);
        x.Value(2);

        if x.NP = 2 then begin
          x.GetBestMove;
        end;

        if x.bv > bv then begin
          bv := x.bv;
          bp := i;
        end;

        x.Free;
      end;
    end;

  Result := bp;                    // vrátime ktorou jamkou treba ťahať
end;

procedure TBoard.Value(FromPointOfPlayer : TPlayerID); // ohodnotí konkrétnu hru
begin                                                  // z pohladu niektoreho hraca
                           // (to co je vyhodne z pohladu hraca 1 je zle pre hraca 2)
  if FromPointOfPlayer = 1 then begin
    if Pit[7]>6*ospp then bv := 5000                          // vyhra
    else if Pit[14]>6*ospp then bv := -5000                   // prehra
    else if (Pit[7]=6*ospp) and (Pit[14]=6*ospp) then bv := 0 // remiza
    else bv := Pit[7]-Pit[14];                                // inak vrati rozdiel kamenov v domcekoch
  end else begin
    if Pit[14]>6*ospp then bv := 5000
    else if Pit[7]>6*ospp then bv := -5000
    else if (Pit[14]=6*ospp) and (Pit[7]=6*ospp) then bv := 0
    else bv := Pit[14]-Pit[7];
  end;
end;

Poznámka - hru Kalah "vyriešil" Geoffrey Irving, viac na http://www.cs.unimaas.nl/~donkers/games/kalah/ - a okrem iného potvrdil, že hráč, ktorý začína, má veľkú výhodu.

Download

Verzia 29.01.2007:
Zmeny: pridané funkcie Späť (undo) a Pomocník; oprava niekoľkých chýb
Zdrojový kód (Delphi 6 Personal) - mancala_src_2007-01-29.zip
Skompilovaný program - mancala_bin_2007-01-29.zip

Verzia 03.01.2007: (pôvodne nesprávne označená ako 03.01.2006)
Pôvodná verzia
Zdrojový kód (Delphi 6 Personal) - mancala_src_2007-01-03.zip
Skompilovaný program - mancala_bin_2007-01-03.zip

Linky

• Mancala na Wikipédii [EN]
• Kalah na Wikipédii [EN]
• Wikimanqala [EN] - všetko o Mancalových hrách
• Linky súvisiace s Programovaním I - delphi.input.sk a stránka Moniky Tomcsányiovej

---

Posledná zmena: 16.3.2007