Answers.Body: <p>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 "<em>What is the optimal sequences of moves for me to win, considering the current situation that is presented on the board?</em>". So you will need to perform your algorithm every turn as the optimal sequence will change when the board changed.</p>
  
  <p>There's a relatively reliable AI algorithm that's being implemented to win games like chess, backgammon, etc. The technique is called <a href="https://en.m.wikipedia.org/wiki/Minimax" rel="nofollow noreferrer"><strong>minimax</strong></a>. In summary, minimax is simply a search algorithm to minimize the other player's score, while maximizing your score.</p>
  
  <p>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 <a href="https://en.m.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer"><strong>alpha-beta pruning</strong></a> 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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-11T20:06:31.863Z
Answers.Text: Looks like your answer bore fruit re: https://ai.stackexchange.com/questions/4975/how-do-i-write-a-good-evaluation-function   Thanks for contributing!
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-14T13:31:16.187Z
Answers.LastActivityDate: 2019-11-22T22:18:26.103Z
Answers.LastEditDate: 2019-11-22T22:18:26.103Z
Answers.UserDisplayName: WorldWind
Answers.Body: <p>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. </p>
  
  <p>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).</p>
  
  <p>Prune your tree. Any branch that guarantees you a decrease in board value can be pruned.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-15T20:19:13.920Z
Answers.Text: would love to get your thoughts on [mbrane](http://mbranegame.com/) We're going classical for the time being, focusing on human-like play and variation as opposed to sheer strength.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-15T19:37:33.080Z
Answers.LastActivityDate: 2017-12-15T19:37:33.080Z
Answers.UserDisplayName: Seth Simba
Body: <h3>Goal</h3>
  
  <p>I want to create an artificial intelligence to compete against other players in a board game.</p>
  
  <h3>Game explanation</h3>
  
  <p>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.  </p>
  
  <h3>For one player</h3>
  
  <p>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.  </p>
  
  <h3>For two or more players</h3>
  
  <p>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.</p>
  
  <h3>My question</h3>
  
  <p>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 <strong>state</strong> 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). </p>
  
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-14T16:58:20.267Z
Comments.Text: 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](http://mbranegame.com/), 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.)
Comments.UserDisplayName: DukeZhou
Tags: <deep-learning><reinforcement-learning><ai-design><game-ai><combinatorial-games>
Title: How do I create an AI for a two-players board game?
UserDisplayName: po0l
ThreadText: # How do I create an AI for a two-players board game?
  
  (Asked by: username_0 on 2017-12-14)
  
  ### 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?
  
  **Tags:** deep-learning, reinforcement-learning, ai-design, game-ai, combinatorial-games
  > **Comments:**
  > **username_1**: 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](http://mbranegame.com/), 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.)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2017-12-14. Score: 9
  
  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**](https://en.m.wikipedia.org/wiki/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**](https://en.m.wikipedia.org/wiki/Alpha%E2%80%93beta_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.
  
  > **Comments:**
  > **username_1**: Looks like your answer bore fruit re: https://ai.stackexchange.com/questions/4975/how-do-i-write-a-good-evaluation-function   Thanks for contributing!  
  
  ---
  
  ### Answer by username_3 on 2017-12-15. Score: 1
  
  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.
  
  > **Comments:**
  > **username_1**: would love to get your thoughts on [mbrane](http://mbranegame.com/) We're going classical for the time being, focusing on human-like play and variation as opposed to sheer strength.  
  
  ---
  
  