download (150 Kb) including source code (Pascal 6)
Sorry, description only in czech
I kdyz me mozi za to titulovali jako silence nebo
podobne, tak sem si zvolil vytvorit sachy. No co bych dodaval , stravil sem na
tom bezesnej mesic a vetsinou je porazi i muj 12 letej bracha , ale
zaplatpanbuch ze hrajou a hlavne ze sem za ne dostal plnej pocet bodu . Takze ,
jestli si chcete shodit sebevedomi ze vas porazi program , kterej bezne porazi
osoba s IQ asi 75 tak to muzete zkusit.
Tady ty kecy dole pod tim , to je dokumentace ,kterou
sem k tomu byl nucenej napsat, takze se pravdepodobne budete muset hodne nudit
,abyste to precetli a navic tam blbne diakritika.
TROCHA TEORIE
Pøi tvorbe svého programu
jsem záhy zjistil , ~.e sem jaksi pøecenil své síly
a ~.e stvoøit a.achy které by hrály alespoò o
trochu lépe ne~. sedmileté dítì není
tak lehké. Nicménì sem se sna~.il , aby respektovaly
pravidla a tahy nebyli zase tak ùplnì nelogické. K
návodu na na poèítaèové a.achy sem vyu~.il
vedomosti z http://www.xs4all.nl/~verhelst/chess/programming.html
, které mì jenom utvrdili v obti~.nosti problému. Doporuèene
postupy se pøevá~.nì sestavají z bitových
operací ,které sice umo~.òují mnohem vìta.í
rychlost a tedy hloubku prohledáváni , ale na druhou stranu
jsou znacnì nepøehledné a te~.ko pochopitelné,
proto sem zvolil pomalejsi ,ale pro mì srozumitelné "normální"
algogoritmy. Dle teorie, a.achový program pracuje na principu
prohledávání stromu øea.ení va.ech mo~.ných
tahù. Bohu~.el se ale tento strom rozrustá exponenciálnì
s hloubkou prohledávání stromu,tak~.e pøi prùmìru
35 mo~.ností na jeden tah se velmi brzo dostaneme k nepøíjemným
hodnotám ,napø. pro prohledáváni 2 tahy do
hloubky máme okolo 1 milionu mo~.ností a pro 3 tahy
ji~. okolo 1 miliardy , co~. doká~.e zahltit i ten nejvýkonìja.í
poèítaè.
1) Minimaxing
První zpùsob spoèívá
ve vyu~.ítí "brutální síly" a prohledává
va.echny mo~.né varianty pomocí rekurzní smyèky
která v~.dy ohodnotí hodnotu provedeného tahu. Aby
se odlia.ily vaa.e tahy od poèítaèe ,tak se v~.dy výsledek
hluba.ího tahu zneguje. Napø. pokud budu hledat do hloubky
1 tahu tak se provede vzdy jeden tah poèítaèe a z
nej se rekurzivnì vola ta samá smyèka ale s opaènou
barvou,která provede va.echny mo~.né tahy soupeøe a
ohodnotí je a vybere ten tah s nejvìta.í hodnotou a
vratí tuto hodnotu mateøské smyèce ,ale se
znaménkem mínus. Nyní se va.e opakuje pro dala.í
tah atd.
2) Alfa Beta search
Je technika zalo~.ená na tom
, ~.e nás nezajímá nejlepa.í tah ,ale staèí
nam "dost dobrej tah", díky èemu~. nemusíme prohledávat
celý strom øea.ení
a pokud máme dobré algoritmy
na øazení výbìru tahù , tak umo~.òuje
za stejný èas prohledat zhruba dvojnásobnou hloubku
ne~. minimax.
Dále existují rùzné
jiné techniky které jea.tì zvya.ují efektivnosti
alfabeta prohledávání jako je napøíklad
porovnáváni provádìních tahù
s temi co jsme ji~. provedli a eliminace opakujicích se pozic (tzv.
Hash Table) , nebo testování pouze nìjakého
urèitého tahu o mìn~. se z nìkých dùvodù
domíváme ,~.e bude velmi úspìa.ný (Killer
heuristic).
PROGRAM
Ve svém programu sem vyu~.il
varianty 1 , proto~.e i kdy~. se to na první pohled nezdá je
u alfabeta prohledávání klíèové
dobré øazení vybíraných tahù
, které je jaksi mimo mé intelektové schopnosti. Program
tedy vyu~.ívá "brutální sílù"
, která je buhu~.el velmi èasovì naøoèná
a ji~. pøi prohledávání do hloubky dvou tahu
, to trvalo prùmìrnì minutu a pùl , co~. se
mi zdá neùnosné a proto sem zkusil pou~.ít nìco
na zpùsob killer heuristik a vybírat pouze ty tahy ,které
se jeví lukrativnì, to znamená upøednostòovat
tahy ve kterých se berou figurky proti ostatním
a také jémné zvýhodnìní tahù
figur oproti pìa.ákùm. Kombinací obou metod
, konkrétnì plného prohledávání
1 tahu a náhodného prohledávání druhého,
sem se dostal do rozumných èasových odezev okolo 20
sekund a relativnì ne tak ùplnì infantilních
tahù. Nicménì nikdo nebrání trpìlivému
tvoru aby si nastavil vìta.í hloubku prohledávání
a dosáhl tak mo~.ná vìta.ích kvalit. V rámci
zachování rozumné slo~.itosti sem se také nepokoua.el
o nìjaké èlenìní fází
hry jako profesionální programi (otevøení,hra
a koncovka) ,pouze pokud uz se na sachovnici maly pocet figurek tak se
automaticky zvysuje hloubka prohledavani, ale i tak kdyz se na sachovnici
nachází ji~. pouze pár posledních figurek ,tak
program jaksi bezcílnì provádí tahy jen aby
nìco dìlal , pokud èirou náhodou nenarazí
na mat (teda dle zkua.enosti ho spía. dostane).
Program lze nastavovat po pùl
tazích , tedy pokue. chceme prohledávání
do hloubky 1 tahu musíme zadat 2 , pokud do 2 tahu tak 4 atd. (teda
víc u~. ani nemá cenu proto~.e u~. pìt trvá 15
minut). Samozøejmì lze zadat i tøeba tøi.
Dále nastavení náhodného
prohledávání. Jediná smysluplná hodnota
je dvì (nebo 0 = vypnuto) ,proto~.e pøi jednièce ,by
se mìlo podle mì dít to samé jako kdy~. se nastavý
normální prohledávání o 1 hlouba. a náhodné
se vypne , proto~.e nahodný vyhlédávání
pracuje na principu ,~.e vybere nìkteré tahy poèítaèe
a k nim prochází V`.ECHNY tahy soupere, tak~.e pokud je to
jedna tak se prochazej pouze va.echny tahy a uspora je nulová . Pøi
vya.a.í hodnotì ne~. 2 je zase jiný problém ,
proto~.e napø. pro tøi se teda vyberou pouze nìjaké
tahy poèítaèe a k nim pouze nìjaké tahy
soupeøe a k nim teprve vsechny tahy pocitace ,tak~.e je pravdìpodobné
~.e se pøehlídne nìjakej zakeønej tah soupeøe(ale
kdo ví mo~.ná to funguje , chce to jenom vyzkoua.et) .
Nastaveni zobrazení prohledávání
stromu sem vyu~.íval hlavnì pro ladìní , ale
ponechal sem ho zde proto~.e je pøece jenom zajimavé prohlédnout
si jak se procházej va.echy tahy a uvìdomit si co va.echno
ten ubohý poèítaè stihne. Lze nastavit buï
na 1 , co~. znamena ~.e se dìsnym fofrem budou míhat figurky
po a.achovnici dokud se neprohledá celý strom (pokud u toho
nechcete stravit mladí tak bych si nastavil hloubku prohledávání
tak max. na 3 ) , nebo na dvì , co~. znamena ~.e po ka~.dém
proa.lém tahu se bude po~.adovat zmáèknout klávesa
(velmi u~.iteèný kdy~. se vychytávaj mouchy), nebo na
tøi , co~. je vypnuto.
Dale k potìa.e oka i ducha disponují
a.achy dvìma velikostma, 200x200 pixelu s velmi schématickými
figurkami (dobré pro ladìní , ale pøi høe
trochu dost nepøehledné), nebo 400x400 s roztomilými
figurkami ,které obìtavì vytvoøil mùj
bratr.
Závìrem : Zkoua.el sem
inteligenci mých a.achù jak s relativnì velkým
okruhem ~.ivých lidí , tak proti jiným programùm.
Zatímco proti poèítaèí to bylo v~.dy
Waterloo , s lidma získaly obèas i òáký
ten skalp.