Game tree public interface

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.

Thanks.

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.

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.

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?

http://www.cs.caltech.edu/~petrovic/...dir/node2.html

>>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.

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.

Code:

---

# 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 {
    public:
    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 {
    public:
    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 {
  public:
  gen_list() {}
  void operator()(const MiMxData& mmd, vector<move>& move_list) {

  }
};

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

class gen_mmd {
    public:
    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;

    MM_gen_move_list(mmd,move_list);

    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_);
    else
        chosen_score = best_score;
}

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

    // initialize mmd...

    minimax<gen_list,gen_mmd,eval>(mmd,s,m);

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

    return 0;
}

---