Project Description
Tic Tac Toe (XO) is a single player game against PC, using AI algorithms like Best First Search (BFS) and Minimax. It has been developed under C#.NET 3.0

Best First Search

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain. From Wikipedia

 

MiniMax (MinMax)

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty. From Wikipedia

Game Development

The game has been developed as part of my Artificial intelligence course in Petra University, given by Dr. Abulraouf Shtaiwi using Best First Search along with Minimax to calculate the heuristic (Promising value) for each node to decide the tree path.

The Heuristic function is F(X) – F(O), where F(X) is number of possible winning paths for X; and F(O) is number of possible winning paths for O.

The below diagram shows how the winning paths are calculated (counted) for each symbol (X,O):

  • F(O) is 4 in the below case based on the shown paths

function o

  • F(X) is 5 in the below case bed on the shown paths

function x

So in that case the calculated heuristic will be F(X) – F(O) which is 5-4 = 1.

Game Playing

As the game shows its self descriptive for normal users to start playing easily.

XO

In addition to that there is “Display Tracing” check box, that allows you to see how the computer do its calculations using MiniMax algorithm, The below diagram shows how does the code works to select the proper move:

heuristic

The code should pick the move with the minimum loss and maximum gain using the formula, As you see there is multiple moves with the same heuristic value (Move No. : 1, 3, 4 & 5). In that case the code picks the first one.

Javascript (JQuery) Version

The code has been ported to JavaScript as a jquery extension, located under github and jQuery plugin.

Downloads

Download the latest version from here.

To get latest project news you can follow the author on twitter

Last edited Sep 25, 2011 at 9:10 PM by moutasema, version 4