As part of this program, I have decided to do the "Entertain the Crew" Project. I have developed an AI based Tic-Tac-Toe Program using HTML/CSS and JavaScript. It has following features:
- Welcome Page (index.html)
- Vs Human (index2.html)
- Vs Bot(AI agent) (index3.html)
The AI module is further divided into two levels: - Novice & Expert
The AI module is implemented using the Minimax algorithm.
Mini-max algorithm is a recursive or backtracking algorithm which is used especially used for decision making in game theory. It provides an optimal move for the player assuming that opponent is also playing optimally. It uses recursion to search through the game-tree.
In this algorithm two players play the game, one is called MAX and other is called MIN. Both the players fight it as the opponent player gets the minimum benefit while they get the maximum benefit. Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value. The minimax algorithm performs a depth-first search algorithm for the exploration of the complete game tree. The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion.
For the two levels of AI:
I have used the entire Minimax algorithm for the expert level so the AI Agent can always choose an optimum move, making it unbeatable.
But for the novice level, I have used Random moves by the AI Agent for maximum number of times and use of Minimax algorithm is restricted to minimum number of moves.
For future prospect of this project I would like to include the following:
- Minimax with Alpha Beta Pruning for increased efficiency
- AI with Reinforcement learning, so AI agent can train by playing with itself and accordingly make an optimum move when playing with the Human Agent
Project Link: https://jsproject.z23.web.core.windows.net/