Cell Division

Introduction

Cell Addition is a strategy-based board game. All AI opponents implement a deterministic strategy that is greedy with respect to a value function. Games against a fixed difficulty AI opponent are reproducible. Players take turns placing their cells. A player’s cells divide when they connect with each other; vertical, horizontal and diagonal connections are allowed. Your score is equal to the total number of cell that you have on the board. The game ends when the board is full and the winner is the player with the most cells. There are three fixed-difficulty AI opponents and an adaptive opponent that plays differently depending on how well the player is doing. Cell Division was originally written using R Shiny. R Shiny is geared more towards interactive data analytics and is not well-suited for this type of game. The current implementation of the game is writen in plain HTML, CSS and Javascript. The code is available here and can be played here.

AI Opponent

All oppponent’s follow a greedy with respect to some value of a move. Since the objective is to maximize your score, it makes sense to approximate the long term benefit of a move with its immediate increase in score. It turn’s out that the increase in score can be decomposed in the a function of the following four variables:

  • \(\text{overlap}_p(\text{move})\) is the number of cells adjacent to a move,
  • \(\text{interlap}_p(\text{move})\) is the number of times the move is sandwitched by its cell and its opposite,
  • \(\text{extensions}_p(\text{move})\) is the number of existing connections that a move extends,
  • \(\text{unconnected}_p(\text{move})\) is the number of unconnected cells that a move connects,

and the formula is

\[\begin{split} \Delta \text{score}_p(\text{move}) &= \mathbb{I} \{\text{overlap}_p(\text{move})>1\} - \text{unconnected}_p(\text{move}) \\ &\quad + 2\cdot \big[\text{overlap}_p(\text{move}) - \text{interlap}_p(\text{move})\big] \\ &\quad + 2\cdot\big[ \text{overlap}_p(\text{move}) - \text{extensions}_p(\text{move}) \big], \end{split}\] where \(p\) denotes the player playing the move. By convention, define the first player (\(p=1\)) to be you and the second player (\(p=2\)) to be the AI
One benefit of this decomposition is that each of the variables can be updated in an online fashion.

Additional player-independent variables that have intuitive value are:

  • \(\text{openness}(\text{move})\) is move number of open positions adjacent to a move,
  • \(\text{centrality}(\text{move})\) measures how close a move is to the center of the board.

To calculate a value of a move, the AI opponent uses a weighted sum of the above variables.

Easy, Medium and Hard Opponents

Cell Addition is a zero sum game and so your gain is the same as the AI’s loss. Thus, when designing the AI, it will be beneficial to take this into account.

The easy AI’s value function is simply \[ \text{easy}(\text{move}) = \text{centrality}(\text{move}); \] that is, the easy AI just places it’s move in the center most position of the board with ties broken arbitrarily.

The hard AI’s value function is \[ \begin{split} \text{hard}(\text{move}) & = \text{centrality}(\text{move}) + 2\cdot \text{openness}(\text{move})\\ & \quad + \big[ \Delta \text{score}_2(\text{move}) + \Delta \text{score}_1(\text{move}) \big]\\ &\quad - \big[ \text{overlap}_2(\text{move}) + \text{overlap}_1(\text{move}) \big] . \end{split} \] The idea is to find a tradeoff between exploration and exploitation. To see this, consider the following formula for the increase in the total overlap of a board when playing \(\text{move}\) \[ \Delta\text{total_overlap}_p(\text{move}) = \text{openness}_p(\text{move}) - \text{overlap}_p(\text{move}). \] The hard AI’s value can now be rewritten as \[ \begin{split} \text{hard}(\text{move}) & = \text{centrality}(\text{move}) \\ & \quad + \big[ \Delta \text{score}_2(\text{move}) + \Delta \text{score}_1(\text{move}) \big]\\ & \quad + \big[ \Delta\text{total_overlap}_2(\text{move}) + \Delta\text{total_overlap}_1(\text{move}) \big] . \end{split} \] The two first two terms after \(\text{centrality}\) encourage exploitation of the current game state while the last two terms encourage exploration of the board.

The medium AI’s value is the average of the easy and hard opponent’s values; i.e., \[ \text{medium}(\text{move}) = 0.5\cdot \text{hard}(\text{move}) + 0.5\cdot \text{easy}(\text{move}) . \]

Adaptive AI

The adaptive AI has a skill level which determines the overall strategy in a game.

The adaptive AI adapts to your play in two ways:

  1. It adapts to your play within a game.
  2. It adapts its entire strategy after a game.

The adaptive AI uses a convex combination of the easy and hard AI’s value.
\[ \text{adaptive}(\text{move}) = \text{skill}' \cdot \text{hard}(\text{move}) + (1 - \text{skill}') \cdot \text{easy}(\text{move}), \] where \(\text{skill}'\) is modified (within-game) skill parameter

\[ \text{skill}' = \text{skill} + 0.01\cdot ( \text{your_score} - \text{ai_score} ). \] Notice that if you are winning, then the effective skill of the AI goes up. Moreover, if you are winning by a lot then the effective skill will go up by a lot.

At the end of the game, the AI’s skill level is updated according to the following formula: \[ \text{skill} \leftarrow \text{skill} + 0.01\cdot \frac{ \text{your_score} - \text{ai_score} }{1 + \mathbb{I} \{ \text{your_score} < \text{ai_score} \} }. \] Hence, if you beat the AI, then its skill goes up by the score difference; if you lose, then its skill goes down in proportion to half the absolute score difference. If the game is a draw, then the skill level stays the same.

Ignoring within-game adaptivity, when \(\text{skill}=0\) you are essentially playing against the easy AI, when \(\text{skill}=1\) you are playing against the hard AI, and when \(\text{skill}=0.5\) you are playing against the medium AI.