| Form of studies |
Master |
| Title of the study programm |
Intelligent robotic systems |
| Title in original language |
Spēles koka pārmeklēšanas algoritmu optimizācija, izmantojot stāvokļu simetriju un jaucējfunkciju |
| Title in English |
Optimizing Game Tree Search Algorithms Using State Symmetry and Hash Function Techniques |
| Department |
Faculty Of Computer Science Information Tehnology And Energy |
| Scientific advisor |
Egons Lavendelis |
| Reviewer |
Alla Anohina-Naumeca |
| Abstract |
Maģistra darbā tiek pētītas spēles koka optimizācijas iespējas, izmantojot spēles stāvokļu simetrijas īpašības. Tika izstrādāta modulāra eksperimentālā vide, kas ļauj novērtēt dažādas optimizācijas pieejas, tostarp dublēto stāvokļu filtrēšanu un pilnas simetrijas filtrēšanu. Pētījuma pirmajā daļā veikta vispārīga simetrisko transformāciju efektivitātes analīze vairākos spēles laukuma izmēros, salīdzinot dažādus filtrēšanas līmeņus un to ietekmi uz ģenerēto stāvokļu skaitu un atmiņas patēriņu.
Darba otrajā daļā izstrādāta metode simetrijas filtrēšanas integrēšanai divos klasiskos meklēšanas algoritmos – Minimax un Monte Carlo Tree Search, pielāgojot to struktūru simetrisko stāvokļu atpazīšanai un atkārtojumu novēršanai. Tika veikts salīdzinošs eksperiments ar un bez simetrijas optimizācijas, novērtējot abu variantu darbības efektivitāti.
Rezultāti liecina, ka simetrijas izmantošana ievērojami samazina dublēto stāvokļu skaitu, būtiski optimizējot atmiņas patēriņu, un noteiktos gadījumos arī paātrina algoritmu darbību. Darba noslēgumā tiek izcelts potenciāls turpmākai attīstībai, tostarp simetriju-invariantas jaucējfunkcijas izstrādei, kas ļautu identificēt līdzvērtīgus stāvokļus bez papildus transformāciju ģenerēšanas |
| Keywords |
spēles koks, simetrija, jaucējfunkcija, Zobrist, stāvokļu optimizācija, Minimax, MCTS |
| Keywords in English |
game tree, symmetry, hash function, Zobrist hashing, state optimization, Minimax, MCTS |
| Language |
lv |
| Year |
2025 |
| Date and time of uploading |
27.05.2025 22:03:26 |
