•      Sign In
• Create Account

### #Actualalvaro

Posted 27 January 2012 - 01:39 PM

You'll only need the ability to undo moves if you use minimax. For MCTS, making moves forward is enough. By generate_moves' I mean a function that creates a list of the available moves in a particular position.

You will not need a database of moves, at least not to get the basic idea working. The UCT algorithm does grow a tree in memory; it's actually fairly easy to implement, but you don't even have to do that to get something working.

As a first version of your bot, make something that explores 1000 times each possible move, finishing the game by playing random moves from there. Then pick the move that won the most times. Once you have that working, you can improve it by using an algorithm called UCB (Upper Confidence Bounds) to explore promising moves more often. Then you can use UCB not only for the current position, but also for positions that have appeared several times in the search, and that's what UCT is (Upper Confidence bounds applied to Trees).

MCTS is a bit random by nature, and you can make it weaker and more random by playing fewer playouts. That's the easy part.

You'll only need the ability to undo moves if you use minimax. For MCTS, making moves forward is enough. By generate_moves' I mean a function that creates a list of the available moves in a particular position.

You will not need a database of moves, at least not to get the basic idea working. The UCT algorithm does grow a tree in memory; it's actually fairly easy to implement, but you don't even have to do that to get something working.

As a first version of your bot, make something that explores 1000 times each possible move, finishing the game by playing random moves from there. Then pick the move that won the most times. Once you have that working, you can improve it by using an algorithm called UCB (Upper Confidence Bound)Bounds) to explore promising moves more often. Then you can use UCB not only for the current position, but also for positions that have appeared several times in the search, and that's what UCT is (Upper Confidence boundbounds applied to Trees).

MCTS is a bit random by nature, and you can make it weaker and more random by playing fewer playouts. That's the easy part. :)[img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

### #1alvaro

Posted 27 January 2012 - 01:37 PM

You'll only need the ability to undo moves if you use minimax. For MCTS, making moves forward is enough. By `generate_moves' I mean a function that creates a list of the available moves in a particular position.

You will not need a database of moves, at least not to get the basic idea working. The UCT algorithm does grow a tree in memory; it's actually fairly easy to implement, but you don't even have to do that to get something working.

As a first version of your bot, make something that explores 1000 times each possible move, finishing the game by playing random moves from there. Then pick the move that won the most times. Once you have that working, you can improve it by using an algorithm called UCB (Upper Confidence Bound) to explore promising moves more often. Then you can use UCB not only for the current position, but also for positions that have appeared several times in the search, and that's what UCT is (Upper Confidence bound applied to Trees).

MCTS is a bit random by nature, and you can make it weaker and more random by playing fewer playouts. That's the easy part.

PARTNERS
Warning: include_once(RContent/redis.php): failed to open stream: No such file or directory in /var/www/gamedev/admin/applications_addon/ips/ccs/sources/pages.php(458) : eval()'d code on line 4899 Warning: include_once(): Failed opening 'RContent/redis.php' for inclusion (include_path='/var/www/gamedev/ips_kernel/PEAR/') in /var/www/gamedev/admin/applications_addon/ips/ccs/sources/pages.php(458) : eval()'d code on line 4899