Alpha-Beta Tron

alpha_beta.h

//---------------------------------------------------------
//  Generalised Alpha-Beta Search Algorithm Implementation
//---------------------------------------------------------
//  by Steven Mark Rose
// Description:
// An alpha-beta search class finds the optimal move, given this information:
// search depth     : integer   : How many ply the tree will search to
// game             : class     : A world state class. Must have function move_count which returns the possible amount of moves given the current state and push_event which applies the given move (index) to the world state.
// adapter          : class     : A utility functor

#pragma once

#include "srlogserver.h"

template<class T, class U>
class alpha_beta
{
public: 
    alpha_beta(int maximum_ply, T& f, U& s):
            max_ply(maximum_ply), ply(0), t(f), e(s), count(0)
    {
        max=t.current_player();
        t.set_max();
    }

    ~alpha_beta()
    {
        autolog("alpha-beta search complete", smr::log::information);
    }

    int go()
    {
        return tau(0);
    }
    
    static int search(int maximum_ply, T& f, U& e) // Returns the best move for player
    {
        alpha_beta<T,U> ab(maximum_ply, f, e);
        return ab.go();
    }
    
    int tau(int alpha)
    {
        int keep(0); // keep is ultimatly the value we return to the parent
        if(t.is_terminal() || ply>=max_ply)
        {
            keep=e.utility(t);
        }
        else
        {
            int local_alpha(0);
            int temp(0);
            ply++; // Increase the depth of the search for all the children
            t.push_event(0); keep=tau(keep); t.pop_event(0); local_alpha=keep;
            for(int i=1; i<t.move_count(); i++)
            {
                // Push the event e that moves us to state i:
                t.push_event(i);
                temp=tau(keep);
                // Pop the event e which will return our state:
                t.pop_event(i);
                if (t.current_player()==max)
                {
                    if(keep<temp) {keep=temp; if(ply==1)best_move=i;}
                    if(keep<alpha)
                    {
                        count++;
                        break;
                    } // This is the 'pruning' line
                }
                else
                {
                    if(keep>temp) keep=temp;
                    if(keep>alpha) {count++; break;}
                }
            }
            ply--;
        }

        if (ply==0)
        {
            return best_move;
        }

        return keep;
    }
private:
    int ply;        // The current depth of the search 
    int max_ply;    // The maximum allowed depth of the search
    int max;        // The MAX player
    T& t;
    U& e;
    int best_move;
    int count;
};

tron_ai.h

// Tron AI implementation that uses an alpha-beta search algorithm

#pragma once

#include "alpha_beta.h"
#include "tron_structs.h"
#include "srlogserver.h"
#include "agents.h"

#include <sstream>
#include <cmath>

namespace tron
{
    namespace alpha_beta
    {
        class simple
        {
        public:
            int utility(Tron & t)
                {return 8+(int)t.is_alive(t.get_max());}
        };

        class offensive
        {
        public:
            int utility(Tron & t)
                {
                    Position p1;
                    p1=t.player_position(t.get_max());
                    Position p2=t.player_position(t.next_player(t.get_max()));
                    int r=40;
                    r-=abs(p1.x-p2.x);
                    r-=abs(p1.y-p2.y);
                    if (t.is_alive(t.get_max())) r+=1000;
                    if (!t.is_alive(t.next_player(t.get_max()))) r+=2000;
                    return r;
                }
        };

        class defensive
        {
        public:
            int utility(Tron & t)
                {
                    Position p1;
                    p1=t.player_position(t.get_max());
                    Position p2=t.player_position(0);
                    int r=0;
                    r+=abs(p1.x-p2.x);
                    r+=abs(p1.y-p2.y);
                    if (t.is_alive(t.get_max())) r+=80;
                    return r;
                }
        };

        // This maximises its own traversable area, whilst decreasing the enemies area.
        class maximise
        {
        public:
        
            maximise(): checked(20,20)
            {
            }
            
            int utility(Tron & t)
            {
                checked.clear();
                score=100;
                tron=&t;
                Position p=t.player_position(t.get_max());
                flood_fill(p.x+1, p.y);
                flood_fill(p.x-1, p.y);
                flood_fill(p.x, p.y+1);
                flood_fill(p.x, p.y-1);

                Position p1;
                p1=t.player_position(t.get_max());
                Position p2=t.player_position(t.next_player(t.get_max()));
                score-=abs(p1.x-p2.x);
                score-=abs(p1.y-p2.y);

                score*=(int)t.is_alive(t.get_max());
                if (!t.is_alive(t.next_player(t.get_max()))) score+=2000;
                return score;
            }
            
            void flood_fill(int x, int y)
            {
                // Check if this square is out of bounds:
                if (x>19 || x<0)
                x=(x+20)%20;
                if (y>19 || y<0)
                y=(y+20)%20;

                // Check if this square has already been recursed:
                if (checked.at(x,y))
                {
                    return;
                }

                // Check if it is a piece, if so then return:
                block_storage& bl=tron->get_board();
                if (bl.check(Position(x,y)))
                {
                    return;
                }
                
                // Mark this square as checked (my territory)
                checked.set(x,y,true);
                // Check each of the four directions
                flood_fill(x-1, y);
                flood_fill(x, y-1);
                flood_fill(x+1, y);
                flood_fill(x, y+1);
                score++;
                }
                array_2d<bool> checked;
                int score;
                Tron * tron;
            };
    }
}