Hra piškvorky iii

Obsah lekce:

Shrnutí současného stavu hry

S naší hrou jsme se dostali do fáze, kdy jsme schopni na hrací ploše daného rozměru umístit jeden ze dvou možných hracích kamenů (podle toho, který hráč je na tahu).

Za úkol bylo napsat část programu pro vyhodnocení konce hry na jednoduché hrací ploše rozměru 3x3. Konec hry nastane v momentě, kdy budou někde v poli 3 stejné prvky vedle sebe (ať už horizontálně, vertikálně nebo diagonálně).

Řešení tohoto úkolu (pro diagonální nebo horizontální posloupnosti) není nějak obtížné, neboť teoreticky stačí postupně procházet sloupce a řádky pole pevně daných rozměrů (3x3) a vždy jen zjistit, zda je pravda, že celý řádek nebo sloupec obsahuje ve všech svých polích stejný symbol. Pokud je pravda, že najdeme v některém řádku nebo sloupci posloupnost tří stejných symbolů, pak jistě nastal konec hry.

U diagonálních výherních posloupností na ploše 3x3 teoreticky stačí zkorolovat obě diagonály.

V této lekci se podíváme na úkol obtížnější. Bude nás zajímat, zda po posledním tahu hráče nevznila někde v poli posloupnost zvolené délky (3-5 dle nastavení proměnné delka při startu hry) složená ze stejných kamenů. Navíc máme pole většího rozměru (obecně mxn).

Algoritmus pro vyhodnocení konce hry

Než začneme algoritmus psát tak je dobré se trochu zamyslet. :)

Jako první "násilná" varianta se nabízí postupný průchod všech sloupců a řádků (+ diagonál) a hledání posloupnosti dané délky některého ze symbolů. Toto řešení je sice možné, ale velmi náročné na výpočetní výkon - resp. počítač (ať už jakkoli rychlý) musí vykonat velké množství kroků, aby prošel celou hrací plochu a určil, zda se někde nenachází posloupnost hracích kamenů dané délky.

Jaký prostor je po umístění hracího kamene nezbytné projít, aby bylo možné určit, že nastal nebo nenastal konec hry?

Uvažujme libovolný stav kamenů na hrací ploše. Řekněme, že výherní posloupnost (posloupnost stejných kamenů v některém z osmi směrů) bude například 4 (proměnná delka).

Na obrázku níže vidíme situaci, kde má každý z hráčů umístěno 7 kamenů (kameny černé barvy). Jedná se o situaci, kdy může v následujícím tahu vyhrát kterýkoliv z hráčů (možné výherní tahy jsou znázorněny kameny červené barvy). Uvědomme si, že ať už je v hracím poli jakákoliv nevýherní kombinace kamenu, tak výherní posloupnost může v daném tahu vzniknout pouze vložením nového kamene, který výherní posloupnost VYTVOŘÍ a MUSÍ tedy být JEJÍ SOUČÁSTÍ. Pokud tedy budeme chtít testovat, zda výherní posloupnost vznikla, pak stačí ověřit, zda taková posloupnost nevznikla z posledního položeného kamene. Není tedy nutné prohledávat celý prostor, ale stačí vzít do úvahy poslední kámen a ověřit délku posloupnosti stejných kamenů do všech směrů.

Rozeberme nyní postupně výherní situace, které by vznikly položením kamenů A, B a C.

Kámen A

Položením tohoto kamene (suvažujeme nyní jeho souřadnice (i,j)=(3,4)) by vznikla výherní posloupnost 4 kamenů severojižním směrem (NS dle našeho kompasu). Jak lze spočítat, že výherní posloupnost v tomto směru vznikla?

Poslední položený kámen je sám o sobě jedním kamenem ze 4. Následně se podíváme postupně na všechny pozice nad ním (severní směr), na kterých se vyskytuje (bezprostředně za sebou) kámen stejného typu a ty spočítáme. V našem případě je tam jeden kámen na souřadnicích (2,4), obecně na (i-1,j) - posunuli jsme se o jeden řádek "výše" a dostáváme tedy číslo sloupce i-1=2.

Analogicky spočítáme kameny jižním směrem (počítáme všechny kameny stejného typu za sebou dokud nenarazíme na kámen druhého hráče, prázdné políčko nebo konec hrací plochy). Kameny výherní posloupnosti tedy nalezneme na pozicích (i+1,j) a (i+2,j). Zvedá se tedy obecně číslo řádku.

Pokud budeme zároveň počítat nalezené kameny, pak můžeme dojít k tomu, že jejich číslo je ALESPOŇ velikosti proměnné delka (počet kamenů vedle sebe, aby vznikla výherní posloupnost).

Kámen B

Tu je situace analogická, jen se vydáváme severozápadním směrem (NW). Musíme si jen uvědomit, že jdeme na pole (2,2)=(i-1,j-1) a (1,1)=(i-2,j-2). V diagonálním směru NW odečítáme jedničku od čísla řádku (i) a také sloupce (j).

Po dosažení konce hrací plochy se vydáme směrem SE. Tam najdeme jeden kámen na souřadnici (i+1, j+1).

Kámen C

Analogicky jako v přechozích případech popište postup v tomto případě.

Pro testování výhry v ostatních směrech je situace analogická

Obecně lze formulovat tento algoritmus (ten proběhne po každém umístěném kamenu):

• Vem souřadnici posledního umístěného kamene (i,j)
• Dokud nenajdeš výherní posloupnost nebo dokud se neujistíš, že v žádném ze čtyř směrů taková (obsahující poslední umístěný kámen) není
• Pro daný směr ověř, zda v něm není výherní posloupnost (směry jsou: hrizontální, vertikální a dva diagonální).

Realizace algoritmu pro směr NS

Předpokládejme, že chceme napsat část programu pro detekci výherní posloupnosti směrem NS.

Souřadnici posledního umístěného kamene máme v proměnných r, s (radek, sloupec). Jádrem hledání je cyklus (dokud nalézám daným směrem stejné kameny). Zavedeme si novou proměnnou hledatdal, která bude mít hodnotu true v případě, že má smysl posun na další políčko směrem N. V opačném případě se nastaví na hodnotu false a hledání daným směrem bude ukončeno. Na začátku nastavíme hodnotu hledatdal na true (předpokládáme, že hledání bude mít smysl).

    //(stejne kameny smerem nahoru)
    hledatdal:=true;
    while (hledatdal=true) do
    begin

    end;
  			

V cyklu while potřebujeme ověřit, zda je nad posledním položeným kamenem (r,s) další kámen stejného typu. Vzhledem k tomu, že si potřebujeme pamatovat, který kámen byl poslední položený, tak si vytvoříme dvě pomocné proměnné pomr a poms, které budou postupně obsahovat souřadnice polí ve hře, která budeme procházet. Na začátku je nastavíme na stejné souřadnice jako má poslední umístěný kámen - tím je určen výchozí bod.

    //(stejne kameny smerem nahoru)
    hledatdal:=true;
    pomr:=r;
    poms:=s;
    while (hledatdal=true) do
    begin

    end;
  			

V těle cyklu se musíme postupně přesouvat směrem N. Je tedy nutno v každém průchodu odečítat jedničku od souřadnice řádku (pomr).

    //(stejne kameny smerem nahoru)
    hledatdal:=true;
    pomr:=r;
    poms:=s;
    while (hledatdal=true) do
    begin
      pomr:=pomr-1;

    end;
  			

Abychom se mohli zeptat, zda je na políčku (pomr, poms) stejný kámen, tak je nejprve potřeba ověřit, že takové pole vůbec existuje (mohli bychom se dostat mimo hrací plochu - to by se v konečném počtu kroků jistě mohlo stát). Položíme tedy nejprve programu dotaz, zda je nová souřadnice řádku pro zkoumání větší než nula (pole má rozměr 1..m, 1..n). Kdyby se stalo, že pomr bude nula, tak to znamená, že jsme mimo rozsah a tím pádem také nemá smysl dál hledat daným směrem (nastavíme hledatdal na false).

    pocetkamenu:= 1; //posledni vlozeny kamen
    //(stejne kameny smerem nahoru)
    hledatdal:=true;
    pomr:=r;
    poms:=s;
    while (hledatdal=true) do
    begin
      pomr:=pomr-1;
      if (pomr>0) then
      begin

      end
      else
  	    hledatdal:=false;
    end;
  			

Pokud narazíme na konec pole, tak je situace jasná. Zbývá vyřešit situaci, kdy se na souřadnicích (pomr, poms) nachází hrací pole a analyzovat jeho obsah (pole může mít tři hodnoty: kámen X, kámen O a prázdné pole). Typ kamene, který byl umístěn jako poslední máme v proměnné typkamene a tak můžeme jednoduše porovnat obsah políčka s posledním umístěným kamenem (r,s) a testovaným polem (pomr, poms). Pokud nastane shoda, tak má smysl pokračovat počítání kamenů v posloupnosti stejných kamenů (proměnná pocetkamenu). Tuto proměnnou nastavíme na jedničku (poslední položený kámen tvoří posloupnost kamenů délky jedna). Jakmile se dopočítáme číska delka, tak nastala výhra.

    pocetkamenu:= 1; //posledni vlozeny kamen
    //(stejne kameny smerem nahoru)
    hledatdal:=true;
    pomr:=r;
    poms:=s;
    while (hledatdal=true) do
    begin
      pomr:=pomr-1;
      if (pomr>0) then
      begin
        if (p[pomr,poms]=typkamene) then pocetkamenu:=pocetkamenu+1
        else
	    hledatdal:=false
      end
      else
  	    hledatdal:=false;
    end;
  			

Uvedený kód spočítá počet stejných kamenů severním směrem od posledního položeného kamene a skončí. Co pak? Následně je nutno provést stejný postup pro kameny POD posledním položeným kamenem. Oběma směry (N i S) se sečte počet nalezených kamenů daného typu (typkamene). Pokud bude výsledné číslo alespoň tak velké jako nutný počet kamenů pro výhru (proměnná delka), tak jsme našli výherní posloupnost a hra končí. Přidáme do programu podobný kód ještě jednou (měníme pouze nastavení poroměnné pomr, kterou postupně inkrementujeme a nebudeme znovu nastavovat proměnnou pocetkamenu - ta se bude případně jen zvětšovat).

    //(stejne kameny smerem dolů)
    hledatdal:=true;
    pomr:=r;
    poms:=s;
    while (hledatdal=true) do
    begin
      pomr:=pomr+1;
      if (pomr>0) then
      begin
        if (p[pomr,poms]=typkamene) then pocetkamenu:=pocetkamenu+1
        else
	    hledatdal:=false
      end
      else
  	    hledatdal:=false;
    end;
  			

Zbývá test na délku nalezené posloupnosti stejných kamenů bezprostředně za sebou a případný konec hry (využijeme proměnnou konec:boolean).

	   if (pocetkamenu>=delka) then konec:=true;
  			

V tento moment je algoritmus detekce konce hry pro směr NS hotov. Zbývá dokončit zbylé tři varianty a zakomponovat do nich případný konec hry (nemá smysl hledat výherní posloupnost v další směru, pokud už byla v některém předchozím nalezena).

Domácí úkol

Dokončete celou hru a odlaďte výsledný program tak, aby korektně fungoval.

Další čtení