navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha3-2010 [2010/10/28 12:48] redtop |
courses:a4m33pal:uloha3-2010 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 3: | Řádek 3: | ||
| Šachová koncovka | Šachová koncovka | ||
| - | [[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/cviceni/chessassignment2.pdf|Provizorní zadání]] | + | [[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=sachy|Zadání]] |
| - | Limit: ?s | + | 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 | ||
| - | Jak na to: | ||
