Úloha 3

Šachová koncovka

Zadání

Limit: variabilní od 1s do 25s

• Naprogramujeme generátor všech možných validních tahů všech figur pro danou pozici (viz úloha 3a)
• Naprogramujeme funkci, která vyhodnotí zda je daná pozice pro někoho vítězná (šach mat)
• Vždy vygenerujeme jeden tah, ověříme jestli to není mat a když není tak se rekurzivně zeptáme na další tahy založeném na tomto tahu
• Rekurze končí když:
  • Daná situace je pro někoho vítězná
  • Stejná situace už se opakovala 3x (pat)
  • Jsme v maximální hloubce (neurčité řešení)
• Výstupy z rekurze spojujeme podle pravidel
  • Aktuální hráč zvolí vždy svojí výhru před čímkoli
  • Aktuální hráč zvolí raději neurčito nebo pat před prohrou
  • Pat a pat je pat
  • Neurčito a neurčito je neurčito
  • Černý hráč zvolí radši pat před neurčito
  • Bílý hráč zvolí radši neurčito před patem
• Když někde výhra probublá až nahoru, končíme algoritmus

Závisí na ukládání situací (uzlů):

• figury se dají uložit jako proměnné obsahující číslo 0..48 značící souřadnice, -1 = vyhozená figura (tady by mohl ale asi nastat problém s hashováním dané šachovnice - v té úloze to bude potřeba)
• nebo lze celá situace zakódovat binárně do jednoho intu

Na zrychlení je potřeba mít předgenerované tabulky

• tabulku čísel na souřadnice
• tabulku souřadnic na čísla
• tabulku 49×49 jestli se ohrožuje věž s králem (asi zbytečné, mělo by stačit otestovat, jestli se shoduje sloupec nebo řádek, navíc z tabulky nezjistí, jestli mezi nimi něco není)
• tabulku možných tahů krále pro všechny políčka
• tabulku možných tahů jezdce pro všechny políčka
• (doplňte další)

Na zakodovani celé šachovnice do jednoho integeru v jave (32 bitů) by šlo něco takovýho:

//Čísla označují pozice na na šachovnici 0..6*0..6
//Pořadí jednotlivých figurek se nesmí měnit
//V co je proměněnej pěšák je vyjádřený proměnou mutace - stavy: 
//                 0(nic),1(dama),2(jezdec)   //Poupraveno - nesmí měnit na střelce
int BK=9,BV=23,Bp=7,CK=6,CV=40,mutace=0;
//Naskládám to tam odzadu
//Posun o 6 pozic tu je proto, že do 6 pozic nacpu číslo velké 0..63(šachovnice má 0..48,49)
int hash = mutace;
hash = (hash<<6) | BK;
hash = (hash<<6) | BV;
hash = (hash<<6) | Bp;
hash = (hash<<6) | CK;
hash = (hash<<6) | CV;

//A pak to zase vyzvednu, je potřeba vyzvedávat v opačném pořadí!
//Maska 63 je v binárním zápisu (26 nul)111111, aby se vytáhlo posledních 6 bitů 
CV = hash & 63;
hash = hash>>>6;
CK = hash & 63;
hash = hash>>>6;
Bp = hash & 63;
hash = hash>>>6;
BV = hash & 63;
hash = hash>>>6;
BK = hash & 63;
hash = hash>>>6;
mutace = hash & 3;

• Problém je v tom, že v Javě jsou všechny typy se znaménkem…tedy první bit ve 32 bitovém intu určuje znaménko a my potřebujem i tenhle bit…takže se bude stávat že výsledný hash bude záporný. Kvůli tomu nemůže výsledný hash označovat index v poli, kam by se hashe ukládali.

• A co treba pouzit 64bit int? Tim by se vyresil problem se znamenkem a navic by se vytvoril prostor pro dalsi zajimave informace (napriklad kdo je na tahu).

• Ono ale stejně mít pole velké jako rozsah intu (2^32) je sebevražda. Neví někdo o nějakém lepším ukládání ? (zřetězený seznam a tak)

• Tahle úloha je dost killer, bylo by fajn to tady dát dohromady

Zkoušel si někdo udělat generátor tahů? Předpokládám že je nemožné ukládat si všechny možný tahy i v závislosti na rozestavění ostatních figurek - jestli blokují políčka. Jak se potom efektivně zjištuje například u střelce kam může a kam ne ?

Jediné co mě napadlo je zkusit cyklit od střelce směrem doleva nahoru, doprava nahoru atd. dokud nenarazí na jinou figurku/konec šachovnice. Tohle by šlo ještě vylepšit tím, že by se rovnou v poli reprezentujícím šachovnici označili pozice ostatních figurek a při tom cyklení by se jen koukalo jestli se nenarazilo na označený pole - odpadnou tak v nejhorším případě 4 testy na každé pole, bude je 1 test.

No a hele tak jsem ohledne toho generovani tahu nasel neco v odkazu ze zadani tady , a napadlo mne, co teda udelat pro kazdou figurku boolean pole 14*14, ktery by se vzdycky posadilo na sachovnici tak, aby byla figurka na svym miste, cimz (po odecteni pripadu kde je neco v ceste) dostanem rovnou vsechny pozice figurky po tahu reprezentovany jednickou na sachovnici:

Pro pouziti v tomhle pripade by se jeste matice dala preskladat do pole (protoze sachovnice se reprezentuje vlastne v poli) a delat logickej and nad dvema polema..

Co myslite? nebo nekdo pouziva nejakej lepsi zpusob? JaRda