PDA

View Full Version : Game tree public interface



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

Thanks.

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

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

IfYouSaySo
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?

Perspective
03-18-2005, 04:57 PM
http://www.cs.caltech.edu/~petrovic/games/archex/othellodir/node2.html

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

IfYouSaySo
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 {
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;
}