Mr. Jack

A-Star, Min-Maxing, and Mr. Jack

Mr. Jack
I’ve been playing board games more and more recently, especially since I moved to California. The last one I played was Mr. Jack, a fairly popular two-player board game by Hurrican. In Mr. Jack, one player plays Jack the Ripper, while the other one plays as an unnamed investigator. The investigator’s goal is to determine the identity of Jack, who is one of the eight characters present on the board. Jack’s goal is to escape, either via the two moving boats on the board, or via an exit at one end of the board.

The play is complicated, because each round of play moves each character only once, alternating control between the two players. Finally, the characters all have special abilities, such as The Captain, who can move the two boats around, or the Inspector, who can place extra Subways on the board. So why the hell am I telling you about this game?

Well, it’s a good way to learn about a few of the more important concepts of AI – search spaces, A* search, and min-max algorithms. It’s also very practical – writing a bot for a relatively simple game like this is good practice for something more complex such as poker.

Search Spaces

Search space is an important concept in AI, but pretty much anyone who is in the mathematics or programming field knows a similar concept – Big O notation, which represent algorithm running time. Search space is simply the amount of positions that are tested by the algorithm to find the solution – some games have very small search spaces, such as tic-tac-toe, which only has 255,168 positions – a winning algorithm doesn’t even have to test all these positions. Some games, like chess or go, have huge search spaces – 10^50 or 10^170, which is far too large to completely test.

Mr. Jack’s search space is fairly limited – characters can only move up to three squares, can only use an ability once per round, and there are only four rounds. The board, while fairly large, is still very limited in actual movements. These factors, combined, make the game fairly possible to search.

A* Search

A* search is one of the more important basic concepts of AI, and it’s also one of simplest. In A* search, positions are given two weights: the ‘cost’ of getting to that position in the first place, and the ‘cost’ of getting from there to the solution. This is illustrated best by the following example:

Romania Map

Say we want to find the shortest path from Arad to Bucharest – we know the actual distance between cities, but we can build a heuristic to estimate the distance from each city to our destination as we hit it. In this way, we can eliminate some cities at each step, and are not forced to check them. How does this relate to Mr. Jack? While A* is not the algorithm that should be used for a bot in this game, heuristic costs are a big part of the game. One of the most important aspects of writing a bot for Mr. Jack is deciding which positions are good for each player – and it plays deeply into the next, and last concept we’ll talk about.

Min-Max

Min-Max is an algorithm that analyzes alternating moves by two competing players. It picks the best move for a player by recursing down possible steps, and evaluating the best move for each side – in this way, the main player maximizes his value, while the challenging player minimizes the main player’s score.

MinMax

For example, our main player has three choices of moves: B1-B3. The challenging player, based on his choice, will have one of three possible moves in each scenario: C1-C9. Since our challenging player will try to minimize the main player’s score, we can give each main player’s move a value – the smallest value in each set of C1-C9. So each move of the main player’s now has a definite value, and the best move can be chosen.

For Mr. Jack, this is the algorithm that one would use to calculate the best moves for each player. It will be harder to define values for each step, of course, but the direct competition between two players, as well as alternating moves, fits this algorithm completely.

What’s the Point?

Finding practical and interesting examples for any topic you’re learning keeps things fresh. Finding small projects to work on on the side is very important as well, especially if you’re working a 9-5 in the programming field. It keeps your interest strong, and it’s always good for your resume.

Hope you enjoyed this article, and if you’ve got any examples of games you’ve written bots for, we’d love to hear about them. Leave your comments below!

2 thoughts on “A-Star, Min-Maxing, and Mr. Jack

  1. Pingback: Can We Brute Force Mr. Jack? | SuperProfundo

  2. Aaron L

    Hey, cool post!

    Mr. Jack sounds like a pretty tough game; simple moves but some really complex emergent behaviours. I’ve been programming casually and bumped into a game you might want to try once or twice called vindinium. It’s a lot simpler but offers a good test of skill. I just finished making my own simple client for it and it works beautifully, so I’m about to start work on a fresh bot for it.

    I’d like your input about my algorithm. So far, I’ve got an A* and a few if statements to choose a good target. I’d like to try a sort of A* minimax combination; generate paths to potential goals using a heuristic A* pathfinder, and then minimax each goal by distance, wealth (captured mines), and by life.

    As far as I understand, A* is excellent in choosing paths to predetermined goals, and minimax is excellent for choosing goals, so a hybrid algorithm would be particularly effective. What’s your take on combining both algorithms?

    Feel free to email me on the topic (I’m not sure I’ll get a notification if you reply).