4
$\begingroup$

Brief idea
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 on 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 backwards and are only allowed to go into the goal if you've got less than some amout 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 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
First of all, I have to say that I'm kind of a beginner (I programmed nn, ga and rl) when it comes to artificial intelligence (don't tell me it could be to difficult for me. I know but I'm willing to learn and at least I want to try it ;) ). What would be ideally is 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 idea? 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?

Thanks for reading all this and for your help ;)

$\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
7
$\begingroup$

I couldn't add my reply as comment, so I decided to leave it here.

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 consider current situation that's 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 call Minimax. In summary, Minimax is simply a search algorithm to minimize other players score while maximizing your score. You can read more here https://en.m.wikipedia.org/wiki/Minimax

One of the problem you will encounter is that the search tree become so wide as we search through deeper part 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's very unlikely to be the optimal choice (in terms of score) thus reduce number of searches to speed up the algorithm. You can read more here https://en.m.wikipedia.org/wiki/Alpha–beta_pruning

I hope my response provided some help and good luck on your project!

$\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.

$\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.