Kabe mängimine arvutiga

Tere,

Tegin hiljuti male mängimise arvutiga, mis on osutunud väga populaarseks - iga päev mängitakse keskmiselt üle 300 partii arvutiga.

Hakkasin nüüd uurima, mis võimalused on sama teha kabes (eelkõige vene kabes). 
Ja tundub, et nii lihtsalt (kui malega) see ei lähe - puudub programm, mis jookseks linuxil ja millel oleks API, kuhu seis ette anda ja mis annab parima käigu vastu (nagu stockfish seda teeb).
Minu info kabeprogrammidest pärineb fmjd lehelt. Sealt on näha, et linuxil jooksvaid vene kabe programme näiteks polegi.

Mis võimalused siis on?
Vindis on mängitud 1.1 miljonit vene kabe partiid. Ja meil on kõikide nende partiide käigud salvestatud (kokku on neid üle 70 miljoni!).
Võimalus on panna vindi robot mängima, kasutades seda käikude andmebaasi. 
Põhiline väljakutse selle lahenduse juures on salvestada laua seis iga käigu juurde ja siis mängu ajal võimalikult kiiresti see seis üles leida ja siis vastav käik teha. Ja kui on täiesti uus seis, tuleb teha esimene ettejuhtuv/juhuslik käik.

See kõik on tõenäoliselt tehtav (see kiire käigu leidmine 70 miljoni kirje seast on natuke küsitav kuid eks seda saab teada kui katsetada) kuid päris tõsine ja aeganõudev projekt.

Ehk on mõni kabehuviline lähitulevikus ülikooli informaatika eriala lõpetamas? See projekt sobiks väga hästi bakalaureuse/magistritööks.






 

Äraandmist saab juba arvutiga mängida, minge proovige! Arvuti hetkel veel areneb (analüüsib mängitud partiisid).

Nüüd aga natuke lahendusest ja numbritest.
Lahenduse võtsin sarnase nagu eelmises postituses kirjeldasin: arvuti mängib läbi kõik partiid, paneb kõik seisud ja nendest seisudest tehtud käigud andmebaasi.
Ta jätab vahele sundkäigud (löögid) ning üritab hinnata ka igat käiku (sõltuvalt partii lõpptulemusest).

Äraandmise mänge on meil andmebaasis 150000, esimese ööpävaga analüüsis arvuti läbi 40000 mängu. Ja analüüsimune jääb järjest aeglasemaks (sest mängu seisude ja käikude andmebaas kasvab järjest). Eks näeme kaua aega 150K mängu läbitöötamiseks läheb ja kui hästi arvuti mängima hakkab.
Näiteks pärast esimest 20K partii läbimängimist vastas arvuti valge gh4 käigule bc5 mis on suht kaotav käik. Aga pärast 40K partii läbimängimist käis juba paremini.
Teoreetiliselt saame tekitada ka erinevaid raskusastmeid kuid eks näeme.

See on nüüd äraandmise kohta. Vene kabe mänge on meil 8x rohkem mis hetkeprognoosi kohaselt tähendab, et server analüüsib neid mänge mitu nädalat. Aga jõuame sinna kui äraandmine tehtud ja mingid tulemused käes.

Positiivne poole pealt - see analüüs võtab u. 25% serveri resurssidest ja ülejäänud portaal toimib normaalselt edasi.

Jutustan siin edasi.

Iga käik saab hinde: Kui lõpuks selle käigu tegija võidab partii (puhtalt mänguga), saab käik +3 punkti, ajaületus/ vastane lahkus mängust annab ühe punkti ja kaotus siis vastavalt -3 ja -1 punkti.

Samadel käikudel siis punktid liidetakse kokku.
Lisaks salvestatakse käigu juurde selle populaarsus (mitu korda on seda käiku sellest seisust tehtud).

Hetkel valib arvuti suurima skooriga käigu.

Ja üks asi hakkas mind häirima, mainisin ka seda ka eelmises postituses: hetkel vastab arvuti valge gh4-le bc5 mis on väga halb käik.
Uurisin siis erinevate käikude skoore pärast valge gh4-ja ja nägin huvitavat tulemust (pilt manuses). Nimelt on kõik skoorid (grade) sellest seisust negatiivsed. Ehk statistiliselt on valge juba võitnud . Ja nüüd üks statistiline anomaalia: kuna väga halbu käike (näiteks bc5) on tehtud väga vähe, on nende absoluutne skoor kõige kõrgem ja seetõttu arvuti neid hetkel valib.

Mõtisklesin tükk aega, mida teha. Ja lahendus on päris huvitav: Nimelt absoluutse skoori asemel peaksin võtma kaalutud skoori (grade / popularity). See valem annab parimaks käiguks fg5, mis on ka kõige mõistlikum käik sellest seisust.
Selle muudatuse viin sisse nädala lõpuks, hetkel veel käikude analüüs käib.

Tundub, et analüüs käib hetkel tempos 10 mängu minutis. Analüüsida on veel 90000 mängu, ehk aega kulub veel 9000 minutit ehk 6+ ööpäeva. See omakorda tähendab, et vene kabe käike analüüsib server reaalselt paar kuud. Aga las analüüsib. mingi hetk panen vene kabe arvuti vastu mängimise üles, alguses mängib arvuti kehvasti, pärast paremini.

Natuke numbreid ka: Analüüsitud on 59 000 mängu, andmebaasis on:

• 1.1 miljonit unikaalset seisu
• 1.2 miljonit unikaalset käiku

Üks asi veel, mida kõrva taha panna: Äraandmises on valgel korralik eelis, seega soovitan mängida mikromatše!

 

Nonii, andmebaasid oli üks indeks puudu, lisasin selle.

Kui enne analüüsiti üks mäng 7 sekundi jooksul siis nüüd analüüsitakse 5 mängu sekundis. Asi läks 30-40 korda kiiremaks!

Tänasest mängib arvuti veidi paremini:

* Lisasin andmebaasi ka kõik seisud, kust saab mitut moodi lüüa (enne neid baasis ei olnud).
* Kui baasis käiku ei ole, analüüsib nüüd arvuti kõik käigud läbi (rekursiivselt kuni sundkäigud/löögid lõppevad) ja loeb lõpus nupud kokku. 1 kabe = 3 kivi (äkki peaks mingi teine hind kabel olema)?

Nüüd edasi tuleb teha sama asi äraandmises. Ja lisaks panen arvuti enda käikudest ka õppima. kui ta ikka ühte liini pidi kogu aeg kaotab, äkki hakkab siis mingi hetk teisi käike eelistama.

Tänasest õpib arvuti ka enda käikudest (salvestab enda käikude info andmebaasi).

Viigi pakkumise võimaluse võtsin ka arvutiga mängimisel ära - nägin eile kuidas kasutaja selgest kaotusseisust pakkus arvutile viiki. Ja arvuti võtab kõik pakkumised vastu. See rikub veidi käikude hindamist.

Aga tuli veel üks mõte - kui andmebaasis on kõik käigud mingis seisus negatiivse skooriga (neid käike tehes ootab ees kaotus) võiks arvuti proovida neid käike, mida andmebaasis veel ei ole - äkki on ikkagi mingi võiduvariant olemas?

ära-andmises on kindel loogika, äkki peaks arvuti esmalt õppima kuuidas 1 nupule kõik vastase nupud saab ära anda, see oskus on ülioluline edaspidises mängu praktikas.