Tron Bot Nuts & Bolts – Full Source

Below is the full sourcecode to my tron bot. The final tournament is currently under way.

My bot uses a fairly basic minimax function with alpha beta cut offs. When both bots are competing for the same space, the evaluation function tries to control more space by being closer to more squares than the opponent. When the 2 bots cannot reach each other, it looks for longest reachable path. When someone runs into a wall, the win() or lose() functions return the value, which are very extreme values offset slightly by the depth at which they are reached.

The search uses iterative deepening to utilize as much time as possible. After the first depth is searched, subsequent searches poll frequently as to not run out of time. The polling functions tries to adjust its frequency to try poll once every 10-50 milliseconds. The search times out at 950 milliseconds.

Here is the source. It may differ slightly from the actual code at the last submission.

// MyTronBot.cc
//
// This is the code file that you will modify in order to create your entry.

#include "Map.h"
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <stdlib.h>

#include <setjmp.h>
#include <sys/time.h>
#include <time.h>

#define WIN 		 1000000
#define LOSE		-1000000
#define DRAW		0

typedef enum { LP_RETURN_ONE, LP_RETURN_FLOODFILL } longestPathStrategy;

int g_time_limit = 950;

// forward declaration...
class visitedMap;

jmp_buf g_jmp;
timeval g_start_timeval;
int g_poll = 0;

int best_move_index_full_search = 0;

visitedMap * g_scratch_map_me = NULL;
visitedMap * g_scratch_map_op = NULL;
visitedMap * g_scratch_map = NULL;

int max(int a, int b)	{ return ( a > b ) ? a : b; }
int min(int a, int b)	{ return ( a < b ) ? a : b; }

int g_move_count = 0;

struct move { int dx; int dy; const char * direction; } g_moves[] =
{
	{ 1, 0, "EAST" },
	{ 0, 1, "SOUTH" },
	{ 0,-1, "NORTH" },
	{-1, 0, "WEST" },
};

struct queue_item { int x; int y; int d; } foo_queue[50*50*4];
int q_top = 0;
int q_bot = 0;

void queue_clear()
{
	q_top = 0;
	q_bot = 0;
}

void queue_add( int x, int y, int d )
{
	foo_queue[q_bot].x = x;
	foo_queue[q_bot].y = y;
	foo_queue[q_bot].d = d;
	q_bot++;
}

int queue_take( int * x, int * y, int * d )
{
	*x = foo_queue[q_top].x;
	*y = foo_queue[q_top].y;
	*d = foo_queue[q_top].d;
	q_top++;
}

int queue_emptyp()
{
	return ( q_top == q_bot );
}

int g_prev_elapsed = 0;

int get_elapsed()
{
	struct timeval tv_now;
	gettimeofday( &tv_now, NULL );
	int d_sec = tv_now.tv_sec - g_start_timeval.tv_sec;
	int d_usec = tv_now.tv_usec - g_start_timeval.tv_usec;
	return d_sec * 1000 + d_usec / 1000;
}

void poll()
{
	static int frequency = 200;
	static int n = 0;
	if ( ++n % frequency == 0 )
	{
		int e0 = get_elapsed();

		if ( e0 > g_time_limit )
			longjmp( g_jmp, 1 );

		if ( g_prev_elapsed )
		{
			int delta = e0 - g_prev_elapsed;
			if ( delta > 50 )
				frequency = max(frequency-100,500);
			else if ( delta < 10 )
				frequency = min(frequency+100,5000);
		}
		g_prev_elapsed = e0;
	}
}

int win( int depth ) 	{ return WIN  - depth; }
int lose( int depth ) 	{ return LOSE + depth; }
int draw( int depth ) 	{ return DRAW /*+ depth*/;  }

class visitedMap
{
private:
	void init( int width, int height )
	{
		m_width			= width;
		m_height	   	= height;
		mapData			= (int*)malloc(byteCount());
	}

public:
	visitedMap( const Map & map )
	{
		init( map.Width(), map.Height() );

		for ( int y = 0; y < m_height; y++ )
		{
			for ( int x = 0; x < m_width; x++ )
			{
				if ( map.IsWall(x,y) )
					visit(x,y);
				else
					unvisit(x,y);
			}
		}
	}

	visitedMap( visitedMap * map )
	{
		init( map->width(), map->height() );
		takeValues( map );
	}

	visitedMap( int width, int height )
	{
		init( width, height );
		clear();
	}

	~visitedMap()					{ free(mapData); }

	void clear()					{ memset( mapData, 0, byteCount() ); }

	size_t byteCount()				{ return m_height*m_width*sizeof(int); }
	int width()						{ return m_width; }
	int height()					{ return m_height; }
	size_t offset( int x, int y ) 	{ return y*m_width+x; }

	void visit( int x, int y ) 		{ mapData[offset(x,y)] = -1; }
	void unvisit( int x, int y )	{ mapData[offset(x,y)] = 0;	}

	int value( int x, int y ) 		{ return mapData[offset(x,y)]; }
	void set( int x, int y, int v )	{ mapData[offset(x,y)] = v; }

	void takeValues( visitedMap * other ) {	memcpy( mapData, other->mapData, byteCount() );	}

	int visited( int x, int y )
	{
		/*
		if ( x < 0 ) return 1;
		if ( x >= m_width ) return 1;
		if ( y < 0 ) return 1;
		if ( y >= m_height ) return 1;
		*/
		return mapData[offset(x,y)];
	}

	// count total reachable squares from x,y...
	// depth first search...
	// returns the number of squares, but messes up matrix...
	int countAvailable( int x, int y )
	{
		if ( visited( x, y ) )
		{
			return 0;
		}
		else
		{
			visit( x, y );
			int r = 1;
			r += countAvailable( x+1, y );
			r += countAvailable( x-1, y );
			r += countAvailable( x, y+1 );
			r += countAvailable( x, y-1 );
			return r;
		}
	}

	void print( FILE * f, int mx, int my, int ox, int oy )
	{
		for ( int y = 0; y < height(); y++ )
		{
			for ( int x = 0; x < width(); x++ )
			{
				if ( x == mx && y == my )
					fprintf(f,"M");
				else if ( x == ox && y == oy )
					fprintf(f,"O");
				else
					fprintf(f,"%c", visited(x,y) ? '#' : ' ' );

			}
			fprintf(f,"\n");
		}
	}

	void printValues( FILE * f )
	{
		for ( int y = 0; y < height(); y++ )
		{
			for ( int x = 0; x < width(); x++ )
			{
				fprintf(f,"%3d ", value(x,y));
			}
			fprintf(f,"\n");
		}
	}

	static int manhattan_distance( int x0, int y0, int x1, int y1 )
	{
		return abs(x1-x0)+abs(y1-y0);
	}

	int is_reachable( int sx, int sy, int ex, int ey )
	{
		if ( sx == ex && sy == ey )
			return 1;
		if ( visited( sx, sy ) )
			return 0;
		else
		{
			visit( sx, sy );
			return is_reachable( sx+1, sy, ex, ey ) ||
				is_reachable( sx-1, sy, ex, ey ) ||
				is_reachable( sx, sy-1, ex, ey ) ||
				is_reachable( sx, sy+1, ex, ey );
		}
	}

	int has_overlap( int mx, int my, int ox, int oy )
	{
		g_scratch_map->takeValues( this );
		return g_scratch_map->is_reachable( mx, my, ox, oy );
	}

	// fill each square with the minimize number of move to reach it...
	// breadth first search...
	void fillDistances( int x0, int y0, int d0 )
	{
		queue_clear();
		queue_add( x0,y0,d0 );
		do
		{
			int x,y,d;
			queue_take(&x,&y,&d);

			if ( 0 == value(x,y) )
			{
				set( x, y, d );
				queue_add( x+1,y,d+1 );
				queue_add( x-1,y,d+1 );
				queue_add( x,y-1,d+1 );
				queue_add( x,y+1,d+1 );
			}
		} while (!queue_emptyp());
	}

	int longestPathSearch( int x, int y, int d, longestPathStrategy strategy, int * best_move )
	{
		if ( g_poll ) poll();

		// dont need to bother checking offboard... just look for a wall...
		if ( visited(x,y) )
			return 0;

		if ( d <= 0 )
		{
			// just return 1...
			if ( strategy == LP_RETURN_ONE )
			{
				return 1;
			}
			// degrade to counting available squares when we out of depth...
			else if ( strategy == LP_RETURN_FLOODFILL )
			{
				g_scratch_map->takeValues( this );
				return g_scratch_map->countAvailable(x,y);
			}
			else
			{
				exit(-1);
			}
		}

		// find the longest subpath reachable from here and add one for this square...
		visit(x,y);
		int mx = 0;
		for ( int i=0; i<4; i++ )
		{
			int dx = g_moves[i].dx;
			int dy = g_moves[i].dy;
			int v0 = longestPathSearch(x+dx,y+dy,d-1,strategy,NULL);

			if ( v0 > mx )
			{
				mx = v0;
				if ( best_move )
					*best_move = i;
			}
		}
		unvisit(x,y);
		return mx+1;
	}

	int longestPath( int x, int y )
	{
		return longestPathSearch(x,y,width()*height(),LP_RETURN_ONE,NULL);
	}

	int non_overlap_evaluate( int mx, int my, int ox, int oy, int depth )
	{
		int m = longestPathSearch(mx,my,depth,LP_RETURN_FLOODFILL,NULL);
		int o = longestPathSearch(ox,oy,depth,LP_RETURN_FLOODFILL,NULL);

		// only return win() / lose() if we searched to an endpoint...
		if ( ( m > o ) && ( o <= depth ) )
			return win(depth);
		if ( ( o > m ) && ( m <= depth ) )
			return lose(depth);
		else
			return 10 * (m - o);
	}

	int evaluate( int mx, int my, int ox, int oy )
	{
	    if ( !has_overlap( mx, my, ox, oy ) )
		{
			return non_overlap_evaluate(mx,my,ox,oy,4);
		}
		else
 		{
			g_scratch_map_me->takeValues( this );
			g_scratch_map_op->takeValues( this );

			g_scratch_map_me->fillDistances( mx, my, 1 );
			g_scratch_map_op->fillDistances( ox, oy, 1 );

			int advantage = 0;

			for ( int y = 0; y < height(); y++ )
			{
				for ( int x = 0; x < width(); x++ )
				{
					// ignore walls
					if ( !visited(x,y) )
					{
						int me = g_scratch_map_me->value(x,y);
						int op = g_scratch_map_op->value(x,y);
						int dt = abs(me-op);

						if ( !me && !op )
							advantage += 0;
						else if ( !me )
							advantage -= 10;
						else if ( !op )
							advantage += 10;
						else if ( me < op )
							advantage += 10;
						else if ( op < me )
							advantage -= 10;
					}
				}
			}

			return advantage;
		}
	}

private:
	int m_width;
	int m_height;
	int * mapData;
};

class payOffMatrix : public visitedMap
{
public:
	payOffMatrix() : visitedMap(4,4)	{}

	int bestDirections( int * bestMin, int * bestTot )
	{
		int maxmin = 0;
		int maxtot = 0;
		int maxmin_index = 0;
		int maxtot_index = 0;

		for ( int i = 0; i < 4; i++ )
		{
			int min=0;
			int tot=0;

			for ( int j = 0; j < 4; j++ )
			{
				int n = value(i,j);
				tot += n;
				if ( j == 0 || n < min )
					min = n;
			}

			if ( i == 0 || min > maxmin )
			{
				maxmin = min;
				maxmin_index = i;
			}
			if ( i == 0 || tot > maxtot )
			{
				maxtot = tot;
				maxtot_index = i;
			}
		}

		if ( bestMin )
			*bestMin = maxmin_index;
		if ( bestTot )
			*bestTot = maxtot_index;
	}

	void print( FILE * f )
	{
		int maxmin = 0;
		int maxtot = 0;
		int maxmin_index = 0;
		int maxtot_index = 0;

		for ( int i = 0; i < 4; i++ )
		{
			fprintf( f, "%6s\t", g_moves[i].direction);
			int min=0;
			int tot=0;
			for ( int j = 0; j < 4; j++ )
			{
				int n = value(i,j);
				fprintf(f,"%7d\t",n);
				tot += n;
				if ( j == 0 || n < min )
					min = n;
			}

			if ( i == 0 || min > maxmin )
			{
				maxmin = min;
				maxmin_index = i;
			}
			if ( i == 0 || tot > maxtot )
			{
				maxtot = tot;
				maxtot_index = i;
			}

			fprintf(f,"\tmin: %7d\taverage: %7d",min,tot/4);
			fprintf(f,"\n");
		}

		fprintf(f,"maxmin: %7d - %s\n",maxmin,g_moves[maxmin_index].direction);
		fprintf(f,"maxtot: %7d - %s\n",maxtot,g_moves[maxtot_index].direction);
		if ( maxmin_index != maxtot_index )
			fprintf(f,"DIFFERENCE IN TOTAL / MAXMIN DIRECTIONS!\n");
	}
};


int search( visitedMap * map, int depth, int mx, int my, int ox, int oy, int best_min, payOffMatrix * payOff )
{
	if ( g_poll ) poll();

	if ( mx == ox && my == oy )
		return draw( depth );

	int me_crash = map->visited( mx, my );
	int op_crash = map->visited( ox, oy );

	if ( me_crash && op_crash )
		return draw(depth);
	else if ( me_crash )
		return lose(depth);
	else if ( op_crash )
		return win(depth);
	else if ( depth <= 0 )
		return map->evaluate(mx,my,ox,oy);
	else if ( !map->has_overlap(mx,my,ox,oy) )
		return map->non_overlap_evaluate(mx,my,ox,oy,depth+2);

	map->visit( mx, my );
	map->visit( ox, oy );

	// int best_move = LOSE * 2;
	int best_move = payOff ? LOSE * 2 : best_min;

	for ( int i_ = 0; i_ < 4; i_++ )
	{
		int i = i_;
		int this_move = WIN * 2;

		for ( int j_ = 0; j_ < 4; j_++ )
		{
			int j = j_;

			int v = search( map, depth - 1,
							mx + g_moves[i].dx,
							my + g_moves[i].dy,
							ox + g_moves[j].dx,
							oy + g_moves[j].dy,
							best_move,
							NULL
				);

			if ( payOff )
				payOff->set(i,j,v);

			this_move = min( this_move, v );

			// alpha-beta style pruning occurs here...
			if ( !payOff && ( v <= best_move ) )
				break;
		}

		best_move = max(best_move,this_move);
	}

	map->unvisit( mx, my );
	map->unvisit( ox, oy );

	return best_move;
}

std::string MakeMove(const Map& map)
{
	static int two_player_start_search_depth = 2;
	static int longest_path_start_search_depth = 4;
	bool print_eval_info = false;

	// get time asap for accuracy...
	gettimeofday( &g_start_timeval, NULL );

	visitedMap scratch0( map );
	visitedMap scratch1( map );
	visitedMap scratch2( map );

	g_scratch_map_me	= &scratch0;
	g_scratch_map_op	= &scratch1;
	g_scratch_map		= &scratch2;

	g_time_limit = (g_move_count == 0) ? 2500 : 950;

	int mx = map.MyX();
	int my = map.MyY();

	int ox = map.OpponentX();
	int oy = map.OpponentY();

	visitedMap v( map );

	// if the maps do not overlap, just try to find the optimal path...
	if ( !v.has_overlap( mx, my, ox, oy ) )
	{
		g_poll = 0;
		int n;

		if ( setjmp( g_jmp ) == 0 )
		{
			for ( n = longest_path_start_search_depth; ; n++ )
			{
				int best_move_index = 0;
				int lp = v.longestPathSearch(mx,my,n,LP_RETURN_FLOODFILL,&best_move_index);
				best_move_index_full_search = best_move_index;

				// we searched past the depth of available moves...
				if ( lp < n )
				{
					if ( print_eval_info )
						fprintf(stderr,"longest path found: %d\n", lp);
					break;
				}

				g_poll = 1;

				if ( n > longest_path_start_search_depth + 2 )
				{
					longest_path_start_search_depth = min(10,longest_path_start_search_depth);
				}
			}
		}
		else
		{
			if ( print_eval_info )
				fprintf(stderr,"ran out of time - depth: %d\n", n);
		}
	}
	else
	{
		best_move_index_full_search = 0;
		g_poll = 0;

		if ( setjmp( g_jmp ) == 0 )
		{
			for ( int search_depth = two_player_start_search_depth; ; search_depth+= 2 )
			{
				visitedMap vm( map );
				payOffMatrix payOff;

				g_prev_elapsed = 0;

				int best_move_value = search( &vm, search_depth, mx, my, ox, oy, LOSE * 2, &payOff );

				payOff.bestDirections( &best_move_index_full_search, NULL );

				if ( print_eval_info )
				{
					fprintf(stderr,"Pay Off Matrix [Depth %d]\n",search_depth);
					payOff.print(stderr);

					fprintf(stderr,"M%02d - [D%02d] - %7d - %s\n", g_move_count, search_depth, best_move_value,
							g_moves[best_move_index_full_search].direction);
				}

				g_poll = 1;

				if ( search_depth > two_player_start_search_depth + 4 )
				 	two_player_start_search_depth = min(7,two_player_start_search_depth+1);
			}
		}
	}

	int x2 = mx+g_moves[best_move_index_full_search].dx;
	int y2 = my+g_moves[best_move_index_full_search].dy;

	// try to find a valid move if the search failed...
	if ( map.IsWall(x2,y2) )
	{
		for ( best_move_index_full_search = 0; best_move_index_full_search < 4; best_move_index_full_search++ )
		{
			int i = best_move_index_full_search;
			x2 = mx+g_moves[i].dx;
			y2 = my+g_moves[i].dy;
			if ( !map.IsWall( x2, y2 ) )
				break;
		}
	}

	g_move_count++;

	return g_moves[best_move_index_full_search].direction;
}

// Ignore this function. It is just handling boring stuff for you, like
// communicating with the Tron tournament engine.
int main() {
	while (true) {
		Map map;
		Map::MakeMove(MakeMove(map));
	}
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *