Naslov
Izrada šahovskog engine-a
(Construction of a Chess Engine)

Autori
Jokić, Jovan

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Odjel za informatiku

Mjesto
Rijeka

Datum
25.09

Godina
2014

Stranica
72

Mentor
Martinčić - Ipšić, Sanda

Ključne riječi
šah; engine; generator poteza; algoritam pretrage; evaluacijska funkcija; minimax; ALFA-BETA; quiescence pretraga; Late Move Reductions (LMR); Principal Variation Search (PVS); null-potez; heuristika; hash; transpozicija; aspired pretraga; history; tropizam
(chess engine; move generator; search algorithm; evaluation function; minimax; ALFA-BETA; quiescence search; Late Move Reductions (LMR); Principal Variation Search (PVS); null-move; heuristics; hash; transposition; aspired search; Memory-enhanced Test Driver with node n and value f (MTD(f)); history; tropism)

Sažetak
Teorijski temelji i saznanja o računalnom šahu razvijaju se više od 50 godina. Počevši s prvim dediciranim i posebno-namijenjenim šahovskim sustavima koji su imali snagu slabijih klupskih igrača, te bili realizirani u, kako u softverskom, tako i u sklopovskom izdanju, šahovski računalni sustavi i komponente su, u međuvremenu, značajno unaprijeđene. U današnje doba, dostupan je velik broj računalnih programa koji igraju šah, tzv. engine-a, na velikom broju platformi i računalnih arhitektura, uključujući i pametne telefone i ostale embedded platforme, od kojih su mnogi u stanju pobjediti i ponajbolje šahovske igrače današnjice. U ovom završnom radu analizirane su i dokumentirane sve vodeće teoretske tehnike i metode, odn. strategije uključene u razvoj tipičnog šahovskog engine-a. Teorijski gledano, osnovne, esencijalne komponente svakog šahovskog engine-a: generator poteza, evaluacijska funkcija i algoritam pretraživanja stabla igre su prezentirane, kao i različite strategije i ideje u praktičnom smislu vezane uz tu problematiku.Uvodi se pojam kombinatorne eksplozije, te analizira način premošćivanja tog problema koji, u osnovi, predstavlja ključnu ideju iza realizacije gotovo svih današnjih šahovskih engine-a. Dodatno, opisane su i određene tehnike unaprijeđenja tih ideja, ponajprije algoritma ALFA-BETA pretraživanja stabla stabla igre, poput Principal Variation Search (PVS) tehnike, Late Move Reductions (LMR), te niza ostalih posebnih heurističkih metoda čiji je cilj maksimalno skratiti prostor pretrage, te ga maksimalno usmjeriti, čime se omogućuje u praktičnom smislu izrada vrlo jakih i sofisticiranih engine-a. U praktičnom pogledu, dokumentira se i opisuje dizajn i implementacija didaktičkog šahovskog sustava, tj. Engine-a Vice, autora BlueFeverSoft, te uvode 2 konkretna poboljšanja ; PVS s LMR heuristikom u ALFA-BETA algoritmu pretraživanja svih mogućih poteza iz ishodišne pozicije nastale na ploči u tijeku igre.Drugo poboljšanje odnosi se na statičku evaluacijsku funkciju za procjenu trenutno nastale pozicije na ploči s aspekta igrača koji je trenutno na potezu. Kako Vice ima razmjerno trivijalnu evaluacijsku funkciju i nema mehanizam procjene sigurnosti kralja, uvodi se mjera tropizma kralja kao surogatno obilježje ukupne sigurnosti kralja od napada protivničkih figura.Također, osmišljena je odgovarajuća testna metodologija kojom se ispitao utjecaj navedenih poboljšanja u internom radu Vice engine-a, te naposljetku, nakon potrebnih testiranja, rezimira se posljedični značaj tih testova i daje zaključak na temelju pribavljenih empirijskih rezultata testova.Naposljetku, u završnom dijelu rada prikazano je što je tijekom rada otkriveno, koje su bile poteškoće u radu te koja su nova pitanja otvorena relevantna za domenu računalnog šaha. Ukratko je dana procjena učinkovitosti implementacije dodatnih poboljšanja u praktičnom smislu Vice šahovskog sustava, te su analizirane prednosti i nedostaci odabranog pristupa. 

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo, Informacijske i komunikacijske znanosti

POVEZANOST RADA