5
$\begingroup$

I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm:

The initial state, S0 is the board state where the AI places the stone, or in other words, the AI's turn. Is it correct that each node should be the AI's turn, not the humans?

In the expansion phase, you need to "create child nodes". In my game, the child nodes would each be a place where an AI can make a move. However, if I want to select the next avaliable AI move, I need to know where the enemy, or the human places the stone before the next avaliable AI move. I improvised by making it 2-layered: for every avaliable human moves, add every avaliable AI moves after the human plays. Is this the correct way to do it?

This is my current tree structure in an Example: Each state has info of where black and white "stones"are placed. the AI plays white, and Human plays black. Black plays first. state S0 would be the first move of the game.

                S0(black stones:[(2,2)],white stones:[])
                        /                            \
                       /                              \
                      /                                \
S1(black stones:[(2,2)],white stones:[(1,1)])        S2(black stones:[(2,2)],white stones:[(1,2)]   
    |                                                       |
S3(black stones:[(2,2),(2,1)],white stones:[(1,1)])  S4(black stones:[(2,2),(2,3)],white stones:[(1,2)]   
$\endgroup$
  • 1
    $\begingroup$ I would imagine nodes represent both human and AI. Then edges would represent the possible moves they could make. Take the example here. The root node is white's turn, its edges are potential decisions, its children represent black's turn. This gets rid of the "double layered" notion you mention and should make it less complicated. You're still overall keeping track of whether the AI wins as a part of the back propagation phase. $\endgroup$ – ryan Jun 23 '17 at 7:20
1
$\begingroup$

In you implementation you need to separate the game rules from the mcts search algorithm. Mcts does not need an evaluation like minimax. When calling random playouts all you need to do is keep making legal moves till the game ends and mark the playout with an outcome of win/loss.

your game rules need functions like legal_moves, make_move, undo_move, is_game_over, winnerIs and maintain a states that represent the position

your mcts needs mcts, ucb_sample, expand, random_playout, backpropogation

for states you need position {visits, value or total/count}

$\endgroup$
  • 1
    $\begingroup$ Yes you do randomly play moves in the playout, but I heard that using a pseudo evaluated moves instead of totally random moves give better results. $\endgroup$ – Dashadower Dec 26 '17 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.