• Contribute
• What's New
• Submit News

I originally saw this game in the form of a puzzle in Trilobyte's multimedia game The 7th Guest. The rules are very simple, the AI relatively simple to create, but the game can pretty challenging to play against. This makes the game an excellent project for gaming AI beginners.

Outline

The rules of the virus game are as follows:

• 
• Goal: To control more than 50% of the board by the end of the game.
• Setup: Two player, turn-based game played on a square board (normally around 15x15). Player 1 has a piece at the top-left and bottom-right corners of the board and the opponent has pieces in the other corners.
• Movement: You move one piece at a time, and you can either move it one space or two spaces. If one space is moved, the virus will reproduce (thus a piece will reside in both the original and new position). If you move the piece two spaces, the virus jumps to the new position. The game stops when all spaces are taken, or it is impossible for the current player to move.
• Captures: When a piece moves into a position, it will take control of all adjacent enemy pieces.

The animation above and diagram below demonstrates the rules. In Figure 1 you see that the green piece moves from the bottom-left hand corner and reproduces into the space above and to the right. It then takes the surrounding four blue pieces. In Figure 2, the blue piece in the bottom right hand corner jumps two places into the "centre" of the 4-piece green structure and takes them all. Note how the two space jump doesn't have to be perfectly straight.

Figure 1: One-space move with replication.

Figure 2: Two-space jump with replication.

Guidelines

Consider using an influence map to assess the various positions on the board. Some possible heuristics:

• Number of surrounding opponent pieces (within reproducing and jumping range).
• Number of surrounding friendly pieces (within reproducing and jumping range).
• Is this empty space a vulnerable hole? (Many friendlies with a enemy in range)
• Is this empty space a good attack point? (Reverse of above)

Probably these heuristics would be sufficient to create decent AI. Note that there is a certain degree of added complexity, since the rules of the game requires both a start and end point to the move (as opposed to games like Tic-tac-toe, where placing is independent to existing pieces). As such, you may want to consider limiting your influence map to positions that are within reach of your existing pieces. Run the heuristics to find the optimum position, then search for the best piece to make the move—obviously, a one-space move is preferable to a two-space jump.

You could also look at creating a simple finite state machine that controls the aggressive/defensive weights applied by the influence map. One state when the AI owns less than 50% of the board, and another when it owns more.

---

Solutions

Virus Applet	A demonstrator for the Generation5 JDK BoardGame, BoardGameAgent and InfluenceMap classes.
VirusGame.zip (27Kb)	Solution submitted by Jon Roelofs. Java applet with an interesting solution method.