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/11/15 22:59] 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: ===== | ===== Jak na to: ===== | ||
| Řádek 24: | Řádek 24: | ||
| * Bílý hráč zvolí radši neurčito před patem | * Bílý hráč zvolí radši neurčito před patem | ||
| * Když někde výhra probublá až nahoru, končíme algoritmus | * Když někde výhra probublá až nahoru, končíme algoritmus | ||
| - | |||
| ==== Implementace ==== | ==== Implementace ==== | ||
| Závisí na ukládání situací (uzlů): | 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 | + | * 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 | * nebo lze celá situace zakódovat binárně do jednoho intu | ||
| Řádek 47: | Řádek 46: | ||
| int BK=9,BV=23,Bp=7,CK=6,CV=40,mutace=0; | int BK=9,BV=23,Bp=7,CK=6,CV=40,mutace=0; | ||
| //Naskládám to tam odzadu | //Naskládám to tam odzadu | ||
| - | //Posun o 6 pozic tu je proto, že do 6 pozic nacpu číslo velké 0..63(šachovnice má -1..48) | + | //Posun o 6 pozic tu je proto, že do 6 pozic nacpu číslo velké 0..63(šachovnice má 0..48,49) |
| int hash = mutace; | int hash = mutace; | ||
| hash = (hash<<6) | BK; | hash = (hash<<6) | BK; | ||
| Řádek 71: | Řádek 70: | ||
| * 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. | * 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) | * 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) | ||
| Řádek 82: | Řádek 83: | ||
| 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. | 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~~ | ~~DISCUSSION~~ | ||
