Úloha 3

Šachová koncovka

Provizorní zadání

Limit: ?s

• 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
• 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
• tabulku možných tahů krále pro všechny políčka
• tabulku možných tahů koně pro všechny políčka
• (doplňte další)