MyTronBot. An entry in the Google AI Challenge 2010.
Copyright (C) 2010 Corey Abshire
___________________________________________________________________

MyTronBot License Notice

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.

This includes the following files:

  aimatron.py
  brandes.py
  gauntlet.py
  MyTronBot.py
  screen.py
  showprof.py
  spectate.py
  test.py
  tronsh.py
  tronutils.py
___________________________________________________________________

AIMA MIT License Notice

Some files in this package are from the code that accompanies
Artificial Intelligence: A Modern Approach, by Peter Norvig and 
Stuart Russell. That code is available on the web under the MIT
License at the following URL:

http://code.google.com/p/aima-python/

This includes the following files:

  games.py
  utils.py
___________________________________________________________________

Dijkstra and Priority Dictionary License Notice

Some of the files in this package are from recipes on the
ActiveState home page, and were written by David Eppstein,
UC Irvine. Those portions of the code are available on the
web at the following URL's.

http://code.activestate.com/recipes/117228/
http://code.activestate.com/recipes/119466/

According to that website, the code is released under
the PSF License.

This includes the following files:

  dijkstra.py
  priodict.py
___________________________________________________________________

Python Starter License Notice

Some of the files in this package are from the python starter
package provided on the competition website. The python starter 
was created by Robert Xiao and is available at the following URL:

http://csclub.uwaterloo.ca/contest/starter_packages.php

The starter package is released under the BSD license.

This includes the following files:

  freebot.py
  tron.py
  northbot.py
  wallbot.py
  randbot.py
___________________________________________________________________

Welcome to my entry into the Google AI Challenge 2010. My entry
is a pretty straightforward implementation of many of the algorithms
that eventually made their way to being published on the forum. 
Thus, it doesn't end up doing all that great in the actual competition.
However, it is a pretty easy to understand implementation, and I
learned a lot from participating. I decided to release it online
in case anyone else wants to study it, learn from it, and make any
suggestions for improving it.

Here are the features of MyTronBot, as key elements of my strategy:

 1. Minimax search with alpha-beta pruning, dynamic time based
    cutoff, and evaluation based on counting each direction from
    the stopping points of each player for the final position.

 2. Detection of points of contention, and dynamic targeting of
    such points within a given range, as an initial strategy.

 3. Shortest path detection between myself and my opponent and
    targeting that path as a far strategy.
	
 4. Depth first search counting as a general fill strategy dynamically
    selected when the board is bisected, as a complement to
    a wall walking strategy.

The code also includes a few other elements for things that I 
experimented with but chose not to include in my final strategy:

 1. Detection of articulation points. A depth first search of
    the tree reveals points which when crossed bisect the floor.

 2. Chunky minimax, wherein instead of moving 1 tile per move
    the successors function moved several.
	
 3. Detection of components, as independent rooms on the board
    that are completely separated by walls.

 4. Detection and enumeration of independent wall segments.

It would be nice to enhance this bot further in the future and
include logic from even more sources.

Hopefully releasing this code encourages others to do the same.
I really enjoyed this competition and look forward to learning
from my fellow participants in the coming weeks.

Thank you Google and the University of Waterloo for putting on
a really great competition this year!

Corey Abshire, 2010
corey.abshire@gmail.com