Proof-number search based solver for the Sprouts game

• Název práce v češtině: Řešič pro hru Sprouts založený na algoritmu Proof-number search
• Název v anglickém jazyce: Proof-number search based solver for the Sprouts game
• Klíčová slova: Sprouts|Nestranné hry|Proof-number search|Paralelní výpočty
• Klíčová slova anglicky: Sprouts|Impartial games|Proof-number search|Parallel computing
• Akademický rok vypsání: 2022/2023
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Schmid, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 01.03.2023
• Datum zadání: 01.03.2023
• Datum potvrzení stud. oddělením: 07.12.2023
• Datum a čas obhajoby: 10.09.2024 09:00
• Datum odevzdání elektronické podoby: 17.07.2024
• Datum odevzdání tištěné podoby: 18.07.2024
• Datum proběhlé obhajoby: 10.09.2024
• Oponenti: Mgr. Vladan Majerech, Dr.
• Konzultanti: doc. RNDr. Martin Balko, Ph.D.

Zásady pro vypracování

Cílem práce je vylepšit state-of-the-art řešič pro kombinatorickou hru Sprouts a tím získat nové výsledky pro dosud nevyřešené pozice.
Součástí bude implementace a porovnání různých řešících technik jako je Alpha-beta pruning nebo Proof-number search v kombinaci s metodami strojového učení.
Další částí bude navržené techniky upravit pro možnost paralelního výpočtu na cloudu.
Závěrem se student pokusí prozkoumané techniky zobecnit na další problémy.

Seznam odborné literatury

- Lemoine, J., and Viennot, S.: Computer analysis of Sprouts with nimbers. Games of no chance 4, 161–181, Math. Sci. Res. Inst. Publ., 63, Cambridge Univ. Press, New York, 2015.

- L. Victor Allis, Maarten van der Meulen, H.Jaap van den Herik: Proof-number search. Artificial Intelligence, Volume 66, Issue 1, 1994, Pages 91-124.

- Saito, Jahn-Takeshi & Winands, Mark & Herik, H.. (2010). Randomized Parallel Proof-Number Search. Journal of Intellectual Disability Research - J INTELLECT DISABIL RES. 6048. 75-87.