Arimaa challenge - comparission study of MCTS versus alpha-beta methods

• Název práce v češtině: Arimaa challenge - comparission study of MCTS versus alpha-beta methods
• Název v anglickém jazyce: Arimaa challenge - comparission study of MCTS versus alpha-beta methods
• Klíčová slova: Arimaa, Monte Carlo Tree Search, alpha, beta, abstraktní strategická hra
• Klíčová slova anglicky: Arimaa, Monte Carlo Tree Search, alpha, beta, abstract strategy game
• Akademický rok vypsání: 2010/2011
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: Mgr. Vladan Majerech, Dr.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 02.03.2011
• Datum zadání: 02.03.2011
• Datum a čas obhajoby: 07.09.2011 09:00
• Datum odevzdání elektronické podoby: 05.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 07.09.2011
• Oponenti: RNDr. Jan Hric

Zásady pro vypracování

Statická vyhodnocovací funkce je jedním z nejdůležitějších prvků ovlivňujících kvalitu hry počítače. Počítačové programy hrající arimaa jsou založeny převážně na alpha-beta prohledávání či na Monte Carlo prohledávání. Práce by se měla věnovat srovnání obou metod při používání stejných statických ohodnocovacích funkcí.

Seznam odborné literatury

[1] Omar Syed: Arimaa: "A New Game Designed to be Difficult for Computers", ICGA Journal Vol. 26, No.2, pp.138-139. http://arimaa.com/arimaa/papers/030801ICGA/
[2] Tomáš Kozelek: "Methods of MCTS and the game Arimaa Master's thesis", Charles University in Prague
Faculty of Mathematics and Physics (2009), http://arimaa.com/arimaa/papers/TomasKozelekThesis/mt.pdf
[3] David Fotland: "Building a World Champion Arimaa Program" CG 2004, LNCS 3846 (2006) 175-186 http://arimaa.com/arimaa/papers/Fotland/CGC2004/Arimaa_paper.doc
[4] Haizhi Zhong: "Building a Strong Arimaa-playing Program" Master's thesis, University
of Alberta, Dept. of Computing Science (September 2005) http://arimaa.com/arimaa/papers/HaizhiThesis/haizhiThesis.doc
[5] Christ-Jan Cox: "Analysis and Implementation of the Game Arimaa" Master's thesis,
Universiteit Masstricht, Institute for Knowledge and Agent Technology (March
2006) http://arimaa.com/arimaa/papers/CoxThesis/Cox_thesis1.pdf a http://arimaa.com/arimaa/papers/CoxThesis/Cox_thesis2.pdf
[6] Stefano Carlini: Arimaa: "From Rules to Bitboard analysys" Knowledge Representation Thesis, University of Modena and Reggio Emilia (December 2008) http://arimaa.com/arimaa/papers/StefanoCarlini/Arimaa.pdf
[7] Gerhard Trippen: "Plans, Patterns and Move Categories Guiding a
Highly Selective Search" (presented at the 2009 Advances in Computer Games 12 confrence, Pamplona, Spain) (May 2009) http://arimaa.com/arimaa/papers/0905Trippen/Contribution118.pdf

Předběžná náplň práce

Poté, kdy počítačové programy začaly porážet nejlepší lidské hráče, vytvořil Omar Sayed pravidla hry rozměrově srovnatelnou s šachama, s pravidly, která by měla velice znesnadňovat tvorbu dobře hrajících počítačových programů. Vypsal cenu Arimaa challenge, za vytvoření programu, který bude porážet nejlepší lidské hráče v této hře. Od té doby se lidští hráči dlouhou dobu zlepšovali daleko rychleji než počítačové programy. V poslední době se ale zdá, že se hra nejlepších počítačových programů hře nejlších hráčů začíná mírně přibližovat.
Upoutávka v anglickém jazyce

Předběžná náplň práce v anglickém jazyce

When best human players were defended by the best computer players of chess, Omar Sayed developed game of size simillar to chess, with rules, which should made development of computer programs plying it very complicated. He set Arimaa challenge for development of the computer program which can defeat best human players in this game. The playing skills of the best human players improved much faster than the computer program skills for a long time. Recently it seems that the skills of the best computer programs started slowly approach the skills of the best human players.