Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

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 🙂

Tags:

5

Answers


  1. 0

    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.

    Login or Signup to reply.
  2. 0

    I would recommend minimax algorithm. One thing you can add to make it more efficient (meaning you should be able go more moves deep into the future) is alpha-beta pruning.

    The problem with minimax search is that the number of games states it has to examine is exponential in the depth of the tree. Unfortunately, we can’t eliminate the exponent, but it turns out we can effectively cut it in half.

    The quote is from Chapter 5.3 of Artificial Intelligence: A Modern Approach third edition by Stuart Russel and Peter Norvig. It was holding up my monitor, and I used it in a few of my classes in college. I know people don’t often reference books on SO, but it’s extremely relevant. I have used it extensively, and I do really recommend it for both being understandable, and covering a wide range of AI content.

    It is available on amazon for $104, or * cough cough * I’m sure you can find it online if you don’t have that kind of money for a textbook floating around. Looking up the minimax algorithm and alpha beta pruning online should also get you good results.

    I think the only circumstance that would make Minimax a poor option for you is if the game state is only partially observable to any given player (they don’t know everything about what’s going on), or if the game is non-deterministic (it has random elements). Because neither of these are the case for Blokus, I think you made an excellent choice with Minimax.

    The area of AI is called Adversarial Search in the textbook (Chapter 5: Adversarial Search), so looking up more info online with that term may get you more helpful information, or help you find an example Java implementation. I do not consider this a beginner’s task, but it sounds like you are up to it, if you made the game and can pick random valid moves. Keep up the good work!

    Login or Signup to reply.
  3. 0

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

    Login or Signup to reply.
  4. 0

    In 2011, with many updates since then, a program called Pentobi
    was released, and it is a very strong Blokus playing program.

    The only one known to date, in fact, which is any good at all, and it
    surpasses all the others by a great deal. It will beat many good human players and gives even the best a run for their money.

    Its main algorithm is Monte Carlo Search Tree, but it also uses a “book” of openings and some heuristics.

    There is documentation and download information at
    http://pentobi.sourceforge.net/

    Login or Signup to reply.
  5. 0

    I found that using a very simple heuristic provides a fairly intelligent player even using only 1-step look ahead. I implemented what I called "space heuristic" which takes the board state and floods it by coloring all squares adjacent to each placed piece the color of that piece. Then, the total number of colored squares is counted once the flooding terminates. The space heuristic gives a rough estimate of how much a play claims or occupies board space, and way outperforms random play. Could be combined with minimax or MCTS to get way stronger as well.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search