Xyarvius Xyarvius - 6 months ago 56
Java Question

Artificial Intelligence for a 'Blokus' game (1-4 Player)

we are working on a little Java game, based on the game Blokus.
Blokus-Manual

I'm a Java-beginner and plan to implement an advanced artificial intelligence. We already have a random AI (picks a random valid move) and an AI with a simple move-rating mechanism. We also want an AI which should be as good as possible (or at least very good ;) ).

The question is: Which AI-concept would be suitable for our purpose?
The minimax-algorithm seems to be a valid choice, but how do you adapt it to a 4-player-game? Are there better concepts for a game like blokus?

Thanks already :)

Answer

Min-max is hard to implement in a 4 player game because:

  • Decision tree grows exponentially, so you're going to be bounded by memory and/or computation time to a log(medMoves)=N steps. For a 4 player game, this is down to N/4. If N is 8 for example, you're only going to be able to see 2 moves ahead for each player.
  • Player collusion is hard to account for. In a realistic game, some players might help each other out (even if they're not on the same team). This will cause them to deviate from their personal 'maximum'.

If you want Minmax, you're going to have to do a lot of pruning to make it viable. What I would suggest is learning a few patterns so the AI would know how to react. This can be done via neural net, or reinforcement learning with a few tweaks.

These patterns could be be static (you can create the input scenario manually or programmatically), or dynamic (create all valid scenarios and randomly makes moves select the ones with the best score).