How do I create an AI for a two-players board game?

Question

Goal

I want to create an artificial intelligence to compete against other players in a board game.

Game explanation

I have a board game similar to 'snakes and ladders'. You have to get to a final field before your opponent does. But instead of depending on luck (throwing the dices) this game uses something like 'food'. You can go as far as you'd like, but it costs food to move (the more you move the more one extra field costs) and you can only get food in some special fields. And there aren't any snakes or ladders so you have to run the whole part. There are some more rules, for example, you can go backward and are only allowed to go into the goal if you've got less than some amount of 'food' and there are some extra fields with other special effects.

For one player

If there was only one player as there isn't anything like 'luck' in this game, I theoretically could just compute every single method to find the one and only the best method. Practically, I should use an algorithm that requires less computational power.

For two or more players

The challenge comes with the other player(s). I cannot visit an already taken field. And some other fields give me bonuses depending on my relative position to the other player (I'll just talk about two-player games). For example, only if I'm behind him that special field gives me some extra food.

My question

It would be ideal if I had some kind of a neural network that knows the field bonuses and I would give my position, the opponents position, the food and so on (the state of the game) and it would compute a value between -100 and 100 (assuming fields from 0 to 100) of how many fields I should go (forward or backward).

I read a bit about Q-learning, deep reinforcement learning and deep neural networks. Is this the right approach to solving my problem? And if yes, have you got any more concrete ideas? The multiple actors and the sheer endless possibilities for moving depending on endless states make it hard for me to think of anything. Or is there a different, way better way that slipped past me?

Answer 1

Assuming it is a turn-based game and, for each turn, there's an optimal choice that will lead to the winning state (zero-sum), you can basically simplify the question to "What is the optimal sequences of moves for me to win, considering the current situation that is presented on the board?". So you will need to perform your algorithm every turn as the optimal sequence will change when the board changed.

There's a relatively reliable AI algorithm that's being implemented to win games like chess, backgammon, etc. The technique is called minimax. In summary, minimax is simply a search algorithm to minimize the other player's score, while maximizing your score.

One of the problems you will encounter is that the search tree becomes so wide as we search through deeper parts of the tree, so it is essential to also implement alpha-beta pruning to cut down the amount of search. In general, alpha-beta pruning is simply eliminating branches that are very unlikely to be the optimal choice (in terms of score) thus reducing the number of searches to speed up the algorithm.

Answer 2

To make an AI opponent, you'll need to create a sub-routine that considers the current state of the board and chooses a move, just like the player would.

Now, how does this subroutine choose what move to make? You need to take the current board and calculate its value. Then consider every possible move you could make. Then consider, for each of those, every possible move your opponent could make. Iterate to maximum depth. You will have constructed a tree structure (breadth first).

Prune your tree. Any branch that guarantees you a decrease in board value can be pruned.

Then, somehow, compare remaining branches. Either you optimistically weigh possible best outcomes and choose those branches. Or continue pruning based on potential of worst outcomes.