Sandeep Deb's Home Page
Game Theory
  Tic Tac Toe
Framework | Chess | Source Code | Rose Model | Javadocs (download) | Javadocs (online)

No Java 2 SDK, Standard Edition v 1.4 support for APPLET!! Tic-Tac-Toe is a simple extension to the two-player game framework. A tic tac toe board consists of 9 cells arranged in a 3X3 matrix. There are two players categorized by Cross (X) and Circle (O) signs. A move for a player is considered valid if the sign assigned to the player is entered in an empty cell. Winning condition for a player is to complete a line, veritical, horizontal or diagonal with his sign.

This implementation uses an extremely simple evaluation policy, which states that a move is good (score=100) if it results in the completion of a line and bad (score=-100) if it results in the opponent to complete the line. The evaluation policy remains neutral if either of the conditions is not satisfied (score=0).

As you would notice, this evaluation policy is too discrete and has no considerations for a fuzzy move, for example it doesn't assign any goodness to move if it results in the completion of two out of three positions required to complete a line. The fuzziness in the goodness rating proves quite useful for games with a large solution space and helps tremendously in pruning the state space and decreasing the time complexity. Since Tic-Tac-Toe has a computationally small state space complexity, it's easy for the algorithm to evaluate all the possible moves and hence even this simple evaluation policy solves the purpose.







250,246,235