Yet another minimax tree for TicTacToe

Question

I have written a working minimax tree for Tic-Tac-Toe. What I have done so far is create a tree with end node having value 10, 0 or -10 base on win, lose or draw. After I create a tree I then determine the move based on depth first search which bubbles the end node value to root node. Based on the value received at the root node I determine which ever has the max possibility of winning (10 win or -10 loss or 0 for draw).

Before going into coding detail I would like to explain that I have another class called TicTacToe.cpp/hpp which runs the game engine. When the user selects single player and it's the computer's turn it calls

minimax(int &y, int &y, std::vector<std::vector<TicTacToe::state>> v);

function which will eventually determine x and y co-ordinates.

The minimax function takes x and y co-ordinate and the 2d-vector which has the present state of the tictactoe ( enum of HASX, HASO and EMPTY). This helps to determine which space is taken by what.

void Tree::minimax(int& x, int& y, std::vector<std::vector<TicTacToe::state> > v){

    bool turn  = true;
    std::shared_ptr<Node> n = std::make_shared<Node>();
    n->v   = v;
    n->val = 9999;
    int max   = -10000;

    // creates the tree
    create_tree(n, find_empty_vec(v), turn);         

    //  does the depth first search on the above tree    
    depth_first_search(n, turn);

    for(auto it = n->collect_nodes.begin(); it != n->collect_nodes.end(); it++){
        if((*it)->val == 10 || (*it)->val == 0) {
            if( (*it)->val > max){ 
                max = (*it)->val; 
                x = (*it)->x;
                y = (*it)->y;              
            }  
        }
    }
}

When minimax is called it eventually calls create_tree which create a tree. Tree is made of node

struct Node{
    // basically set of children this node have
    std::set<std::shared_ptr<Node>> collect_nodes;
    // stores current game state with each index 
    // containing either EMPTY, HASX or HASO
    std::vector<std::vector<TicTacToe::state> > v;
    int val; 
    int x;  
    int y;

};

The create_tree function takes the node which has snap shot of the tictactoe state.

// This function creates the minimax tree, ev is just the vector of 
// EMPTY space that are in n->v ( see struct node above )
void Tree::create_tree(std::shared_ptr<Node> n, std::vector<std::pair<int, int>> ev, bool turn){

    static int count = 0;
    // loss
    // game_state is function that determine who won, loss or draw
    // by looking at the 2d vector that I have passed here.
    if(game_state(n->v) == 1){
        n->val = -10;
        return;
    }
    // win
    else if(game_state(n->v) == 2){ 
        n->val = 10;
        return;
    }
    // draw
    else if(game_state(n->v) == 3){ 
        n->val = 0;       
        return;
    }
    for(auto it = ev.begin(); it != ev.end(); it++){

        if(turn) {
            // HASO turn
            std::shared_ptr<Node> node = std::make_shared<Node>();
            node->v = n->v;
            node->val = -9999;
            node->v[it->first][it->second] = TicTacToe::HASO;
            node->x = it->first;
            node->y = it->second;
            n->collect_nodes.insert(node);
            create_tree(node, find_empty_vec(node->v), false); 

        }else{
            std::shared_ptr<Node> node = std::make_shared<Node>();
            node->v = n->v;
            node->val = 9999;
            node->v[it->first][it->second] = TicTacToe::HASX;  
            node->x = it->first;
            node->y = it->second;
            n->collect_nodes.insert(node);

            create_tree(node, find_empty_vec(node->v), true);
        }

    }
}

After the tree has been made then I do the dfs over the tree

int Tree::depth_first_search(std::shared_ptr<Node> n, bool turn){
    if(n->val == -10 || n->val == 0 || n->val == 10) return n->val;
    else if(turn){
        int max = -10000000;  // I could use numeric_limits here
        for(auto it = n->collect_nodes.begin(); it != n->collect_nodes.end(); it++){
            if(depth_first_search(*it, false) > max) 
                max = depth_first_search(*it, false);
        }
        n->val = max;
        return max; 
    }else{
        int min = 10000000; 
        for(auto it = n->collect_nodes.begin(); it != n->collect_nodes.end(); it++){
            if(depth_first_search(*it, true) < min) 
                min = depth_first_search(*it, true);
        }
        n->val = min;
        return min;
    }
} 

I do have few concerns about the way I have done things here:

1. I create tree every time its computer's turn. I was thinking about reusing previously dynamically allocated node tree by reassigning with new state. ( I am still confused what should be root in those case, since I have to determine which node in the tree determine the current state of tictactoe)

2. Is the dfs algorithm I have used a good design or good way to do ? It would be great if someone critique on it.

3. I also wanted to create a difficulty level like easy, moderate and hard so user can pick those level to play.

For more detail you can visit the my git repo.

Answer 1

1. I create tree every time its computer's turn. I was thinking about reusing previously dynamically allocated node tree by reassigning with new state.

No, I would not do that. You could, but you would have to store the entire tree structure in memory, which can get very huge. Instead you can 'build' the tree while you search it and only store what you need (see below).

1. I am still confused what should be root in those case, since I have to determine which node in the tree determine the current state of tictactoe

If you really want to store the tree in memory, selecting a root node is simple. You traverse the tree until you find any node that matches your current game state (a tupel made of std::vector<std::vector<TicTacToe::state> > v and turn). There will be multiple nodes satisfying this criteria, which one you pick does not matter, as the subtrees are identical. Such a state fullfills the Markov Property and thus history doesn't matter.

2. Is the dfs algorithm I have used a good design or good way to do ? It would be great if someone critique on it.

Sort of. Its almost the standard recursive DFS for a given tree, but has a substential flaw:

if(depth_first_search(*it, false) > max) 
    max = depth_first_search(*it, false);

Visiting every subtree twice means a lot of extra work for nothing. Instead do

double temporary = depth_first_search(*it, false);
if(temporary > max) 
    max = temporary;

and you should see an immediate performance boost. I prefer the iterative way of searching, as stated below.

3. I also wanted to create a difficulty level like easy, moderate and hard so user can pick those level to play.

The default way to create difficulty levels is to limit search time or depth. You would have to reimplement your search, because it does not come up with temporary solutions. (see below)

Instead you could, based on a chance, make a random move instead of searching for the best one. This would allow players to outmanouver the AI. Alternatively you could pick a 'bad' move on purpose (to make it look less random).

---

As promised I want to breefly sketch out how you can combine the creation and search of the tree in a way that (I think) is quite beautiful:

struct Node {
    // game state
    std::vector<std::vector<TicTacToe::state> > game_state;
    bool turn;

    // misc and utility values
    double value;
    bool is_terminal;
    action move;                                // which action brought us to this node
    std::vector<std::shared_ptr<Node>> history; // what nodes did we visit to come here
};

action find_move(std::set<std::shared_ptr<Node>> initial_state, bool turn, double search_time) {
    Queue search_nodes; // initialize right queue here (stack, FILO, priority queue, ...)
    search_nodes.push(initial_state);

    action best_move = choose_random_move();
    std::shared_ptr<Node> best_node;

    while (!search_nodes.isEmpty() && search_time > 0) {
        std::shared_ptr<Node> current_element = search_nodes.pop();

        if current_element.is_terminal{
            bool found_better_move = false;

            // this loop is special for minimax
            for (each history_node in reversed current_element->history) {
                if (history_node->turn) {
                    //maximize
                    if (current_element->value > history_node->value) history_node->value = current_element->value;
                    else break;
                }
                else {
                    //minimize
                    if (current_element->value < history_node->value) history_node->value = current_element->value;
                    else break;
                }
                found_better_move = true;
            }

            if (found_better_move) {
                best_move = current_element->history[2]->move; 
                best_node = current_element;
            }
            continue;
        }

        //add all childs to queue
        childs = get_all_childs(current_node);
        for (each child_node in childs) {
            search_nodes.push(child_node);
        }

        update_time(search_time);
    }
}

This implementation is beautiful because of its flexibilty. First of all I can easily add a maximum search time (or any other criteria) to change difficulty. Also depending on the type of Queue I can achieve different search behavior:

• Stack --> depth first search
• FIFO --> breadth first search
• Priority queue based on heuristic --> greedy search
• priority queue based on node values --> djikstra's algorithm
• priority queue based on node values + heuristic --> A*

The last options however are tricky in the minimax case, but come in handy in other scenarios. A thought is to use a stack, but sort the order in which childs of current_element are inserted. This can yield a massive performance boost when combined with pruning.

You also have several ways to do pruning. For alpha-beta-pruning the easiest is to check against the last two nodes in the history of a node. Their values give you alpha and beta.

Edit: Corrected alpha-beta pruning