WIP

beta_snake.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <deque>
#include <set>
#include <map>
#include <chrono>

using namespace std;


class Timer
{
public:
    Timer(const char* name) : beg_(clock_::now()), name_(name) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const {
        return std::chrono::duration_cast<ms_>
            (clock_::now() - beg_).count();
    }

    void print_elapsed()
    {
        fprintf(stderr, "%s: %.2f\n", name_.c_str(), elapsed());
    }
    
    ~Timer()
    {
        print_elapsed();
    }
private:
    string name_;
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::milli> ms_;
    std::chrono::time_point<clock_> beg_;
};


struct Cell
{
    float weight;
    int occupant; //-1 if free
};

const int Width = 30;
const int Height = 20;



void ClearPlayer(Cell board[Height][Width], int playerID)
{
    for(int i = 0; i < Height; ++i)
    {
        for(int j = 0; j < Width; ++j)
        {
            //Clear occupant since the guy died.
            if(board[i][j].occupant == playerID+1)
                board[i][j].occupant = 0;
        }
    }
}


void AddPlayerPosition(Cell board[Height][Width], int playerID, int x, int y)
{
    board[y][x].occupant = playerID+1;
}


void PrintBoard(Cell board[Height][Width])
{
    //cerr << setiosflags(ios::left);
    //cerr << setfill(' ');
    //cerr << setw(2);
    for(int i = 0; i < Height; ++i)
    {
        for(int j = 0; j < Width; ++j)
            cerr << setw(2) << board[i][j].occupant << " ";
        cerr << endl;
    }
    
    cerr << endl << "Weights:" << endl;
    for(int i = 0; i < Height; ++i)
    {
        for(int j = 0; j < Width; ++j)
           cerr << setw(2) << (int)board[i][j].weight << " ";
        cerr << endl;
    }
    cerr << resetiosflags(ios::left);
}

void GenerateWeights(Cell board[Height][Width])
{
    for(int i = 0; i < Height; ++i)
        for(int j = 0; j < Width; ++j)
            board[i][j].weight = 0.0f;
    
    for(int i = 0; i < Height; ++i)
    {
        for(int j = 0; j < Width; ++j)
        {
            if(board[i][j].occupant != 0 || (i == Height-1) || (j == Width-1) || j == 0 || i == 0)
            {
                //start decay of weights
                float weight = 16.0f;
                int step = 0;
                while(step < 3)
                {
                    weight = weight/3;
                    //Top side
                    int row = i - step;
                    if(row >= 0 && row < Height)
                    {
                        for(int x = j + step; x >= j - step; x--)
                            if(x >= 0 && x < Width )
                                board[row][x].weight += weight;
                    }
                    
                    //Left side
                    int column = j - step;
                    if(column >= 0 && column < Width)
                    {
                        for(int y = i - step + 1; y <= i + step - 1; y++)
                            if(y >= 0 && y < Height)
                                board[y][column].weight += weight;
                    }
                    
                    //Bottom side
                    row = i + step;
                    if(row >= 0 && row < Height)
                    {
                        for(int x = j - step; x <= j + step; x++)
                            if( x >= 0 && x < Width )
                                board[row][x].weight += weight;
                    }
                    
                    //Right side
                    column = j + step;
                    if( column >= 0 && column < Width )
                    {
                        for(int y = i - step + 1; y <= i + step - 1; y++)
                            if( y >= 0 && y < Height )
                                board[y][column].weight += weight;
                    }
                    
                    step++;
                }
            }
        }
    }
    
/*    float weight = 8.0f;
    for(int x = 0; x < Width; ++x)
    {
        for(int offset = 0; offset < 3; ++ offset)
        {
            board[offset][x].weight += weight;
            board[Height-offset][x].weight += weight;
            weight /= 2.0f;
        }
    }
    
    weight = 8.0f;
    for(int y = 0; y < Height; ++y)
    {
        for(int offset = 0; offset < 3; ++offset)
        {
            board[y][offset].weight += weight;
            board[y][Width-offset].weight += weight;
            weight /= 2.0f;
        }
    }
    */
}


struct Point
{
    Point()
    {
        x = y = 0;
        cost = 0.0f;
    }
    
    Point(int _x, int _y)
    {
        x = _x;
        y = _y;
        cost = 0.0f;
    }
    
    Point(int _x, int _y, float _cost)
    {
        x = _x;
        y = _y;
        cost = _cost;
    }
    
    Point(const Point& other)
    {
        x = other.x;
        y = other.y;
        cost = other.cost;
    }
    
    int x;
    int y;
    float cost;
};


Point LastResortDestination(Cell board[Height][Width], Point myPosition);

vector<Point> g_BannedPositions;

std::ostream& dump(std::ostream &o, const Point& p)
{
    return o << " (" << p.x << ", " << p.y << ")";
}


inline bool operator==(const Point& lhs, const Point& rhs)
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}


inline Point operator+(const Point& lhs, const Point& rhs)
{
    return Point(lhs.x+rhs.x, lhs.y+rhs.y);
}


inline Point operator-(const Point& lhs, const Point& rhs)
{
    return Point(lhs.x-rhs.x, lhs.y-rhs.y);
}


void Print(const Point& p)
{
    fprintf(stderr, "(%d, %d)", p.x, p.y);
}


void Print(const char* name, const vector<Point>& arr)
{
    fprintf(stderr, "%s size=%d: ", name, arr.size());
    for(const Point& p : arr)
    {
        fprintf(stderr, "(%d, %d) ", p.x, p.y);
    }
    fprintf(stderr, "\n");
}


#define USE_DIJ
vector<Point> GetPath(Cell board[Height][Width], Point start, Point dest)
{
    float Cost[Height][Width];
    for(int i = 0; i < Height; i++)
        for(int j = 0; j < Width; ++j)
            Cost[i][j] = 99999;
    
    vector<Point> visited;
    vector<Point> openList;
    openList.reserve(100);
    visited.reserve(100);
    
    openList.push_back(start);
    visited.push_back(start);
    typedef pair<int, int> Key;
    map< Key, Point > parents; 
    bool foundPath = false;
    
    while(!openList.empty())
    {
        
        Point current = Point(0, 0, 1000.0f);
        int min_idx = -1;
        for(int i = 0; i < openList.size(); ++i)
        {
            Point p = openList[i];
            if( p.cost < current.cost )
            {
                current = p;
                min_idx = i;
            }
        }
        if(min_idx != -1)
            openList.erase(openList.begin() + min_idx);
        
        
        if(current == dest)
        {
            //cerr<<"Found path" << endl;
            //Print("OpenList", openList);
        
            foundPath = true;
            break;
        }
        
        vector<Point> candidates = { Point(current.x, current.y-1), Point(current.x, current.y+1),
                            Point(current.x-1, current.y), Point(current.x+1, current.y) };
        
        //random_shuffle(candidates.begin(), candidates.end());
        
        for(Point& child : candidates)    
        {
            if( board[child.y][child.x].occupant == 0 
                && child.x >= 0 && child.y >= 0 && child.x < Width && child.y < Height)
            {
                float testCost = board[child.y][child.x].weight + current.cost;
                
                if( testCost< Cost[child.y][child.x])
                {
                    Cost[child.y][child.x] = testCost;
                    parents[Key(child.x, child.y)] = current;    
                }
               
                if(find(visited.begin(), visited.end(), child) == visited.end())
                {
                    visited.push_back(child);
                    openList.push_back(child);
                }
                
                /*
                cerr << "Current: "; Print(current); cerr << " Child: "; Print(child); cerr << endl;            
                cerr << "parents" << endl;
                for(auto& p : parents)
                {
                    cerr << "(" << p.first.first << ", " << p.first.second << ") ";
                    cerr << "->";
                    Print(p.second);
                    cerr << endl;
                }
                cerr << endl;
                */
            }
        }
        
        //Print("OpenList", openList);
        //Print("Visited", visited);
    }
    
    vector<Point> path;
    map<Key, Point>::iterator it;
    
    if(foundPath)
    {
        path.push_back(dest);
        Point node = dest;
        while( (it = parents.find(pair<int, int>(node.x, node.y))) != parents.end() )
        {
            path.push_back(it->second);
            node = it->second;
        }
    }
    
    reverse(path.begin(), path.end());
    
    return path;
}


const char* GenerateMove(const Point& start, const Point& dest)
{
    if(dest.x - start.x > 0)
        return "RIGHT";
    if(dest.x - start.x < 0)
        return "LEFT";
    if(dest.y - start.y < 0)
        return "UP";
    if(dest.y - start.y > 0)
        return "DOWN";
    
    return nullptr;
}



//Random valid path of minimum cost.
vector<Point> GetRandomPath(Cell board[Height][Width], Point myPosition)
{
    cerr<<"Getting random path" << endl;
    int tries = 0;
    vector<Point> path;
    int minSize = 50000;
    while(tries < 25)
    {
        Point dest = Point(rand()%Width, rand()%Height);
        vector<Point> test_path = GetPath(board, myPosition, dest);    
        if(test_path.size() > 1 && test_path.size() < minSize)
        {
            minSize = test_path.size();
            path = test_path;
        }
        tries++;
    }
    
    return path;
}


bool IsValidMove(Cell board[Height][Width], Point pos)
{
    return pos.y >= 0 && pos.y < Height && pos.x >= 0 && pos.x < Width && board[pos.y][pos.x].occupant == 0 && find(g_BannedPositions.begin(), g_BannedPositions.end(), pos) == g_BannedPositions.end();
}


bool visited[Height][Width];
int DFS(Cell board[Height][Width], Point startPos, int currentDepth, int max = 10000, bool debug = false)
{
    Point directions[] = { Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)};
    int maxDepth = currentDepth;
    
    if(currentDepth == 0)
    {
        for(int i = 0; i < Height; ++i)
            for(int j = 0; j < Width; ++j)
                visited[i][j] = false;
    }
    
#ifdef DEBUG_PRINT
        cerr  << maxDepth << endl;
#endif

    visited[startPos.y][startPos.x] = true;
    if (maxDepth > max)
        return maxDepth;

    for( Point& d : directions)
    {
        Point p = startPos+d;
        
#ifdef DEBUG_PRINT
            cerr << "Trying pos "; Print(p); cerr << endl;
#endif
        
        if(IsValidMove(board, p) && visited[p.y][p.x] == false)
        {
            //visited[p.y][p.x] = true;
            int depth = DFS(board, p, currentDepth + 1, max, debug);
            if( depth > maxDepth )
                maxDepth = depth;
        }
    }
    
    //cerr << maxDepth << endl;
    return maxDepth;
}


//Number of nodes reachable from startPos;
unsigned int BFS(Cell board[Height][Width], Point startPos, unsigned int maxNodes = 100000)
{
    deque<Point> openList;
    openList.push_back(startPos);
    
    int distance[Height][Width];
    for(int i = 0; i < Height; ++i)
        for(int j = 0; j < Width; ++j)
            distance[i][j] = -1;
    
    distance[startPos.y][startPos.x] = 0;
    unsigned int count = 0;
    
    while(!openList.empty())
    {
        Point node = openList.front();
        openList.pop_front();
        
        Point directions[] = {Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)};
        for( Point& d : directions)
        {
            Point p = node + d;
            if(IsValidMove(board, p) && distance[p.y][p.x] == -1)
            {
                distance[p.y][p.x] = distance[node.y][node.x] + 1;
                count += 1;
                
                if(count >= maxNodes)
                    return count;
                    
                openList.push_back(p);
            }
        }
    }
    
    return count;
}


int ChoosePathIdx(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players)
{
    int min_idx = -1;
    int min_len = 9999;
    
    for(int i = 0; i < paths.size(); ++i)
    {
        const vector<Point>& path = paths[i];
        //Print("CandidatePath", paths[i]);
        
        if(path.size() < min_len)
        {
            min_len = path.size();
            min_idx = i;
        }
    }
    
    return min_idx;
}

int ChoosePathIdx3(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players)
{
    int min_idx = -1;
    int max_len = -1;
    
    for(int i = 0; i < paths.size(); ++i)
    {
        const vector<Point>& path = paths[i];
        //Print("CandidatePath", paths[i]);
        
        if(path.size() > max_len)
        {
            max_len = path.size();
            min_idx = i;
        }
    }
    
    return min_idx;
}


inline bool CompareSizes(const vector<Point>& a, const vector<Point>& b)
{
    return a.size() < b.size();
}

inline bool IsOnBoard(Point p)
{
    return p.x >= 0 && p.x < Width && p.y < Height && p.y >= 0;
}

int ChoosePathIdx2(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players)
{
    Timer t("ChoosePathIdx2");
    
    int idx = -1;
    int maxCount = -1;
    
    Point possibleDirs[] = {Point(1, 0), Point(0, 1), Point(0, -1), Point(-1, 0)};
    for(int i = 0; i < paths.size(); ++i)
    {
        const vector<Point>& path = paths[i];
        //Print("Candidate path", path);
        if(path.size() <= 1)
            continue;
        
        int minCount = 99999;
        
        for(const Point& player : players)
        {
            for(const Point& dir : possibleDirs)
            {
                Point p = player + dir;
                if(IsOnBoard(p))
                {
                    int prevOccupant = board[p.y][p.x].occupant;
                    int pathSpace = board[path[1].y][path[1].x].occupant;
                    board[p.y][p.x].occupant = 1;
                    board[path[1].y][path[1].x].occupant = 1;
                    
                    int count = BFS(board, path[1]);
//                    fprintf(stderr, "path search BFS count (idx=%d): %d\n", i, count);
                    if(count < minCount)
                    {
                        minCount = count; //Just take the minimum that we are left with if the enemy plays perfectly.
                        if( minCount < 10 )
                            g_BannedPositions.push_back(p);
                    }
                        
                    board[p.y][p.x].occupant = prevOccupant;
                    board[path[1].y][path[1].x].occupant = pathSpace;
                }
            }
        }
        
        if(minCount > maxCount)
        {
            //Best of the worse choices.
            maxCount = minCount;
            idx = i;
        }
    }   
    
    fprintf(stderr, "Free cells: %d \n", maxCount); //best choice no matter if enemy plays perfectly.
    if(maxCount < 10)
        return -1;
        
    return idx;
}


//Returns a path to annoy the closest player and kill him.
vector<Point> GetAnoyingPath(Cell board[Height][Width], vector<Point>& players, Point myPosition, const vector<Point>& candidateDestinations)
{
    Timer T("Destination Path search");
    vector< vector<Point> > paths;
    for(const Point& p : candidateDestinations)
    {
        if(!IsValidMove(board, p))
            continue;
            
        //if(reachableNodes < 300)
        {
            int prevOcupant = board[p.y][p.x].occupant;
            board[p.y][p.x].occupant = 1;
            
            int reachableNodes = BFS(board, myPosition);
            int depth = BFS(board, p);
            //fprintf(stderr, "MyReachableCount: %d, ReachableCount: %d\n", reachableNodes, depth);
        
            board[p.y][p.x].occupant = prevOcupant;

            if(depth < reachableNodes)
                continue;
        }
        
        vector<Point> path = GetPath(board, myPosition, p);
        if(path.size() > 1)
            paths.push_back(path);
    }
    T.print_elapsed();
    
    sort(paths.begin(), paths.end(), CompareSizes);
    int pathIdx = ChoosePathIdx2(board, paths, players);
        
    fprintf(stderr, "PathIdx= %d\n", pathIdx);

    if(pathIdx == -1)
    {
        vector<Point> tmp;
        tmp.push_back(myPosition);
        tmp.push_back(LastResortDestination(board, myPosition));
        return tmp;
    }
    
    return paths[pathIdx];
}


Point LastResortDestination(Cell board[Height][Width], Point myPosition)
{
    int maxDepth = 0;
    Point dest;
    
    Point candidates[] = {Point(1, 0), Point(0, 1), Point(0, -1), Point(-1, 0)};
    for(Point& c : candidates)
    {
        Point p = myPosition+c;
        
        if(!IsValidMove(board, p))
            continue;
        int depth = DFS(board, p, 0);
        //cerr << "Trying point: "; Print(p); cerr << " Depth: " << depth <<  endl;
        if(depth > maxDepth)
        {
            maxDepth = depth;
            dest = p;
        }
    }
    
    cerr << "Trying random shit. Max depth: " << maxDepth << " Dest: "; Print(dest); cerr << " " << GenerateMove(myPosition, dest) << endl; 
    return dest;
}



bool IsStuck(Cell board[Height][Width], Point player, Point movePos)
{
    Point directions[] = {Point(0, -1), Point(0, 1), Point(1, 0),  Point(-1, 0)};
    
    int failed = 0;
    bool killed = false;
    for(Point& dir : directions)
    {
        Point move = dir + player;
        
        if(move == movePos)
        {
            if(!IsValidMove(board, move))
                failed++;
            killed = true;
        }
    }
    return failed == 4 && killed;
}

bool IsStuck2(Cell board[Height][Width], Point player, Point movePos, Point myPos)
{
    
    if(IsValidMove(board, movePos))
    {
        int prevCount = DFS(board, player, 0);
        int myPrevCount = DFS(board, myPos, 0);
        
        board[movePos.y][movePos.x].occupant = 1;
        
        int afterCount = DFS(board, player, 0);
        int myAfterCount = DFS(board, myPos, 0);
        
        board[movePos.y][movePos.x].occupant = 0;
        fprintf(stderr, "prevCount: %d, afterCount: %d, myPrevCount: %d, myAfterCount: %d\n", prevCount, afterCount, myPrevCount, myAfterCount);
        return afterCount < prevCount-15 && abs(myAfterCount-myPrevCount) < 20; 
    }
    return false;
}


/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    Cell Board[Height][Width];
    for(int i = 0; i < Height; ++i)
        for(int j = 0; j < Width; ++j)
            Board[i][j].occupant = 0;
    
    Point destination(0, 0, 10000.0f);
    srand(42);
    bool firstTime = true;
    vector<Point> prevPlayers;
    // game loop
    while (1) 
    {
        Timer t("Turn time");
        
        g_BannedPositions.clear();
        int N; // total number of players (2 to 4).
        int P; // your player number (0 to 3).
        
        Point myPosition;
        vector<Point> players;
        cin >> N >> P; cin.ignore();
        for (int i = 0; i < N; i++) 
        {
            int X0; // starting X coordinate of lightcycle (or -1)
            int Y0; // starting Y coordinate of lightcycle (or -1)
            int X1; // starting X coordinate of lightcycle (can be the same as X0 if you play before this player)
            int Y1; // starting Y coordinate of lightcycle (can be the same as Y0 if you play before this player)
            cin >> X0 >> Y0 >> X1 >> Y1; cin.ignore();
            
            fprintf(stderr, "X0=%d Y0=%d X1=%d Y1=%d\n", X0, Y0, X1, Y1);
            if(X1 == -1)
                ClearPlayer(Board, i);
            else
            {
                if(firstTime)
                    AddPlayerPosition(Board, i, X0, Y0);
                AddPlayerPosition(Board, i, X1, Y1);
            }
            
            GenerateWeights(Board);
            //PrintBoard(Board);
            
            if(i == P)
                myPosition = Point(X1, Y1);
            else
                players.push_back(Point(X1, Y1));
        }
        
        firstTime = false;
        
        Print("PrevPositions", prevPlayers);
        Print("Positions", players);
        
        cerr << "Finding path: "; Print(myPosition); cerr << endl;
            
        vector<Point> directions = {Point(0, -1), Point(0, 1), Point(1, 0),  Point(-1, 0)};//, Point(-1, -1), Point(1, 1), Point(1, -1), Point(-1, 1)};
        vector<Point> candidateDestinations;
        
        for(const Point& p : players)        
        {
            
            for(const Point& d : directions)
            {
                Point dest = p + d;
                if(IsValidMove(Board, dest) && (find(candidateDestinations.begin(), candidateDestinations.end(), dest) == candidateDestinations.end()))
                    candidateDestinations.push_back(dest);
            }
        }
        
        const int MaxPredictionDistance = 6;
        
        if(players.size() == prevPlayers.size())
        {
            for(int i = 0; i < players.size(); ++i)
            {
                if(!IsOnBoard(players[i]) || !IsOnBoard(prevPlayers[i]))
                    continue;
                
                Point newDir = players[i] - prevPlayers[i];
                for(int distance = 2; distance <= MaxPredictionDistance; ++distance)
                {
                    Point dir_tmp = newDir;
                    Point p = players[i]+dir_tmp;
                    vector<Point>::iterator it = find(candidateDestinations.begin(), candidateDestinations.end(), p);
                    if(it != candidateDestinations.end())
                    {
                        fprintf(stderr, "Removing destination: (%d, %d)\n", p.x, p.y);  
                        candidateDestinations.erase(it);
                    }
                    
                    dir_tmp.x *= distance;
                    dir_tmp.y *= distance;
                    dir_tmp = players[i] + dir_tmp;
                             
                    if(IsValidMove(Board, dir_tmp) && (find(candidateDestinations.begin(), candidateDestinations.end(), dir_tmp) == candidateDestinations.end()))
                        candidateDestinations.push_back(dir_tmp);
                    else
                        break;
                }
            }    
        }
        
        const char* move = nullptr;
        bool done = false;
        for(const Point& dir : directions)
        {
            if (done)
                break;
            Point newPos = dir + myPosition;
            for(const Point& player: players)
            {
                if(IsStuck2(Board, player, newPos, myPosition))
                {
                    move = GenerateMove(myPosition, newPos);
                    fprintf(stderr, "Found killer move:  (%d, %d)->(%d, %d) Killing(%d, %d): %s\n;", myPosition.x, myPosition.y, newPos.x, newPos.y, player.x, player.y, move);
                    cout << move << endl;
                    done = true;
                    break;
                }
            }
        }
        
        if(done)
            continue;
        
        Print("Candidate destinations", candidateDestinations);
        vector<Point> path = GetAnoyingPath(Board, players, myPosition, candidateDestinations);
        
        prevPlayers = players;
       
        //Print("Path", path);      
        float totalCost = 0.0f;
        for(const Point& p : path)
            totalCost += p.cost;
        cerr << "Total path cost: " << totalCost << endl;    
        
        
        if(path.size() > 1)
        {
            move = GenerateMove(myPosition, path[1]);
        }
        else
        {
            //PrintBoard(Board);
            cerr <<"LAST RESORT!" << endl;
            move = "LEFT";
            
            Point dest = LastResortDestination(Board, myPosition);
                        
            move = GenerateMove(myPosition, dest);                 
        }
        
        cout << move << endl;
        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;
        
        //cout << "LEFT" << endl; // A single line with UP, DOWN, LEFT or RIGHT
        
    }
}




//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//MTCS stuff - start with minimax

typedef vector<Point> PointArray;
const Point directions[] = {Point(-1, 0), Point(1, 0), Point(0, 1), Point(0, -1)}; //Possible directions of expansion
const vector<PointArray> dirOptions;

/*
void GenerateDirCombinations()
{
    for(const Point& d1 : directions)
        for(const Point& d2: directions)
            for(const Point& d3: directions)
            {
                PointArray dirs = {d1, d2, d3);
                dirOptions.push_back(dirs);
            }
}
*/

class GameState
{
public:
    GameState(): parent(nullptr), m_MaxState(true){}

    void GenerateChildren()
    {
        //Expand m_MaxPlayer
        Point player = m_MaxPlayer;

        if(!m_MaxState)
            player = m_MinPlayer; //Min state, expant m_MinPlayer

        for(const Point& dir : directions)
        {
            Point candidate = dir + player;
            if(!IsValidMove(m_Board, candidate))
                continue;

            GameState* newState = new GameState();

            newState->parent = this;
            
            for(int y = 0; y < Height; y++)
                for(int x = 0; x < Width; x++)
                    newState->m_Board[y][x].occupant = m_Board[x][y].occupant;
            
            //occupy it
            newState->m_Board[candidate.y][candidate.x].occupant = 1;
            newState->m_MaxState = !m_MaxState;
            
            if(m_MaxState)
            {
                //Max got to move to a new position.
                newState->m_MaxPlayer = candidate;
                newState->m_MinPlayer = m_MinPlayer;
            }
            else
            {
                //Min got to move to a new position.
                newState->m_MaxPlayer = m_MaxPlayer;
                newState->m_MinPlayer = candidate;
            }

            newState->m_Depth = m_Depth + 1;

            m_Children.push_back(newState);
        }
    }
    
    int Evaluate()
    {
        m_MaxDestination = m_MaxPlayer;
        m_MinDestination = m_MinPlayer;

        if(m_MaxState)
            return EvaluateMaxState();
        else
            return EvaluateMinState();
    }

    int EvaluateMinState()
    {
        int min = 9999;

        if(CanGenerateChildren())
        {
            GenerateChildren();

            for(GameState* child : m_Children)
            {
                if(!child)
                    continue;
                int val = child->Evaluate();
                if(val < min)
                {
                    min = val;
                    m_MinDestination = child->m_MinDestination;
                }
            }
        }
        else
        {
            //Heuristics
            return DFS(m_Board, m_MinPlayer, 0) - DFS(m_Board, m_MaxPlayer, 0);
        }

        return min;
    }

    int EvaluateMaxState()
    {
        int max = -1;

        if(CanGenerateChildren())
        {
            GenerateChildren();

            for(GameState* child : m_Children)
            {
                if(!child)
                    continue;
                int val = child->Evaluate();
                if(val > max)
                {
                    m_MaxDestination = child->m_MaxPlayer;
                    max = val;
                }
            }
        }
        else
        {
            //Heuristics
            return DFS(m_Board, m_MaxPlayer, 0) - DFS(m_Board, m_MinPlayer, 0);
        }
    }

    bool CanGenerateChildren()
    {
        return m_Depth < 4;
    }

    ~GameState()
    {
        for(GameState* child : m_Children)
            delete child;
    }

public:
    Point   m_MaxDestination;
    Point   m_MinDestination;

    int     m_Depth;
    bool    m_MaxState;
    Cell     m_Board[Height][Width];
    Point   m_MaxPlayer; //End positions where the players are now.
    Point   m_MinPlayer;
    GameState* parent;
    vector<GameState*> m_Children;
};


//Gets us a score based on if players die and we stay alive. maxDepth on each branch !!!
int EvaluateState(Cell board[Height][Width], GameState* state, int maxDepth = 50, bool max_turn = true)
{
    return 0;
};


void ConstructTree(Cell board[Height][Width], Point myPosition, const PointArray& enemies)
{
    //I move first (now), since it's my update... Assume enemies move in the order from the array.
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////