1
$\begingroup$

I want to implement an AI capable of playing the game RoboRally (https://en.wikipedia.org/wiki/RoboRally) using Monte Carlo Tree Search (MCTS). In RoboRally, there are 2-8 characters controlled by (human) players, each of which must reach checkpoints. However, each turn, a character can only move by playing cards chosen by the player associated with that character. For example, the card MOVE2 allows a character to move 2 tiles in the direction they are facing on the gameboard.

In each turn, the player selects 5 cards from their hand of 9 cards, which are then played in the chosen order. Each node in the MCTS represents a game state with a certain set of chosen cards. For example, a node expanded from the root might represent playing the MOVE2 card first for a player. My question is: how should I simulate a game state to a terminal state in this case? As I understand it, a terminal state would be reached when 5 cards are chosen, i.e., the fifth level of the MCTS is reached.

Considering the example where only MOVE2 is chosen first, should the simulation involve randomly choosing the remaining 4 cards from my hand of 9 cards and then simulate the game state with these chosen cards? This evalution might then be how far the character is from the next checkpoint. The closer the character is to the next checkpoint, the better the evaluation, i.e., value of the node. Furthermore, is MCTS even a suitable choice for this game, considering that reaching a terminal state does not evaluate to a win/loss/draw situation, and I must evaluate the simulations with a function, which might be very complicated.

If MCTS is not suitable, what other algorithms would be appropriate for implementing an AI for this kind of game?

I would appreciate any advice and feedback!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Have looked at the game description. MCTS can be a very good choice, as far as I can tell.

The action that you take at each phase is selecting five cards from the nine you have and placing them face down in a specific order. If I follow the rules then from now on it is not in your control, there is just a stage in which all the players see what have happened.

The MCTS is all about choosing the five cards out of the nine and their order. I think it can be a very nice implementation of MCTS, without thinking too much about it, just selecting random cards and random picking/ordering of the cards. If you repeat it in your "head" enough times, you shall find the most promising moves I believe.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 9c5 with important order gives a lot of action choices to decide between on each turn. I think OP may want to look into something heirarchical, making the card choices sequentially. So their description of that being a "terminal" state is not quite right, but they are IMO identifying an issue that needs to be resolved $\endgroup$
    – Neil Slater
    Jul 29 at 8:44
  • $\begingroup$ I would suggest that the simplest implementation would to have an action select a single card and to have state that tracks what is already selected, and maybe some helper state such as possible position outcomes on the board, depending on success of cards played so far $\endgroup$
    – Neil Slater
    Jul 29 at 8:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .