Comment by wyldfire | Hacker News Reader

Comment by wyldfire | Hacker News Reader

Parent Full thread

I'd used minimax before but not heard of Monte Carlo tree search. It sounds interesting.

From [1]:

> Although it has been proven that the evaluation of moves in MCTS converges to the minimax evaluation, the basic version of MCTS can converge to it after enormous time. Besides this disadvantage (partially cancelled by the improvements described below), MCTS has some advantages compared to alpha–beta pruning and similar algorithms. Unlike them, MCTS works without an explicit evaluation function. It is enough to implement game mechanics, i.e. the generating of allowed moves in a given position and the game-end conditions. Thanks to this, MCTS can be applied in games without a developed theory or even in general game playing.

> The game tree in MCTS grows asymmetrically: the method concentrates on searching its more promising parts. Thanks to this, it achieves better results than classical algorithms in games with a high branching factor.

> Moreover, MCTS can be interrupted at any time, yielding the move it considers the most promising.

[1] https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Advant...

Aside from the tree search perspective, MCTS can be thought of as an extension of upper confidence bound approaches for multi armed bandit problems. This stuff is all about exploration vs exploitation tradeoffs - which is something quite different to Minimax / alpha-beta search - those prune branches when they logically prove that evaluating the branches cannot improve the decision of which move to make.

A multi armed bandit problem offers you one decision to pull one of n levers, so it's like a wide shallow game tree where the root has n leaves.

I wrote a MCTS backgammon move recommendation engine/AI for a class in college. It was a lot of fun.

It was easy to ramp up to many many cores.

I have no idea how to play the game well, never learned, but because the win/lose rules are so clear and using this method, no need to build in game/move theory. Still got great results compared to "advanced" players' games.

I wrote a MCTS Ultimate tic-tac-toe engine[0] over the last little while, and likewise don't know how to play the game well. Once thing I have been mulling over in my mind but haven't really explored is training an NN on the game tree produced by long searches and somehow extracting strategies a la DeepDream. I don't have much experience with NNs though so no idea if it even possible or what the extracts would look like.

If anyone would find this interesting work to collaborate on feel free to contact me. The MCTS part is done.

0. https://github.com/putterson/uxobot

Reply on news.ycombinator.com