3
$\begingroup$

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.
  • In 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 of the large number of possible moves)?
  • If no, is there a proper alternative?
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – DukeZhou Nov 30 '18 at 18:44
0
$\begingroup$

-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:

These algorithms are quite a bit more complicated than MiniMax though, MiniMax is a very basic algorithm in comparison.

$\endgroup$
  • $\begingroup$ MCTS is a simple sampling approach which is traversing the given game tree but isn't able to reduce it's size. Like the Minimax strategy it will produce a problem because of the large branch factor but didn't provide a walkthrough. And “combinatorial games” are not an algorithm but the term describes certain type of games. $\endgroup$ – Manuel Rodriguez Nov 30 '18 at 11:22
  • 1
    $\begingroup$ @ManuelRodriguez The combinatorial variants of MCTS which I provided references for can handle combinatorial action spaces better by generalizing observations across different parts of the search tree (similar intuition to RAVE-like enhancements for standard MCTS). I didn't use the term "combinatorial games" anywhere, so I also didn't imply anywhere that that would be an algorithm rather than a certain type of game. $\endgroup$ – Dennis Soemers Nov 30 '18 at 11:46
  • $\begingroup$ All games are algorithms, and "combinatorial game" is a fuzzy term that expands as the scope of CGT expands (all games are also combinatorial.) For more info see Constraint Logic: A Uniform Framework for Modeling Computation as Games and [Playing Games with Algorithms: Algorithmic Combinatorial Game Theory] (erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf) (Demaine/Hearn) $\endgroup$ – DukeZhou Nov 30 '18 at 18:49
-1
$\begingroup$

A huge “branch depth” is a common problem in game AI. The best-practice method to overcome it are heuristics. Formalizing heuristics in game playing can be done with Domain specific languages. The assumption is, that a board game solver has certain commands like “pickup figure”, “setsearch depth 17” or “search freefield”. The board game solver is treated as a textadventure which provides a userinterface and allows to formalize all the heuristics in a convincingly way. From a performance perspective such a solver works similar to the minimax algorithm. He has to search in the game tree until he finds a solution. The difference is, that the search is fine granular like in a PDDL solver. Instead of occupying all the cpu cores with 100% the search in the game tree is declared as an art which follows rules.

In the cited paper, the manhattan distance was used as an evaluation function. Partial Evaluation is another promising approach. The idea is to divide the goal into subgoals and solve them separate.

  • Romein, John W., Henri E. Bal, and Dick Grune. "An Application Domain Specific Language for Describing Board Games." Parallel and Distributed Processing Techniques and Applications. Vol. 1. 1997.
$\endgroup$
  • $\begingroup$ Thank you! Since i‘m completely new to the subject this raises another question: the evaluation function for minmax is a heuristic approach, to determine which states/conditions on the board are more favorable. Is this all it need to cope with the huge branch depth? $\endgroup$ – josebert Nov 30 '18 at 9:04
  • 1
    $\begingroup$ Like @josebert mentioned, MiniMax-style algorithms already use heuristic functions to evaluate states. There are some other ways in which they can also use heuristic functions (early pruning, move ordering, etc.), but unless you do that in an extremely aggressive fashion, it won't address a combinatorial explosion of the action space. It would likely degrade the performance of minimax too much (because heuristics can be inaccurate), and you'd honestly be better off with different styles of algorithms altogether. $\endgroup$ – Dennis Soemers Nov 30 '18 at 13:08
  • $\begingroup$ @DennisSoemers Perhaps we should separate between the minimax description in university context and solving board games in reality. In university context, the aim is to explain the minimax algorithm to the student. They are informed about the mathematical background. Describing Minimax as a “heuristic aware” algorithm is optimistic. In a broader sense the term heuristic is reserved for a strategy which will reduce the state space drastically. $\endgroup$ – Manuel Rodriguez Dec 3 '18 at 21:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.