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

Question

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 1

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).

Answer 2

Theoretically speaking, an "as good as possible AI" is a perfect AI, which is an AI that has, at any moment in the game, full knowledge of the game state (if the full game state is not known by human players). In case of games that everyone has full game state knowledge (like Blokus), a good as possible AI is an AI that can try to predict the very best move to make (minimax here, as you said). You can also google for genetic algorithms and simulated annealing, as they are valid, depending on what you want. Also, you can use minimax for more than 2 players.