7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to AI! Excellent question. One point I'll make, because this appears to be deterministic game, is that you could take a classical approach, and see if you can "solve" the game to identify "perfect play". My question is: what is your intent? Are you looking to build the strongest AI possible? If so, Deep Learning would definitely be the way to go, barring solution of the game. (On my own project, we're currently taking a modular, classical approach, to produce human-like play that can strengthen or weaken, depending on the skill of the human opponent.) $\endgroup$ – DukeZhou Dec 14 '17 at 16:58
  • $\begingroup$ po0l: You might consider accepting @WorldWind's answer since it seems that you're proceeding with his suggestion here: ai.stackexchange.com/q/4975/16806 $\endgroup$ – user16806 Nov 23 '19 at 22:42
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ would love to get your thoughts on mbrane We're going classical for the time being, focusing on human-like play and variation as opposed to sheer strength. $\endgroup$ – DukeZhou Dec 15 '17 at 20:19

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.