Answers.Body: <blockquote>
    <p>-The player can choose as many pieces to move as he likes. For example none, all of them, or some number inbetween. (Whereas in chess you can only move one)</p>
  </blockquote>
  
  <p>That quote specifically is the part that really causes the size of your legal action set to blow up. You have a combinatorial action space here. If each of your pieces has 8 legal moves, then that is:</p>
  
  <ul>
  <li>8 legal moves for the first piece (or 9 if that count didn't already include the "do nothing" option)</li>
  <li>for each of those, there are again 8 or 9 different choices for the second piece (leading to e.g. <span class="math-container">$8 \times 8 = 64$</span> possible combinations for just the first two pieces)</li>
  <li>for each of those, again 8 choices for the third piece (leading to <span class="math-container">$64 \times 8 = 512$</span> possible combinations for just the first three pieces).</li>
  <li>etc.</li>
  </ul>
  
  <p>This blows up way too quickly, and there's really no hope of ever getting a decent player for this using any MiniMax-based algorithm (including things like alpha-beta pruning, principal variation search etc.).</p>
  
  <p>In the kinds of games that you describe, you'll want to use algorithms that can exploit the "structure" of your action space. A raw enumeration of all possible combinations blows up quickly, but many algorithms can do reasonably well by re-phrasing the problem in such a way that you have more "depth" rather than "breadth". For example, instead of viewing a full combination of choices for all pieces as a single "action", you can treat the choices per piece as a separate "action". </p>
  
  <p>Rather than making a single choice out of <span class="math-container">$8 \times 8 \times 8 \times \dots$</span> possibilities every turn, you want to have a search tree where your player makes one choice out of <span class="math-container">$8$</span> (for the first piece), followed immediately by another choice out of <span class="math-container">$8$</span> (for the second piece), etc. The opposing player only gets to make a choice after the current player has made choices for all pieces. With such a strategy, the breadth of your search tree will no longer be a problem, but the depth will become a problem. To address this, you'll additionally want to make sure that your methods can generalize across different depth levels.</p>
  
  <p>A good place to look would be combinatorial versions of Monte-Carlo Tree Search, such as those described in:</p>
  
  <ul>
  <li><a href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Roelofs_thesis.pdf" rel="nofollow noreferrer">https://project.dke.maastrichtuniversity.nl/games/files/msc/Roelofs_thesis.pdf</a></li>
  <li><a href="https://www.jair.org/index.php/jair/article/view/11053" rel="nofollow noreferrer">https://www.jair.org/index.php/jair/article/view/11053</a></li>
  <li>(probably a few other publications by the author of that second link)</li>
  </ul>
  
  <p>These algorithms are quite a bit more complicated than MiniMax though, MiniMax is a very basic algorithm in comparison.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-30T18:49:31.293Z
Answers.Text: All games are algorithms, and "combinatorial game" is a fuzzy term that expands as the scope of [CGT](https://en.wikipedia.org/wiki/Combinatorial_game_theory) expands (all games are also combinatorial.)  For more info see [Constraint Logic: A Uniform Framework for Modeling Computation as Games](http://erikdemaine.org/papers/CL_Complexity2008/) and [Playing Games with Algorithms:
  Algorithmic Combinatorial Game Theory] 
   (http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf)  (Demaine/Hearn)
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-30T11:12:53.700Z
Answers.LastActivityDate: 2018-11-30T11:12:53.700Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I have to build a KI for a made-up game similar to chess. As I did research for a proper solution, I came upon the MinMax algorithm, but I'm not sure it will work with the given game dynamics.</p>
  
  <p>The challenge is that we have far more permutations per turn than in chess because of these game rules.</p>
  
  <ul>
  <li>Six pieces on the board, with different ranges.</li>
  <li>On average, there are 8 possible moves for a piece per turn.</li>
  <li>The player can choose as many pieces to move as he likes. For example none, all of them, or some number in between (whereas in chess you can only move one.)</li>
  </ul>
  
  <p>Actual questions:</p>
  
  <ul>
  <li>Is it feasible to implement MinMax for the described game?</li>
  <li>Can alpha-beta-pruning and a refined evaluation function help (despite the large number of possible moves)?</li>
  <li>If no, is there a proper alternative?</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-30T18:44:41.137Z
Comments.Text: By similar to Chess do you mean 2-player, non-chance, perfect information, sequential (turn-based) games involving moving and capturing tokens?  How big is the gameboard and what accounts for the higher number of branches? Is the game natively finite, or can it get "loopy" (potentially infinite loops)?
Comments.UserDisplayName: DukeZhou
Tags: <game-ai><minimax><alpha-beta-pruning>
Title: Is it feasible to use minimax to solve a board game with a large number of moves?
UserDisplayName: josebert
ThreadText: # Is it feasible to use minimax to solve a board game with a large number of moves?
  
  (Asked by: username_0 on 2018-11-30)
  
  I have to build a KI for a made-up game similar to chess. As I did research for a proper solution, I came upon the MinMax algorithm, but I'm not sure it will work with the given game dynamics.
  
  The challenge is that we have far more permutations per turn than in chess because of these game rules.
  
  * Six pieces on the board, with different ranges.
  * On average, there are 8 possible moves for a piece per turn.
  * The player can choose as many pieces to move as he likes. For example none, all of them, or some number in between (whereas in chess you can only move one.)
  
  Actual questions:
  
  * Is it feasible to implement MinMax for the described game?
  * Can alpha-beta-pruning and a refined evaluation function help (despite the large number of possible moves)?
  * If no, is there a proper alternative?
  
  **Tags:** game-ai, minimax, alpha-beta-pruning
  
  > **Comments:**
  > **username_1**: By similar to Chess do you mean 2-player, non-chance, perfect information, sequential (turn-based) games involving moving and capturing tokens?  How big is the gameboard and what accounts for the higher number of branches? Is the game natively finite, or can it get "loopy" (potentially infinite loops)?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-11-30. Score: 2
  
  > -The player can choose as many pieces to move as he likes. For example none, all of them, or some number inbetween. (Whereas in chess you can only move one)
  
  That quote specifically is the part that really causes the size of your legal action set to blow up. You have a combinatorial action space here. If each of your pieces has 8 legal moves, then that is:
  
  * 8 legal moves for the first piece (or 9 if that count didn't already include the "do nothing" option)
  * for each of those, there are again 8 or 9 different choices for the second piece (leading to e.g. $8 \times 8 = 64$ possible combinations for just the first two pieces)
  * for each of those, again 8 choices for the third piece (leading to $64 \times 8 = 512$ possible combinations for just the first three pieces).
  * etc.
  
  This blows up way too quickly, and there's really no hope of ever getting a decent player for this using any MiniMax-based algorithm (including things like alpha-beta pruning, principal variation search etc.).
  
  In the kinds of games that you describe, you'll want to use algorithms that can exploit the "structure" of your action space. A raw enumeration of all possible combinations blows up quickly, but many algorithms can do reasonably well by re-phrasing the problem in such a way that you have more "depth" rather than "breadth". For example, instead of viewing a full combination of choices for all pieces as a single "action", you can treat the choices per piece as a separate "action".
  
  Rather than making a single choice out of $8 \times 8 \times 8 \times \dots$ possibilities every turn, you want to have a search tree where your player makes one choice out of $8$ (for the first piece), followed immediately by another choice out of $8$ (for the second piece), etc. The opposing player only gets to make a choice after the current player has made choices for all pieces. With such a strategy, the breadth of your search tree will no longer be a problem, but the depth will become a problem. To address this, you'll additionally want to make sure that your methods can generalize across different depth levels.
  
  A good place to look would be combinatorial versions of Monte-Carlo Tree Search, such as those described in:
  
  * <https://project.dke.maastrichtuniversity.nl/games/files/msc/Roelofs_thesis.pdf>
  * <https://www.jair.org/index.php/jair/article/view/11053>
  * (probably a few other publications by the author of that second link)
  
  These algorithms are quite a bit more complicated than MiniMax though, MiniMax is a very basic algorithm in comparison.
  
  > **Comments:**
  > **username_1**: All games are algorithms, and "combinatorial game" is a fuzzy term that expands as the scope of [CGT](https://en.wikipedia.org/wiki/Combinatorial_game_theory) expands (all games are also combinatorial.)  For more info see [Constraint Logic: A Uniform Framework for Modeling Computation as Games](http://erikdemaine.org/papers/CL_Complexity2008/) and [Playing Games with Algorithms: Algorithmic Combinatorial Game Theory]   (http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf)  (Demaine/Hearn)  
  
  ---
  
  