Stalo žaidimo dirbtinio intelekto kūrimas naudojant Monte Karlo paiešką

Ištrauka

Informacinių technologijų bakalaurinis darbas
Stalo žaidimo dirbtinio intelekto kūrimas naudojant Monte Karlo paiešką

Turinys
Sutartinis terminų žodynas 4
Santrauka 5
Summary 6
Įvadas 7
1. Šachmatų žaidimo jgyvendinimas 8
1.1. "Crazyhouse" varianto taisyklės 8
1.2. Projekto struktūra 8
1.3. Taisyklių įgyvendinimas 9
1.3.1. Leidžiamų ėjimų radimas 9
1.3.2. Ėjimo atlikimas 12
1.3.3. Lentos išsaugojimo formato įgyvendinimas 13
1.4. Sujungimas su "Stockfish" 14
1.5. Sąsajos 14
1.5.1. Sąsaja terminale 14
1.5.2. Grafinė sąsaja 15
2. Minimax paieška ir patobulinimai 16
2.1. Teorija 16
2.2. Paieškos funkcija 17
2.2.1. Alfa-beta paieška 17
2.2.2. Lentelės, skirtos saugoti įvertintas šakas 19
2.2.3. Ėjimų rikiavimas bei iteracinis gylio didinimas 21
2.3. Vertinimo funkcija 22
2.3.1. Figūrų vertės 22
2.3.2. Figūros-langelio vertės 22
3. Monte Karlo paieška ir patobulinimai 23
3.1. Teorija 23
3.2. Ėjimo reitingo skaičiavimas 24
3.3. Parinkimo funkcijos patobulinimai 25
3.3.1. UCT formulė 25
3.3.2. Euristinio vertinimo taikymas 26
3.3.3. Matų radimas taikant Minimax 27
3.3.4. Dinaminis tiriamų ėjimų spektro plėtimasis 28
3.4. Simuliacijos patobulinimai 29
3.4.1. Simuliacijos ėjimų pasirinkimas 29
3.4.2. Simuliacijos nutraukimas 31
3.5. Galutinio ėjimo išrinkimas 31
3.6. Daugiagijiškumo galimybių testavimas 32
4. Dirbtinių intelektų stiprumo jvertinimas 33
4.1. Minimax dirbtinio intelekto palyginimas prieš "Stockfish" 33
4.2. Monte Karlo dirbtinio intelekto palyginimas su kitais. . . . . . . . . . . . . . . .34
Išvados 36
Ateities tyrimų planas 37
Literatūros šaltiniai 38

Įvadas
Nuo pat kompiuterijos mokslo pradžios buvo siekis sukurti kompiuterius, galinčius pranokti
žmonės įvairiuose stalo žaidimuose. Istorijoje ypač yra įsimintini du atvejai, kurie buvo kulmi-
nacija keleto dešimtmečių pastangų įveikti žmones ten, kur buvo laikyta, jog kompiuteriai negali
aplenkti žmogaus kūrybiškumo. Pirmasis iš šių atvejų buvo "Deep Blue" 1997 m. pergalė prieš
tuometinį pasaulio šachmatų čempioną Garį Kasparovą [IBM97]. Antroji kulminacija buvo pa-
siekta 2015 m., kai "AlphaGo" įveikė stipriausią Go žaidėją Lee Se-dolį. [Goo15]
Nepaisant nemažai panašumų tarp šių įvykių istorine prasme, iš techninės pusės tai buvo
labai skirtingi pasiekimai. 1997 m. pergalė šachmatuose buvo rezultatas dešimtmečius
tobulėjančių galimybių vis efektyviau ir greičiau perrinkti įvairias pozicijas Minimax algoritmu,
pranokusiu visus kitus algoritmus, ir iš jų išrinkti geriausią ėjimą. Tuo tarpu "AlphaGo"
pasiekimas 2015 m. buvo klasikinės Monte Karlo paieškos bei naujos neuroninių tinklų
technologijos mišinio debiu- tas. [Fu16]
Patobulėjus kompiuteriams atsirado galimybė šachmatus žaisti internetu ir dėl šios priežasties
išpopuliarėjo "Crazyhouse" variantas [Lic16]. Šio varianto esmė pasiskolinta iš japoniškų šach-
matų šogio ir yra ta, jog nukirtus varžovo figūrą, ją galima savo ėjimo metu pastatyti bet kuriame
lentos langelyje. Šis pakeitimas padaro ši variantą gerokai dinamiškesnį už paprastus šachmatus.
Šiame darbe buvo siekiama išsiaiškinti ar yra įmanoma sukurti Monte Karlo paieška grįstą
dirbtinį intelektą, kuris galėtų taip pat gerai žaisti šachmatais, kaip ir ilgą laiką dominavęs Mini-
max. Taip pat buvo siekta išsiaiškinti ar šis algoritmas galėtų žaisti ganėtinai naują "Crazyhouse"
šachmatų variantą. Šio darbo tikslas buvo sukurti kuo geriau "Crazyhouse" šachmatų
varian- tą žaidžiantj ir Monte Karlo paiešką taikantj dirbtinj intelektą, ir ištirti jo
stiprumą. Tam buvo apibrėžti tokie darbo uždaviniai:
1. Sukurti programą, kuria būtų galima žaisti šachmatais pagal "Crazyhouse" varianto taisykles.
2. Sukurti Minimax algoritmą taikantį dirbtinį intelektą, kuris būtų varžovas Monte Karlo paieškos intelektui.
3. Sukurti Monte Karlo paiešką taikantį dirbtinį intelektą.
4. Stiprinti abiejų sukurtų dirbtinių intelektų žaidimo kokybę, juos lyginant tarpusavyje, prieš
senąsias savo versijas, bei prieš stiprią šachmatais žaidžiančią programą "Stockfish".
Šio darbo metu buvo sukurti du dirbtiniai intelektai, kurie buvo lyginami vienas su kitu, kurių
vienas naudoją Monte Karlo paiešką su euristiniu vertinimu, taikant ėjimų vertinimą, Minimax
taikymu matams, dinaminiu...