====== Úloha 3 ======

Šachová koncovka

[[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=sachy|Zadání]]

Limit: variabilní od 1s do 25s

===== Jak na to: =====
==== Overview ====
  * 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
==== Implementace ====
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 49x49 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ší)

== Hash ==
 
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 


== Generator tahů ==
 
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.


== Generator tahů /poznamka/ ==

No a hele tak jsem ohledne toho generovani tahu nasel neco v odkazu ze zadani [[http://chessprogramming.wikispaces.com/General+Setwise+Operations|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:
{{:courses:a4m33pal:screen_shot_2010-11-18_at_1.36.03_am.png|}}

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



~~DISCUSSION~~