Computer Science Department
Utilizing a Personal Robotics Platform to Demonstrate A* Search with Manhattan Heuristic and Two Player Minimax Algorithm for Autonomous Execution of Tic-Tac-Toe
Robert Arrington
This project will demonstrate Tic-tac-toe played on the personal robotics platform known as Scribbler. A configuration will be created upon which future projects and research could be built further extending exploration of robotics and/or game play.
Via a collaboration between Georgia Tech, Bryn Mawr College, and Microsoft Corporation, the Institute for Personal Robots in Education exists to promote computer programming instruction utilizing the robot platform known as Scribbler with the Fluke2 system on a board controller. Fluke2 utilizes an embedded Linux distribution executing a “server” program managing communication between itself, its attached Scribbler, and a client computer through bluetooth. Typical use of this platform utilizes one computer operating one Scribbler. This project will have multiple Scribblers communicating with each other, absent a computer, performing tasks in harmony. There are three development components to this project: “network” communication, A* search, and minimax. Communication will be established between the devices to facilitate passing a location selected on a game board to the next player in turn. Once notified of a player’s position selection, the active player will calculate its best board position utilizing minimax and then perform A* search to find the best path to the desired grid location. A three by three grid of twelve inch squares will comprise the game board which will be in the center of a five by five grid. The additional two square space surrounding the game play area will be “home” location zones from which paths to the game board will be found.