OakGP

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
Approach
Configuration
   Return Type
   Variable Set
   Constant Set
   Function Set
Java Source Code
Output

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:

The genetic programming run is configured in GridWarExample using a org.oakgp.util.RunBuilder.

Configuration

Return Type

TypeDescription
integerIndicates which direction (up, down, left or right) the player should move next.

Variable Set

IDTypeDescription
v0integerX coordinate of player to move next.
v1integerY coordinate of player to move next.
v2integerPrevious move of player to move next, or -1 if not yet moved.
v3integerX coordinate of opponent of player to move next.
v4integerY coordinate of opponent of player to move next.
v5integerPrevious move of opponent of player to move next, or -1 if not yet moved.

Constant Set

TypeValues
integer0, 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.java
package org.oakgp.examples.gridwar;

import static org.oakgp.examples.gridwar.GridWar.GRID_WIDTH;

import org.oakgp.node.Node;

/** Represents the current state of a player in a GridWar game. */
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.java
package org.oakgp.examples.gridwar;

import org.oakgp.Assignments;
import org.oakgp.node.Node;
import org.oakgp.rank.tournament.TwoPlayerGame;
import org.oakgp.util.Random;

/** Game engine for Grid War. */
class GridWar implements TwoPlayerGame {
   static final int GRID_WIDTH = 4;
   /** Number of possible directions a player can move in - up, down, left or right. */
   private static final int NUMBER_OF_POSSIBLE_DIRECTIONS = 4;
   /** The maximum number of moves without a winner before the game is considered a draw. */
   private static final int MAX_MOVES = 24;
   /** The reward assigned to a winning player. */
   private static final int WIN = 1;
   /** The penalty assigned to a losing player. */
   private static final int LOSE = -WIN;
   /** The reward assigned to both players of a drawn game. */
   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;
         }
         // each player takes it in turn to move
         currentPlayerIdx = 1 - currentPlayerIdx;
      }
      // no winner within maximum number of moves - draw
      return NO_WINNER;
   }

   private Player[] createPlayers(Node playerLogic1, Node playerLogic2) {
      // randomly position player 1
      int x = random.nextInt(GRID_WIDTH);
      int y = random.nextInt(GRID_WIDTH);
      Player player1 = new Player(x, y, playerLogic1);

      // randomly position player 2, ensuring they do not occupy the same or an adjacent square to player 1
      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)) {
         // duplicate move - lose
         return LOSE;
      }
      player.updateState(nextMove);
      if (isWon(player, opponent)) {
         // entered square already occupied by opponent - win
         return WIN;
      }
      return NO_WINNER;
   }

   private static int getNextMove(Player player, Assignments assignments) {
      int result = (int) player.getLogic().evaluate(assignments);
      // normalise the result to ensure it is in the valid range of possible moves
      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.java
package 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();
      // wrap a GridWar object in a FirstPlayerAdvantageGame to avoid bias
      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 1Candidate 2Candidate 3Candidate 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)))))
Home | Getting Started | Documentation | FAQs