Google AI challenge: tron
28 Feb 2010I participated in the google ai challenge. In the end I was placed 134 out of 708: My profile url.
Since I am working on a Monte Carlo tree search based Computer Go program, I figured I would try to use that as a basis for my bot.
In general it worked quiet ok. Especially in close range combat it is often able to play quite well:
At longer range and when looking for the longest path in endgame situations lack of depth in the tree search shows and quiet many mistakes are made.
I also experimented with using the distance between the players as a heuristic to bias the tree search into deeper branches, this was only mildly successful however. It seemed to be very hard to strike a balance between the heuristic not making a difference and turning my bot into a chaser.
In the final version my bots strategy is as follows:
Test if there is a path reaching the opponent using the a* pathfinding algorithm.
# ###############
## ... #
## .#1 #
## # .### #
# # . #
# # . #
# # ..... # #
# # .#### #
# ### # . #
# #### # . #
# # . # #
# # . # #
# # ###. # #
# # .... # #
# # .# #
# ..# ### #
# . # ### #
# ####. # #
# # .... # #
# .. # #
# . # #
# ###. # ##
# 2#. ##
# ... ##
###############
a* found shortest path between players
In case there is not, enter special endgame mode: the value of nodes in tree search is number of moves divided by flood fill size. I am unhappy with the endgame, this should make less mistakes.
In case opponents can still reach each other, use a biased tree search:
p and P are nodes searched for player 1
e and E are nodes searched for player 2 (enemy)
1 is the principal variation for player 1
1 is the principal variation for player 2
###############
#1PPPPPPP #
#111PPPPP #
#1111PPP e#
#PPP1PP eE#
#PPPPPPP eEE#
#PPPPPPPe eEEE#
#PPPPPPEEEeEEE#
#PPP p EEEEEEE#
#PPp EEEEEEE#
#Pp EEE2EEE#
# EEE2222#
# EEEEEE22#
# EEEEEEE22#
###############
nodes evaluated for each player in tree search at long range
At long range nodes closing in to the opponent are preferred.
Nodes are evaluated using flood fill if they divide opponents into separate areas.
Otherwise random playouts until either player crashes are used.
###############
## PPP e #
#### pPPPPWEEE#
# #PPPP111222#
# #PPP11W22E2#
# #PPP11W2EEE#
# #####1W2EEE#
# ##1122EEE#
# PPPW#EEE #
# PP ##E #
# # #
# #####
# ####
# ####
###############
nodes evaluated for each player in tree search at closer range
Tree search terminates as soon as 0.9 seconds are spent and return the best move found so far.
After reading a little about strategies other people have used, it may also have been a bad heuristic to just approach the other bot. “Voronoi territory” - the number of points that can be reached by each bot first - may have been a better choice. In general a good heuristic is key for Monte Carlo tree search to be able to deeply explore the tree without missing the wrong branches, so this could have helped a lot.
Further links: