Java Color Expansion

The Game

Java Color Expansion is the Java adaption of a two player boardgame called Color Expansion. The rules of the game are very simple :

The board is divided into rectangular tiles. Each tile has a color. Adjacent tiles with the same color form regions.

The game is played by two players. Each player starts a game with a corner region. The players start in opposing corners ( the current player's region is marked with an X ).

During the game, the players take turns picking a new color for their region. They are not allowed to pick the color of their own region or the color of the other player's region.

When a player picks a new color for his / her region, all adjacent regions which have the same color are added to it, as well as all regions cut off from the other player's region.

The game ends when the whole board is conquered, and the player with the biggest region wins.

Artificial Intelligence

Creating an algorithm like the Difference AI (see below) is not very difficult, but it only looks a few moves ahead. That means it is only able to make tactical decisions, especially on big boards, although it is quite good at that. Adding strategical strength is a real challenge. With Color Expansion, moving strategically would mean to move across the board as fast as possible while keeping the opponent from doing so. Fast movement will let you cut off groups of regions from the opponent and it will increase the number of neutral regions within reach of your territory.

All the AIs that come with Java Color Expansion calculate a number (equivalent to their level) of moves ahead, evaluate every game state they can reach and pick the move that should lead to the game state with the highest value. Here's a description of the two AIs currently included in the program :

Difference AI

This AI tries to increase its territory as fast as possible while keeping the opponent from doing so. The value of a game state is equal to

(size of the AI's territory) - (size of the opponent's territory)

Maze AI

Many neutral regions on the board are far closer to one player's territory than to the other's. Going for a region the opponent can conquer with a single move while you need five moves to get there is a waste of effort. To account for this, the Maze AI uses only the neutral regions for which the distance to the player territories differs by less than two (other values are possible and do not have a big impact on the algorithm's strength, although when looking solely at regions with equal distance to both player territories there will - very rarely - be game situations where there is no region that meets the criterium). It marks these regions before starting the look ahead algorithm. The value of a game state is equal to

(sum of the distances between the AI's territory and the marked regions)- (sum of the distances between the opponent's territory and the marked regions)

The Maze AI algorithm is not very good at tactical decisions, because it ignores the size of the regions. That's why it uses the Difference AI algorithm for the last few moves of a game, where tactical strength is all that matters.

The Java Color Expansion Project

The aim of this project is to find the strongest possible AI for the game. There are already two other projects trying to reach this goal, Color Expansion and Alpha Better. Java Color Expansion is an open source project. That means you can download the source code and use it or the knowledge gained from it in your own programs. The source code is protected by the Gnu General Public License (which basically says every program that makes use of the source code must be open source as well and the author of the original source code cannot be held responsible for malicious modifications of his/her code by other persons).

Program Requirements

The program requires jre, the Java Runtime Environment, to run. If your browser is able to execute Java applets, you probably have it on your computer already. Otherwise you can download it here ( find your system in the list, then pick the download link in the jre column ).

Details about the Program

The program has three different modes, "normal", "AI match" and "client". The "normal" mode is used when none of the players is a connection to a remote server, at least one of the players is a human or "Rounds per AI match" is not set to a number. In "normal" mode only one game is played each time the "New game" button is pressed, with player 1 starting in the lower left corner, player 2 starting in the upper right corner and player 1 making the first move. At the end of the game the winner and the score each player achieved is displayed (the first number is the score of player 1). The program uses the "AI match" mode if both players are AIs (or remote clients) and "Rounds per AI match" is set to a number. In "AI match" mode, the program will let the AIs play as many games as "Rounds per AI match" says. Each generated board is played twice, with reversed roles to make sure the end scores will not be influenced by the board setups or by who started. The first time a board is played, player 1 starts in the lower left corner, player 2 starts in the upper right corner and player 1 makes the first move. The second time a board is played, player 2 starts in the lower left corner, player 1 starts in the upper right corner and player 2 makes the first move. In this mode, the number of games each AI won will constantly be displayed (the first number is the number of games player 1 won). The "client" mode is used when one of the players is a connection to a remote server. In this mode, the remote server controls how many games are played, whether a game is over and who's turn it is.

Project Page

Download Game

Artificial Intelligence

About this Project

Other Color Expansion projects

Color Expansion

Color Expansion. Fast Gamer.

Alpha Better

ColorSnatch

Other Projects

Blood Bowl League

Tube Blazer