Graphics Reference
In-Depth Information
Chapter 8
Tic-Tac-Tandroid: A Tic-Tac-Toe Mobile Vision
App that Can “See” and “Think”
Milena Djordjevic-Kisacanin, Vinjai Vale and Branislav Kisacanin
Abstract
We present our work on a mobile Android app that can play the game of
tic-tac-toe by using (1) computer vision to “see” the current situation on the hand-
drawn board and (2) artificial intelligence to “think” of the best next move. The
app displays the next best move on the device display. In order for the app to be
usable on mobile devices, such as smart phones and tablets, the vision part of the app
uses computationally and power-efficient version of gradients of the camera image
to determine the location of the tic-tac-toe board and the cells within it. We then
use averages of gradients in the cells as well as in much smaller boxes around the
centroids to determine whether the contents of the cells are empty, X, or O. After this
our AI algorithm analyzes the situation on the board and determines the next best
move. In both the vision and the AI part of the app we could have used a variety of
approaches to achieve the same goal. In order to get the best possible performance,
we determined through experimentation which particular approaches work best. We
document the limitations of the system, discuss similarities and differences between
embedded and mobile vision, and look at how this and other mobile vision apps will
benefit from mobile vision accelerators and developments in OpenVX.
8.1 Introduction
The game of tic-tac-toe is played on a 3
3 grid. Players can chose to be “X” or “O”
and place their symbols in one of the “cells” of the grid. Tic-tac-toe has been popular
throughout history. An early variant called
Terni Lapalli
was played in Ancient Rome
around the 1st century BC [
1
]. Here is the version of the rules that we used (Fig.
8.1
):
×
X always goes first
The players alternate placing their symbols
The objective of the game is to get three symbols in a row
(vertically, horizontally, or diagonally)
B
M. Djordjevic-Kisacanin
·
V. Va l e
·
B. Kisacanin (
)
Fermat School of Math and Science, Plano, TX, USA
e-mail: b.kisacanin@yahoo.com
