2
$\begingroup$

I'm writing an AI for a board game, and previously I would just create a value maximizing state machine and tune the factors one at a time.

However, the issues with this is getting apparent. My last AI did not look into the future, hurting it's long term chances, and manual tuning of weights is proving to be a chore.

I've looked into minimax algorithms, but with a non perfect information game and elements of random chance I'm not too confident it will be effective.

I've also looked into traditional neural networks, but evaluating board states is tricky and the game does not split into moves well.

The game I'm writing the AI for is Ticket To Ride, but I would appreciate tips for any board game with similar mechanics.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Many successful game-playing engines use some form of search to look ahead and plan the next move. This is possible even in stochastic environments by building a tree with probabilities assigned, or by simulating the randomness during planning and relying on lots of samples to get reasonable estimates of value.

There are many approaches possible. However, as Ticket to Ride is a relatively simple game that you could automate to play to the end very quickly (1000s of times per second), then you could look into Monte Carlo Tree Search (MCTS) as a mechanism for the game-playing agents to look ahead and adjust their play to current odds.

The basics of Monte Carlo Tree Search:

  • On its turn, the agent builds up an evaluation tree local to its current state - each node of the tree is a game state, augmented with statistics from MCTS (how often node was chosen, how many times agent managed to win eventually from that node) and each link is a choice that a player makes. This is built up slowly, typically just adding one node per full simulated game.

  • For look-ahead search "inside" the tree, the agent explores options according to their relative promise, selecting moves to simulate according to its best estimates of value at the time. It needs to explore alternatives to make sure it doesn't miss anything, and there are a few variations of doing this. One successful approach to action selection inside the tree is Upper Confidence Bound applied to Trees (or UCT for short).

  • When play gets to a leaf node of the tree, the tree might be expanded slightly, and then afterwards the agent simulates plays of the game either to the end or to a robust evaluation point. This later play might be entirely random - or might still be guided probabilistically by some heuristic - and is called a rollout. The important thing here is to play quickly to get samples just to roughly assess the position at the leaf of the tree.

  • The evaluation resulting from rollout is fed back into the tree, which builds up sampled statistics of the most promising variations of play.

  • After a certain number of repeats of the whole algorithm (local tree search, expanding the tree, rollout and update), the agent picks the most promising next step from the tree. At this point it may just discard the whole tree - in a game with lots of randomness, this is probably what you would do now, as things you were considering as just probabilities before will have become historical fact, and the chances are that re-running the tree build from the next start position will be more accurate.

There are a few variants possible, including combinations with neural networks as used in AlphaZero.

The basic principle is to sample from many choices, focusing over time on what looks "best" to each player based on statistics of those choices.

As Ticket To Ride is a card game where cards can be drawn from an unseen deck, and it would be considered cheating to simulate and rollout with the actual deck in play, you would need to have realistic shuffles of the remaining unknown cards used during rollout. It may still work quite well without the realistic part and for speed just assume a random unlimited deck of cards (because re-shuffling on each imagined rollout would be costly).

$\endgroup$
2
  • $\begingroup$ How does MCTS work with randomness? Most articles on the Web that I've found are for perfect information games. How do I know what moves other people will do if I don't know their state? I could figure it out based on probability or something but I'm not soo syre, $\endgroup$ Mar 9, 2019 at 18:02
  • $\begingroup$ The tree growing stage will need to allow for probabilities of steps happening, I don't know the exact formulation for it. The rollout stage is identical as you are just sampling and you don't need to track anything but a single path (and you could just steal the rollout idea for a very simple improvement to a game with randomness, that's how TD-Gammon worked for backgammon). Knowing what other people will do is about guessing their policies, and potentially training all of them at the same time using the same agent code $\endgroup$ Mar 9, 2019 at 18:34

You must log in to answer this question.

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