we are working on a little Java game, based on the game Blokus.
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 :)
Min-max is hard to implement in a 4 player game because:
log(medMoves)=Nsteps. 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.
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).