View Full Version : Game tree public interface

03-18-2005, 03:48 PM
Does anyone know what public interface I should have for a game tree? I mean a game tree that could be used with Minimax, etc. for a variety of turn-taking games of perfect information.

Am I correct in saying that the first task (if I am going to implement a game using Minimax) is to write a game_tree data structure? I just want to make sure that I am starting at the right place. From my understanding, Minimax and other algorighms are fairly strightforward, but usually they assume that some game tree already exists (I think).

I assume that I need to write a depth first search for whatever data structure I come up with (correct?). Also I would need to add and remove nodes, and get at the current node. Any other things needed?

Finally, if anyone knows of a good online resouce that explains this, feel free to just post that instead.


Dante Shamest
03-18-2005, 04:27 PM
You don't really need a data structure to do a minimax search. The minimax conceptually evaluates a game tree via recursion.

You might want to take a look at a source code for Tic-Tac-Toe here (http://fawx.com/software/defunct/files/minimax.htm).

03-18-2005, 04:45 PM
I've written several minimax's for various games and never have I used a physical data structure. The recursively called functions themselves can store the information and can be thought of as a node to a game-tree.

03-18-2005, 04:53 PM
Ah...Well I'm glad I didn't write it then!

BTW, thanks for the Tic-tac-toe link, I don't really want to look at the code too much, since that was what I was going to write myself, to be sure I understand. But maybe I will look when I am done.

So it sounds like the recommendation is just write the minimax is that right? And the only thing I guess I need is a board representation, and a candidate-move generator, and minimax?

03-18-2005, 04:57 PM

03-18-2005, 05:56 PM
>>So it sounds like the recommendation is just write the minimax is that right? And the only thing I guess I need is a board representation, and a candidate-move generator, and minimax?<<

You also need an evaluator, some kind of function that rates a board state and assigns it a number based on which player it thinks is winning and by how much. Its this number that drives the minimax function.

03-18-2005, 08:40 PM
Okay...so I was looking at the cal-tech example, but it was sort of hard to follow (being pseudo code, and no variable declarations, or explanations of what the abstract types are holding, etc.). But I used to as a starting point to write a C++ minimax function, where the generate-list, generate-move, and evaluate functions were template parameters that could be defined later. I'm really not sure if it's correct, because sometimes the cal-tech code was pretty fuzzy, and I just sort of made a guess at what would be the correct thing to do. Can someone take a look at this and see if it's more or less correct? It compiles, but does nothing at all, because the template functions are no-ops.

# include <vector>
using namespace std;

// or whatever is appropriate...
# define MAX_DEPTH 10

// Type definitions...dependent on the game I guess

// this depends on the game, but for example with
// chess using a bitboard this might be okay...?
typedef int64_t board;

class move {
move() {}
// assuming chess for a minute for kicks...
// src_ is the initial square, dst_ is the
// move destination square, and type_
// is the type of piece. Probably not exactly right,
// but...
int64_t src_;
int64_t dst_;
int type_;

class MiMxData {
MiMxData() {}
board board_;
int depth_;

// wouldn't this usually just be an int?
typedef int score;

// Functors that can be defined later to do the appropriate thing
// for whatever game is being coded

class gen_list {
gen_list() {}
void operator()(const MiMxData& mmd, vector<move>& move_list) {


class eval {
eval() {}
score operator()(const board& b) {
return 0;

class gen_mmd {
gen_mmd() {}
MiMxData operator()(const board& b, const move& m) {
// todo: depends on game
return MiMxData();

template <class MoveListFn, class MoveFn, class EvalFn>
void minimax(const MiMxData& mmd, score& chosen_score, move& chosen_move)
int best_score = -INT_MAX;
move best_move;
vector<move> move_list;

MoveListFn MM_gen_move_list;
MoveFn MM_move;
EvalFn MM_eval;


vector<move>::iterator end = move_list.end();
for (vector<move>::iterator itr = move_list.begin();
itr != end; itr++) {
// is this what they are trying to do?
// I.e. call a function that takes the current board
// and a move as input and return the resulting board?
MiMxData next_mmd = MM_move(mmd.board_,*itr);

// Now call minimax with next_board?
score next_score;
move next_move;
minimax<MoveListFn,MoveFn,EvalFn>(next_mmd, next_score, next_move);
if (next_score > best_score) {

best_score = next_score;

best_move = *itr;

// This is the move we pick
chosen_move = best_move;

// Call evalation function?
if (mmd.depth_ == MAX_DEPTH)
chosen_score = MM_eval(mmd.board_);
chosen_score = best_score;

int main()
MiMxData mmd;
score s;
move m;

// initialize mmd...


// and I assume that s should be the evaluation of
// the selected move, m should be the move that
// minimax selects?

return 0;