Hosted by imgur.com

Update: The contest is over, I finished 36th out of 708. That isn’t too bad, I suppose, but it’s not great either. I guess I can be happy about finishing in the top 50, and easily in the top 10%.

The University of Waterloo (in Canada) along with Google representatives is hosting a Tron A.I. programming contest. (Finals Tournament is on Feb. 26th, 2010). Having not participated in any programming contests since high school, I have decided to compete in this just to see how well I stack up. The basis behind this challenge is to create a Tron AI which will compete with other people’s submissions, so it becomes your program vs. every body else. The current rankings can be seen here, while my own personal page can be seen here. Bots are welcome to be programmed in a variety of languages, including C++, Java, Python, C#, Haskell, Go, Javascript, Perl, and others, however it’s been noted that the JVM the contest organizers are using is extremely slow, which is devastating when your bot is allowed only 1 second to move. So don’t make the same mistake I did, and use something other than Java.

You should learn from my mistake and not keep all of your source code stored on a personal server that doesn’t have some sort of X server installed. This is the first (and hopefully only) time in my life where I program an entire project using the nano text editor, rather than something sane like JCreator, Eclipse, or Visual Studio. I’ll admit the syntax coloring looks nice at first, but in reality, I like having line numbers. I mean, I really like having line numbers. And the ability to use my mouse. And not having to ssh into my server whenever I want to edit code. So from now on, I vow to only use real IDE’s. No more of this retro 70’s GNU ASCII text editor stuff.


 		It looks pretty, and seemed like a good idea at the time

Mmmk, here is the source code for my Java Bot (which sucks compared to my C++ bot, but was (and still can be) a most worthwhile learning experience.

First up is the Bug class, which, as the name implies, is used for debugging. Turning it on causes the S.O.P.’s to print to the console, turning it off causes the bot to be silent. Usage is just as a static function call would be, so Bug.ol(“blah blah”);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Bug
{
	private Bug(){} // no instantiating
	public static final boolean on = true;
	public static void ol(String str)
	{
		if(on)
			System.err.println(str);
	}
	public static void o(String str)
	{
		if(on)
			System.err.print(str);
	}
}

Next up is the Point class, which holds some additional information other than just X and Y coordinates. It also provides the manhattan distance between itself and another Point object, as well as returns an array of Points which are adjacent to that point, as well as returns the specific point one space away from a given direction 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

enum DIR { NORTH, SOUTH, EAST, WEST };
 
public class Point
{
	private int mX;
	private int mY;
 
	public Point(int x, int y)
	{
		mX = x;
		mY = y;
	}
 
	public Point(Point p)
	{
		mX = p.mX;
		mY = p.mY;
	}
	public int X() { return mX; }
	public int Y() { return mY; }
	public void setX(int x) { mX = x; }
	public void setY(int y) { mY = y; }
 
	public Point[] adjPointsToMe()
	{
		Point[] adjPs = new Point[4];
		int i = 0;
		for(DIR dir : DIR.values())
		{
			adjPs[i] = getAdjPoint(dir);
			i++;
		}
		return adjPs;
	}
 
	public Point getAdjPoint(DIR dir)
	{
		int x = mX;
		int y = mY;
		switch(dir)
		{
			case NORTH:
				return new Point(x,y-1);
			case SOUTH:
				return new Point(x,y+1);
			case EAST:
				return new Point(x+1,y);
			case WEST:
				return new Point(x-1,y);
			default:
				return null;
		}
	}
 
	public int manhattanDist(Point b)
	{
		return Math.abs(mX - b.mX) + Math.abs(mY - b.mY);
	}
 
	public boolean isNorthOf(Point b)
	{
		return ( this.mY < b.mY);
	}
 
	public boolean isSouthOf(Point b)
	{
		return ( this.mY > b.mY );
	}
 
	public boolean isEastOf(Point b)
	{
		return ( this.mX < b.mX);
	}
 
	public boolean isWestOf(Point b)
	{
		return ( this.mX > b.mX);
	}
 
	@Override
	public int hashCode()
	{
		final int prime = 31;
		int result = 1;
		result = prime * result + mX;
		result = prime * result + mY;
		return result;
	}
 
	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(getClass() != obj.getClass())
			return false;
		Point other = (Point)obj;
		if(mX != other.mX)
			return false;
		if(mY != other.mY)
			return false;
		return true;
	}
 
	public String toString()
	{
		return "[" + mX + "][" + mY + "]";
	}
}

Here we have the Move class, which is basically a Point but with a value member variable. What does that value represent? Good question, actually, because I abuse this class in a number of places, using it to represent for different kinds of values. At one point I tried to implement A* and there was a whole other Node class, but, that failed when I gave up on the implementation. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

import java.util.PriorityQueue;
//import java.util.Comparable;
 
public class Move implements Comparable<Move>
{
	private Point myPoint;
	private int myVal;
 
	public Move(Point p)
	{
		myPoint = p;
		myVal = 0;
	}
	public Move(Point p, int v)
	{
		myPoint = p;
		myVal = v;
	}
 
	public Point getPoint()
	{ return myPoint; }
 
	public PriorityQueue<Move> getAdjMoves()
	{
		PriorityQueue<Move> pq = new PriorityQueue<Move>();
		Point[] possPoints = myPoint.adjPointsToMe();
		Map map = new Map();
		for(int i=0; i < possPoints.length; i++)
		{
			Move temp = new Move(possPoints[i]);
			if(map.isValid(possPoints[i]))
				temp.myVal = -1000; // die
			else
			{
				// if enemy could move there, temp.myVal -= 50
				if(map.canEnemyMoveTo(temp.myPoint))
					temp.myVal = -500;
				 temp.myVal += map.openPtsFrom(new Point(possPoints[i].X(),possPoints[i].Y()));
			}
			pq.offer(temp);
		}
		return pq;
	}
 
	public int compareTo(Move other)
	{
		//Bug.ol("Move CompareTo called");
		if(myVal< other.myVal)
			return 1;
		else if(myVal > other.myVal)
			return -1;
		else
			return 0;
	}
 
	public void setValue(int i)
	{
		myVal = i;
	}
 
	public int getValue()
	{
		 return myVal;
	}
 
	@Override
	public int hashCode()
	{
		final int prime = 37;
		int result = myPoint.hashCode()*prime;
		result = myVal * prime * result;
		return result;
	}
	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(getClass() != obj.getClass())
			return false;
		Move other = (Move)obj;
		if(myVal != other.myVal)
			return false;
		if(! myPoint.equals(other.myPoint) )
			return false;
		return true;
	}
 
	@Override
	public String toString()
	{
		String t = myPoint.toString();
		t+= ": " + myVal;
		return t;
	}
}

Ah, the heart and soul of my Java Bot, the Map class. This isn’t the same map class that is provided with the starter kit. I renamed that to Tron.java so I could use the name “Map”. Everything here was designed and coded by yours truly, and it does a fairly good job if I may say so myself. Unfortunately, I failed at implementing A*, and so this relies somewhat on a very ghetto best – first algorithm for moving towards the opponent. That is why this is not a high ranking bot. It needs a better path finding algorithm. The flood fill algorithm on the other hand is top notch. Ish. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.lang.StringBuilder;
import java.util.LinkedList;
import java.util.ArrayList;
 
public class Map
{
	private Point me;
	private Point op;
	private char[][] walls;
	private int width;
	private int height;
 
	public Map()
	{// init to default values
		walls = Tron.getCharMap();
		me = new Point(Tron.MyX(),Tron.MyY());
		op = new Point(Tron.OpponentX(),Tron.OpponentY());
		width = Tron.Width();
		height = Tron.Height();
 
	}
 
	public Point getMe() { return me; }
	public Point getOp() { return op; }
 
	public Map(char[][] w, Point m, Point o)
	{
		height = w.length;
		width = w[0].length;
		me = m;
		op = o;
		// deep copy
		walls = new char[width][height];
		for(int r = 0; r < height; r++ )
			for(int c = 0; c < width; c++)
				walls[r][c] = w[r][c];
	}
 
	public boolean isClosedOff()
	{
		boolean ret = !openAtoB(me,op);
		Bug.ol("me: " + me + " , op: " + op + "  isClosedOff: " + ret);
		return ret;
	}
 
	public boolean canEnemyMoveTo(Point p)
	{
		Point[] possEnemyMoves = op.adjPointsToMe();
		Point[] possPMoves = p.adjPointsToMe();
		for(Point a : possEnemyMoves)
		{
			for(Point b : possPMoves)
			{
				if(a.equals(b))
					return true;
			}
		}
		return false;
	}
	public boolean openAtoB(Point a, Point b)
	{
		//Bug.o("Checking open from: " + a + " to: " + b );
		Queue<Point> openQueue = new LinkedList<Point>();
		Set<Point> closedQueue = new HashSet<Point>(); // no doubles!
		openQueue.offer(a);
		while(!openQueue.isEmpty())
		{
			//Bug.ol("here");
			Point p = openQueue.remove();
			//Bug.ol("comparing: " + p + " to " + b );
			closedQueue.add(p);
			if(nextToEachOther(p,b))
			{
				//Bug.ol(":  true");
				return true;
			}
			for(Point adjPoint : adjFreePointsTo(p))
			{
				if(!(openQueue.contains(adjPoint) || closedQueue.contains(adjPoint)))
					openQueue.offer(adjPoint);
			}
		}
		//Bug.ol(":  false");
		return false;
	}
 
	public int openPtsFrom(Point start)
	{
		int count = 0;
		Queue<Point> openQueue = new LinkedList<Point>();
		Set<Point> closedQueue = new HashSet<Point>();
		openQueue.offer(start);
		while(!openQueue.isEmpty())
		{
			Point p = openQueue.remove();
			closedQueue.add(p);
			count++;
			for(Point adjPoint : adjFreePointsTo(p))
				if(!(openQueue.contains(adjPoint) || closedQueue.contains(adjPoint)))
					openQueue.offer(adjPoint);
		}
		return count;
	}
 
	public boolean nextToEachOther(Point a, Point b)
	{
		Point[] pts = a.adjPointsToMe();
		for(Point n : pts)
		{
			if(n.equals(b))
			 return true;
		}
		return false;
	}
 
	public ArrayList<Point> adjFreePointsTo(Point point)
	{
		ArrayList<Point> adjfree = new ArrayList<Point>();
		for(Point t : point.adjPointsToMe())
		{
			if(isValid(t))
				adjfree.add(t);
		}
		return adjfree;
	}
 
	public boolean isValid(Point p)
	{ // not wall and not me and not enemy
		//Bug.o("width: " + width + ", height: " + height);
		if( (p.X() >= 0) && (p.X() < width) && (p.Y() >= 0) && (p.Y() < height))
		{
			//Bug.ol("isValid IB: " + p);
			return walls[p.X()][p.Y()] == ' ';
		}
		else
		{
			//Bug.ol("isValid OOB: " + p);
			return false; // out of bounds
		}
	}
 
	public DIR closeCombatDecision()
	{
		Move m = new Move(me);
		PriorityQueue<Move> bestMoves = m.getAdjMoves();
		Move t = bestMoves.peek();
		Point p = t.getPoint();
		Bug.ol("ccD bestMove Point: " + t.getPoint());
		if( me.getAdjPoint(DIR.NORTH).equals(p))
			return DIR.NORTH;
		if( me.getAdjPoint(DIR.SOUTH).equals(p))
			return DIR.SOUTH;
		if( me.getAdjPoint(DIR.EAST).equals(p))
			return DIR.EAST;
		if( me.getAdjPoint(DIR.WEST).equals(p))
			return DIR.WEST;
		Bug.ol("cCD ERROR");
		return DIR.NORTH;
	}
 
	public int taxiDist(Point a, Point b)
	{
		return a.manhattanDist(b);
	}
 
	public DIR moveTo(Point end)
	{ // ghetto best first algo 
		int mX = me.X();
		int mY = me.Y();
		int oX = op.X();
		int oY = op.Y();
		DIR NS_bias = null;
		DIR EW_bias = null;
		DIR Total_bias = null;
		int NSdist = Math.abs(mY - oY);
		int EWdist = Math.abs(mX - oX);
		if(mY > oY)
			NS_bias = DIR.NORTH;
		else
			NS_bias = DIR.SOUTH;
 
		if(mX > oX)
			EW_bias = DIR.WEST;
		else
			EW_bias = DIR.EAST;
 
		if(NSdist >= EWdist) // NS bias is greater, moves N or S
		{
		   if(isValid(me.getAdjPoint(NS_bias)))
				Total_bias = NS_bias;
		}else // EW bias is greater, move E or W
		{
			if(isValid(me.getAdjPoint(EW_bias)))
				Total_bias = EW_bias;
		}
 
		Bug.ol("moveTo: " + end + " is going: " + Total_bias);
		return Total_bias;
	}
 
	public DIR getBestQDir()
	{
		Point[] possPoints = me.adjPointsToMe();
		int max = 0;
		Point bestPoint = new Point(me.getAdjPoint(DIR.NORTH)); // default, die?
		PriorityQueue<Move> allMoves = new PriorityQueue<Move>();
		// calculate the numOpenSpaces*3 + numWalls next to, store that as value
		// in PQ allMoves<Move>
		for(Point p : possPoints)
		{
			Move m = new Move(p,0);
			//int t=0;
			if(!isValid(p))
				m.setValue(-1000); //t = -1000;
			else
				m.setValue(openPtsFrom(p)*3); //t = openPtsFrom(p);
			int nWalls = numWallsNextTo(p);
			m.setValue(m.getValue()+nWalls);
			allMoves.offer(m);
		}
		Bug.ol("allMoves: " + allMoves);
		//Move[] mArray = allMoves.toArray(new Move[0]);
		//Bug.ol("mArray: " + mArray);
		Move bestMove = allMoves.peek();//mArray[mArray.length-1]; //allMoves.peek();
		max = bestMove.getValue();
		bestPoint = bestMove.getPoint();
		Bug.ol("gBQD Value: " + max + " , point: " + bestPoint);
		if(me.getAdjPoint(DIR.NORTH).equals(bestPoint))
			return DIR.NORTH;
		if(me.getAdjPoint(DIR.SOUTH).equals(bestPoint))
			return DIR.SOUTH;
		if(me.getAdjPoint(DIR.EAST).equals(bestPoint))
			return DIR.EAST;
		if(me.getAdjPoint(DIR.WEST).equals(bestPoint))
			return DIR.WEST;
		Bug.ol("ERROR - gBQD");
		return DIR.NORTH;
	}
 
	public int numWallsNextTo(Point p)
	{
		Point[] adjPts = p.adjPointsToMe();
		int c = 0;
		for(Point m : adjPts)
			if(!isValid(m))
				c++;
		return c;
	}
 
	public String toString()
	{
		StringBuilder build = new StringBuilder( ) ;
		for(int r = 0 ; r< width; r++ )
		{
			build.append( walls[ r ] ) ; 
		}
		return build.toString();
	}
}

Here is MyTronBot, which is what contains main and is used for getting things started, as well as running the fundamental strategy that is to be used

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

public class MyTronBot
{
	boolean IsClosedOff;
 
	public MyTronBot()
	{
		IsClosedOff = false;
	}
 
	public int convertMove(DIR dir)
	{
		Bug.ol("Choice: " + dir);
		switch(dir)
		{
			case NORTH: return 1;
			case SOUTH: return 3;
			case EAST: return 2;
			case WEST: return 4;
			default: return 0;
		}
	}
 
	public DIR makeMove()
	{
		Map map = new Map();
		DIR decision = DIR.SOUTH;
		if(!IsClosedOff)
		{ // we may need to update boolean, don't waste time
			IsClosedOff = map.isClosedOff();
		}
		if(IsClosedOff)
		{
			Bug.ol("Is closedOff, doing max fill strategy");
			decision = map.getBestQDir();
		}else
		{
			Bug.ol("Is !closedOff, doing ccombat ghetto moveTo ");
			if(map.nextToEachOther(map.getMe(), map.getOp()))
			{
				Bug.ol("Bots are next to eachother, doing close combat");
				decision = map.closeCombatDecision();
			}
			else
			{
				Bug.ol("Moving to OP (?)");
				decision = map.moveTo(map.getOp());
				if(decision == null)
				{
					Bug.ol("couln't go towards, picking flood");
				 	decision = map.getBestQDir();
				}
			}
		}
	//	while(false != true)
	//	{
		//	if(map.nextToEnemy(map.getMe(), map.getOp()))
		//	{
		//		Bug.ol("Next To Enemy, do something");
		//		decision = map.closeCombatDecision();
		//	}else if( map.getMe().manhattanDist(map.getOp()) == 2)
		//	{
		//		Bug.ol("manhattanDist == 2, prepare for combat?");
		//	}else
		//	{
				//
		//	}
			// close combat,
			// check taxi dist
			//  if far, do max fill
			//  if near, do cut - off
 
		//}
		return decision;
	}
 
 
	public static void main(String abc[])
	{
		MyTronBot mrBot = new MyTronBot();
		while(true)
		{
			Tron.Initialize();
			Tron.MakeMove(mrBot.convertMove(mrBot.makeMove()));
		}
	}
}

Lastly, Tron is just the Map.java file from the starter pack renamed, which can be found here.