4
$\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.
  • 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?
Improve this question
$\endgroup$
1
  • $\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
    Commented Nov 30, 2018 at 18:44

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .