Game tree public interface

This is a discussion on Game tree public interface within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Does anyone know what public interface I should have for a game tree? I mean a game tree that could ...

  1. #1
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446

    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.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  2. #2
    Even death may die... Dante Shamest's Avatar
    Join Date
    Apr 2003
    Location
    Malaysia
    Posts
    970
    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.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  4. #4
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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?
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>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.

  7. #7
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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;
    }
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 06-18-2009, 05:58 AM
  2. Game Engine Link Prob
    By swgh in forum Game Programming
    Replies: 2
    Last Post: 01-26-2006, 12:14 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM
  5. Exporting Object Hierarchies from a DLL
    By andy668 in forum C++ Programming
    Replies: 0
    Last Post: 10-20-2001, 02:26 PM

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