Google AI challenge: tron

I 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:

comments powered by Disqus