Trees Go Brrr ~ The game tree search engine


browse  log 



You can also use your local clone with git send-email.


A game tree search engine.


To build, simply run:

$ make # TODO: Explain linking.


Simply run:

$ ./bin/tgb [options]


Running the test cases

$ make test


Given an engine to a game played with two players on a 2 dimensional board, we will use MPI and some sort of tree search/ optimization algorithm (most likely negamax with alpha beta pruning). To recursively search the game space, and return optimal moves, given a game state.

For more information go, have a look at

Thus, TGB Will link the engine at compile time, and the result is a binary which will find optimal moves for that given game using the above described methods.


Below are the current implemented engines that can be used with TGB.

  • Chess
  • TicTacToe (TODO).

#Engine Interface

Note, argument params and types are subject to change. This is simply a rough roadmap.

The game engine must provide the following functions. What follows is a rough specification of what this engine must provide.

The most up to date interface can be found in include/engine.h.

  • The board must be represented as a single dimension array, to access the co-ord we simply use mod and div appropriatly. E.G, given an n by n board. position 21 in the array indicates, x -> 2, y -> 1 on the board, note that the top left of the board is represented by 00, and bottom right by (n-1)(n-1). Reason: This makes copying board states trivial, and passing via MPI trivial as well, also a move is simply written as two ints (start point and end point). That being said, the engine must have an init function that returns the start board for the game.
    • Func Def: int *initgame()
  • Given a board state and a move, check to see if a given move is legal.
    • Func Def: int islegal(int *board, int *move)
  • Make a move, and return the new board state. Reason, some games can vastly alter the game state (think othello), and this should be abstracted to the game engine, the bot simply wants to see if a move is valid, and then get the game state after applying that move.
    • Func Def: int *move(int *board, int *move)
  • An eval function, I have not yet decided if this should come with the game engine, but as of now I think this will be the best place to package it. The purpose of the eval function will be to determine how good the game state is for the current player, higher int -> better state.
    • Func Def: int eval(int *board, int player)
  • Check the game state, given a board. (WIP, still deciding on struct).
    • Func Def: struct state *gamestate(int *board)
    • Struct: The struct state will have the following fields.
      • int winner;
        • -1: Game is still ongoing
        • 0: Player 0 won.
        • 1: Player 1 won.
        • 2: Draw.
      • int turn
        • 0: Player 0's turn
        • 1: Player 1's turn
      • void *other;

Certain games can have a move that results in a certain amount of steps that happen (e.g promoting a piece in chess), too handle this, the library should implement an event handler(s) which are simple function pointers which exec the given event.

This abstract bot will essentially be a more advanced version of what I implemented in my third year concurrency course, excepte it has the advantage of working given an engine for any game (that implemented the above interface correctly).

Given the above interface, the engine will allow us to implement a driver that will allow users to play the game, which by extension will allow us to implement a bot that plays the game against itself.