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.