Grid War
This page provides an example of using the OakGP genetic programming Java framework to evolve suitable candidates for a two-player game named "Grid War".
For an overview of OakGP please read the getting started with OakGP guide.
Problem Description
Grid War is a two-player turn-based zero-sum board game. It is played on a 4x4 grid. Players take turns to move. Players can move one square at a time in one of four directions (up, down, left or right). If a player selects a move that would cause them to exit the board then they forfeit their turn. A player wins if they move to a square that is already occupied by their opponent. A player loses if they move in the same direction on two consecutive moves.
The game is described in the O'Reilly book "Programming Collective Intelligence" by Tony Segaran (ISBN 978-0-596-52932-1). View extract.
Approach
The following classes were created to represent the components of a Grid War game:
Player
- stores the board position and previous move of a player in a game.GridWar
- an implementation of org.oakgp.rank.tournament.TwoPlayerGame
which contains the Grid War game logic used to determine the comparative fitness of potential solutions.
The genetic programming run is configured in GridWarExample
using a org.oakgp.util.RunBuilder
.
Configuration
Return Type
Type | Description |
---|
integer | Indicates which direction (up, down, left or right) the player should move next. |
Variable Set
ID | Type | Description |
---|
v0 | integer | X coordinate of player to move next. |
v1 | integer | Y coordinate of player to move next. |
v2 | integer | Previous move of player to move next, or -1 if not yet moved. |
v3 | integer | X coordinate of opponent of player to move next. |
v4 | integer | Y coordinate of opponent of player to move next. |
v5 | integer | Previous move of opponent of player to move next, or -1 if not yet moved. |
Constant Set
Type | Values |
---|
integer | 0, 1, 2, 3, 4 |
Function Set
Class: | org.oakgp.function.choice.If |
Symbol: | if |
Return Type: | integer |
Arguments: | boolean, integer, integer |
Class: | org.oakgp.function.compare.Equal |
Symbol: | = |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.compare.GreaterThan |
Symbol: | > |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.compare.GreaterThanOrEqual |
Symbol: | >= |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.compare.LessThan |
Symbol: | < |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.compare.LessThanOrEqual |
Symbol: | <= |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.compare.NotEqual |
Symbol: | != |
Return Type: | boolean |
Arguments: | integer, integer |
Class: | org.oakgp.function.math.Add |
Symbol: | + |
Return Type: | integer |
Arguments: | integer, integer |
Class: | org.oakgp.function.math.Multiply |
Symbol: | * |
Return Type: | integer |
Arguments: | integer, integer |
Class: | org.oakgp.function.math.Subtract |
Symbol: | - |
Return Type: | integer |
Arguments: | integer, integer |
Java Source Code
org/oakgp/examples/gridwar/Player.javapackage org.oakgp.examples.gridwar;
import static org.oakgp.examples.gridwar.GridWar.GRID_WIDTH;
import org.oakgp.node.Node;
class Player {
private final Node logic;
private int x;
private int y;
private int previousMove = -1;
Player(int x, int y, Node logic) {
this.x = x;
this.y = y;
this.logic = logic;
}
void updateState(int nextMove) {
previousMove = nextMove;
switch (nextMove) {
case 0:
up();
break;
case 1:
right();
break;
case 2:
down();
break;
case 3:
left();
break;
default:
throw new IllegalArgumentException("Invalid move: " + nextMove);
}
}
private void up() {
if (y > 0) {
y--;
}
}
private void down() {
if (y < GRID_WIDTH - 1) {
y++;
}
}
private void left() {
if (x > 0) {
x--;
}
}
private void right() {
if (x < GRID_WIDTH - 1) {
x++;
}
}
int getPreviousMove() {
return previousMove;
}
Node getLogic() {
return logic;
}
int getX() {
return x;
}
int getY() {
return y;
}
}
org/oakgp/examples/gridwar/GridWar.javapackage org.oakgp.examples.gridwar;
import org.oakgp.Assignments;
import org.oakgp.node.Node;
import org.oakgp.rank.tournament.TwoPlayerGame;
import org.oakgp.util.Random;
class GridWar implements TwoPlayerGame {
static final int GRID_WIDTH = 4;
private static final int NUMBER_OF_POSSIBLE_DIRECTIONS = 4;
private static final int MAX_MOVES = 24;
private static final int WIN = 1;
private static final int LOSE = -WIN;
private static final int NO_WINNER = 0;
private final Random random;
GridWar(Random random) {
this.random = random;
}
@Override
public double evaluate(Node playerLogic1, Node playerLogic2) {
Player[] players = createPlayers(playerLogic1, playerLogic2);
int moveCtr = 0;
int currentPlayerIdx = 0;
while (moveCtr++ < MAX_MOVES) {
Player player = players[currentPlayerIdx];
Player opponent = players[1 - currentPlayerIdx];
int moveOutcome = processNextMove(player, opponent);
if (moveOutcome != NO_WINNER) {
return currentPlayerIdx == 0 ? moveOutcome : -moveOutcome;
}
currentPlayerIdx = 1 - currentPlayerIdx;
}
return NO_WINNER;
}
private Player[] createPlayers(Node playerLogic1, Node playerLogic2) {
int x = random.nextInt(GRID_WIDTH);
int y = random.nextInt(GRID_WIDTH);
Player player1 = new Player(x, y, playerLogic1);
Player player2 = new Player((x + 2) % GRID_WIDTH, (y + 2) % GRID_WIDTH, playerLogic2);
return new Player[] { player1, player2 };
}
private static int processNextMove(Player player, Player opponent) {
Assignments assignments = createAssignments(player, opponent);
int nextMove = getNextMove(player, assignments);
if (isRepeatedMove(player, nextMove)) {
return LOSE;
}
player.updateState(nextMove);
if (isWon(player, opponent)) {
return WIN;
}
return NO_WINNER;
}
private static int getNextMove(Player player, Assignments assignments) {
int result = (int) player.getLogic().evaluate(assignments);
return Math.abs(result % NUMBER_OF_POSSIBLE_DIRECTIONS);
}
private static Assignments createAssignments(Player playerToMoveNext, Player opponent) {
return Assignments.createAssignments(playerToMoveNext.getX(), playerToMoveNext.getY(), playerToMoveNext.getPreviousMove(), opponent.getX(),
opponent.getY(), opponent.getPreviousMove());
}
private static boolean isRepeatedMove(Player currentPlayer, int nextMove) {
return currentPlayer.getPreviousMove() == nextMove;
}
private static boolean isWon(Player player, Player opponent) {
return player.getX() == opponent.getX() && player.getY() == opponent.getY();
}
}
org/oakgp/examples/gridwar/GridWarExample.javapackage org.oakgp.examples.gridwar;
import static org.oakgp.Type.integerType;
import static org.oakgp.util.Utils.createIntegerTypeArray;
import org.oakgp.Type;
import org.oakgp.function.Function;
import org.oakgp.function.choice.If;
import org.oakgp.function.compare.Equal;
import org.oakgp.function.compare.GreaterThan;
import org.oakgp.function.compare.GreaterThanOrEqual;
import org.oakgp.function.compare.LessThan;
import org.oakgp.function.compare.LessThanOrEqual;
import org.oakgp.function.compare.NotEqual;
import org.oakgp.function.math.IntegerUtils;
import org.oakgp.node.ConstantNode;
import org.oakgp.node.Node;
import org.oakgp.rank.RankedCandidates;
import org.oakgp.rank.tournament.FirstPlayerAdvantageGame;
import org.oakgp.rank.tournament.TwoPlayerGame;
import org.oakgp.util.JavaUtilRandomAdapter;
import org.oakgp.util.Random;
import org.oakgp.util.RunBuilder;
import org.oakgp.util.Utils;
public class GridWarExample {
private static final int NUM_VARIABLES = 5;
private static final int NUM_GENERATIONS = 10;
private static final int INITIAL_POPULATION_SIZE = 50;
private static final int INITIAL_POPULATION_MAX_DEPTH = 4;
public static void main(String[] args) {
Function[] functions = { IntegerUtils.INTEGER_UTILS.getAdd(), IntegerUtils.INTEGER_UTILS.getSubtract(), IntegerUtils.INTEGER_UTILS.getMultiply(),
LessThan.create(integerType()), LessThanOrEqual.create(integerType()), new GreaterThan(integerType()), new GreaterThanOrEqual(integerType()),
new Equal(integerType()), new NotEqual(integerType()), new If(integerType()) };
ConstantNode[] constants = Utils.createIntegerConstants(0, 4);
Type[] variables = createIntegerTypeArray(NUM_VARIABLES);
Random random = new JavaUtilRandomAdapter();
TwoPlayerGame game = new FirstPlayerAdvantageGame(new GridWar(random));
RankedCandidates output = new RunBuilder().setReturnType(integerType()).setConstants(constants).setVariables(variables).setFunctions(functions)
.setTwoPlayerGame(game).setInitialPopulationSize(INITIAL_POPULATION_SIZE).setTreeDepth(INITIAL_POPULATION_MAX_DEPTH)
.setMaxGenerations(NUM_GENERATIONS).process();
Node best = output.best().getNode();
System.out.println(best);
}
}
Output
Below are some examples of solutions generated by GridWarExample
.
Candidate 1 | Candidate 2 | Candidate 3 | Candidate 4 |
---|
(+ v2 (if (!= (- v1 v2) (+ v1 (if (<= v0 v1) 1 (+ v0 v2)))) 3 (+ v0 v2)))
| (+ v2 (if (= v1 (+ v2 (if (< (* -1 v4) 2) 2 3))) v1 3))
| (+ (- 1 v2) (* v4 (* v3 (* 2 v3))))
| (+ v2 (+ 5 (* 2 (if (= 2 v1) -1 (if (<= (+ 7 v2) (if (<= v2 v1) v0 4)) 1 v4)))))
|