First, this article explains the rationale behind the bot architecture designed in CodinGame-Scala-Kit. Then, we demonstrate this architecture style with some code.

What‘s a bot?

A bot is a computer program. It communicates with a referee system. A referee system controls two or more bots.
The referee defines game rules. It distributes the game state to bots, collects bot actions and updates the game. It continues the distribute-collect-update loop until the game is over.

Bot design principles

The following design principles are driven by challenges in bot programming. Each of the principles aims to tackle one problem from a given perspective. The final architecture proposition should take into account the principles.

Separation of concerns

As explained above, a bot should

• communicate with the referee system
• model the game domain such as game rules, state, action
• implement a fighting strategy

Among these concerns, the communication mechanism is strictly constrained by the referee system. We have more flexibility on domain modeling but game rules must be respected. The strategy is the heart of the bot and it’s where we can be creative. On one hand, separating these concerns allows us to distinguish the fixing and moving parts. On the other hand, it helps us to invest time and efforts on the right module.

Debugging

Debugging helps developers to diagnosis a bot’s behavior. However, bot is often executed in a remote server. Even if it’s possible to write some logs, the debugging capabilities are still limited. If we managed to replay the game in developer’s local environement, all debugging issues would be resolved. Therefore, the achitecture should enable developers to write replayable codes.

Performance

In most games, one wins the game if he/she looks ahead more steps than others. Better performance leads to better result. As we know, premature optimization is root of all evil for performance tuning tasks. The proposed architecture should make benchmarking and profiling easy to setup.

Simulation

A well designed game should have a large action space. A game is playable when one cannot figure out a winning strategy within a reasonable amount of time.

Given that most of time, it’s extremely difficult to solve a problem analytically, we often adopt an approach where we try a possible action and check how good it is. To know if an action is a good one, we need to play what-if scenarios. In a what-if scenario, we impact an action on a given state and then assess the quality of the updated game state. Playing a what-if scenarios is called a simulation.

Architecture

Input/Output

The Input/Output layer handles communication with the referee system. It reads input to state and write action to output.

State/Action

Inside the I/O layer, we can find the domain layer where we model the game state and action. They are pure input and output data for the bot logic. All I/O related side effects are removed.

Bot logic

The Bot module is a logic module that is reponsable to make action decisions upon game state change. It’s where most work should be done.

Separating the concerns into I/O, Model and Logic layer helps us to meet our requirements on debugging, performance, and simulation.

• Debugging: to replay a game locally, we only need to serialize the state object
• Performance: to benchmark the performance of bot logic, we only need to provide the serialized state object
• Simulation: the simulator takes action and existing state as input, and produces an updated state

Show me some codes

The following code examples are taken from CodinGame-Scala-Kit.

I/O

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

trait GameIO[Context, State, Action] {
  /**
    * Reads game context from the referee system. A context stores game's global information
    */
  def readContext: Context

  /**
    * Reads current state from the referee system. A state provides information for the current turn
    */
  def readState(turn: Int, context: Context): State

  /**
    * Writes action to the referee system
    */
  def writeAction(action: Action)
}

Bot

1
2
3
4
5
6
7
8
9

trait GameBot[State, Action] {
  /**
    * Reacts to the given game state by playing one or more actions
    *
    * @param state current state of the game
    * @return one or more actions to play
    */
  def react(state: State): Action
}

Accumulator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

trait GameAccumulator[Context, State, Action] {

  /**
    * Accumulates information derived from the current state into a new game context
    * that will be used in the next round.
    *
    * In certain cases, the input state doesn't include all required information.
    * These information must be calculated from historical actions and states.
    * For example, it could be action cool down, observed positions in fog of war.
    *
    * @param context the current context which may contain historical events.
    * @param state   the current state
    * @param action actions performed for the current round
    * @return a new context accumulated with historical events including those generated from the current round
    */
  def accumulate(context: Context, state: State, action: Action): Context
}

Simulation

1
2
3
4
5
6
7
8
9
10
11
12

trait GameSimulator[State, Action] {
  /**
    * Impacts the provided action on the given state and
    * produces a new state according to the defined game rule
    *
    * @param state   the starting state
    * @param action action selected based on the starting state
    * @return an updated state after action impact
    */
  def simulate(state: State, action: Action): State

}

Debugging

For more details on how state is serialized, refer to my first post on Debugging in CodinGame-Scala-Kit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

object WondevPlayerDebug {

  def main(args: Array[String]): Unit = {

    val bot = WondevPlayer(true)
    val state = WondevState(
      context = WondevContext(6, 2),
      turn = 1,
      heights = Map(
        Pos(2, 5) -> 48, Pos(1, 5) -> 48, Pos(5, 0) -> 48, Pos(0, 2) -> -1, Pos(0, 0) -> 48),
      myUnits = List(Pos(3, 0), Pos(3, 4)),
      opUnits = List(Pos(3, 2), Pos(5, 1)),
      legalActions = List(
        MoveBuild(0, S, N), MoveBuild(0, S, NW), MoveBuild(0, S, SE), MoveBuild(0, S, SW))

    bot.react(state)

  }
}

Benchmark

Benchmarking and profiling is powered by JMH, Sbt-JMH plugin and Java Flight Recorder.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
  * jmh:run -prof jmh.extras.JFR -i 1 -wi 1 -f1 -t1 WondevBenchmark
  */
@State(Scope.Benchmark)
class WondevBenchmark {

    val bot = MinimaxPlayer
    val state = WondevState(
      context = WondevContext(6, 2),
      turn = 1,
      heights = Map(
        Pos(2, 5) -> 48, Pos(1, 5) -> 48, Pos(5, 0) -> 48, Pos(0, 2) -> -1, Pos(0, 0) -> 48),
      myUnits = List(Pos(3, 0), Pos(3, 4)),
      opUnits = List(Pos(3, 2), Pos(5, 1)),
      legalActions = List(
        MoveBuild(0, S, N), MoveBuild(0, S, NW), MoveBuild(0, S, SE), MoveBuild(0, S, SW))

    @Benchmark
    def wondevMinimax(): Unit = {
        bot.reactTo(state)
    }

}

Conclusion

The architecture proposal is influenced by ideas in functional programming such as

• side effects isolation
• data and logic separation

Please feel free to leave your comments.

After competing in serveral Bot Contests in CodinGame, I started to learn meta-heuristics(aka modern heuristics). I implemented an evolutionary algorithm (lamba, mu) in the Coders Strike Back multi-game(ranked 55 at time of writing this post). I find that designing the evaluation function is most tough and also creative part when we adopt a meta-heuristic based approach.

In this post, I will share some insights gained from crafting the evaluation function in the CSB game.

What is an evaluation function?

Meta-heuristics (such as genetic algorithms, hill-climbing, simulated annealing) are used for problems where you don’t know how to find a good solution, but if shown a candidate solution, you can give it a grade.

To grade a solution, we use Evaulation Function.

Tips

Situational

Most of time, we can have mutliple stages in a game such as early game, middle game and late game. A good candidate solution in the early game is not necessarily a good one in late game. In addition to stages, we can also stand in differnt positions such as winning, losing positions. If you are winning, you may want to enforce your position by being more defensive. On the contrary, if you are losing, it’s better to risk all your resources to reverse that situation.

Therefore, avoid applying the same and universal evaluation function all the time. Make it situational.

Prefer small value and small coefficient

Don’t use huge numbers because we are not good at reason about huge numbers.

For example, we want to evaluate the distance between two objects. They can be tens of thousands meters far away from eatch other. How to transform the distance to small numbers?

My favorite function is the expotention function with a small base. For instance, Math.pow(0.999, 1234) ~= 0.3. It feels much better to compare 0.3 with 0.9 instead of comparing 15123 to 53492.

See and Feel the numbers

Don’t just look at the formula. Open your debugger, see and feel the numbers to make sure they are relavant. Feeling those numbers helps a lot to tune your formula.

Bonus vs Malus

Instead of using positive numbers for bonus and negative numbers for malus, always think in terms of positive score. Only in the end, subtract malus from bonus. This helps to you to stick with one reference system.

Conclusion

There are still many areas that I need to explore such as how to weight different coeffcients, how to design multi-objective functions. I will add more lessons here when I play and win more games.

In CodinGame, code is executed on server side. This makes debugging a luxury. In this post, I’ll share how to debug your Bot with Scala’s case class.

Feed Game State to Bot

In CodinGame Scala Kit, we model Bot as a function which maps game state to actions. Therefore, to debug the Bot locally, we only need to feed it with the game state. The following example shows how I debug my Caribbean Bot:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

object CaribbeanPlayerDebug {

  def main(args: Array[String]): Unit = {
    val state = CaribbeanState(
      CaribbeanContext(Map(), Map(2 -> 50, 0 -> 39)),
      Map(0 -> Ship(0, Offset(8, 12), 1, 2, 64, 1)
        , 2 -> Ship(2, Offset(10, 11), 2, 1, 50, 1)
        , 1 -> Ship(1, Offset(20, 10), 4, 2, 67, 0)
        , 3 -> Ship(3, Offset(17, 16), 5, 2, 59, 0)),
      Map(),
      Map(59 -> Ball(59, Offset(12, 14), 3, 1)
        , 60 -> Ball(60, Offset(14, 17), 2, 2)),
      Map(5 -> Mine(5, Offset(14, 12))
        , 29 -> Mine(29, Offset(7, 8))
        , 61 -> Mine(61, Offset(15, 12))
        , 38 -> Mine(38, Offset(4, 10))
        , 7 -> Mine(7, Offset(12, 16))
        , 51 -> Mine(51, Offset(14, 10))
        , 4 -> Mine(4, Offset(14, 8))), 51)

    val player = CaribbeanPlayer(1, 0, new CountStopper(100))
    println(player.reactTo(state))
  }
}

Data as Code

In scala, when you print a case class, you get a magic string because it can re-instantiate the case class itself. To feed your bot, just print the game state.
As shown in the GameLoop, we print the game state at line13.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class GameLoop[C, S, A](
                         controller: GameController[C, S, A],
                         myPlayer: GamePlayer[S, A]
                       ) {
  def run(): Unit = {
    val time = System.nanoTime()
    val initContext = controller.readContext
    controller.warmup(myPlayer)
    System.err.println("GameInit elt: " + (System.nanoTime() - time) / 1000000 + "ms")
    (1 to 200).foldLeft(initContext) {
      case (c, turn) =>
        val state = controller.readState(turn, c)
        System.err.println(state)
        val time = System.nanoTime()
        val actions = myPlayer.reactTo(state)
        System.err.println("GameReact elt: " + (System.nanoTime() - time) / 1000000 + "ms")
        actions.foreach(a => println(a))
        val context = controller.nextContext(c, state, actions)
        context
    }
  }

}

Another real-world example in Ghost-in-the-Cell contest: