Overview
For the AI of this project, several different algorithms that could be used for Chess were studied and implemented. They were programmed in a way that allowed them to figure out the optimal move. There were several different types of AI that were used for this project.
Optimal Decision Making w/ Uncertainty AI
This AI focused on the idea of Optimal Decision Making. Through the use of many variables, it figures out the optimal move to take next.
Optimal Decision Making has three main parts:
- Predicting the outcome of a decision
- Assigns a value to that decision
- Finds the decision that maximizes the value
This allowed the AI to makes judgements of each possible move then do the one that gives itself the greatest advantage over the opponent.
This AI is the smartest AI that has been created.
Maximin/ Minimax AI using Alpha-Beta Pruning
This AI implemented the minimax algorithm which made use of Alpha-Beta pruning and Zero-sum pruning. This makes this AI a depth-first sorting algorithm.
A Maximin algorithm looks to minimize the worst possible scenario that could occur from the next player's move. This is done by looking at all possible moves that can be made. Then it looks at all possible moves that the other player could do off that move, this will determine the worst possible combinations of moves. Whichever move returns to highest value, is the move that the AI will make.
This process takes a long time, especially if the AI is looking several moves ahead. Pruning is used to cut off nonviable paths.
- Alpha-Beta Pruning is a search algorithm that stops completely evaluating an action when at least one possibility has been found that proves the action to be worse than a previously examined action.
- Zero-sum Pruning uses the idea that the worst action for player 1 is the best action for player 2. It seeks to maximize player 1's action.
Because of depth-first searching, the main problem is the large amount of time that it takes determine the best possible move. Pruning helps cut this time dramatically.
Supervised Machine Learning using a Neural Network
This AI parses a large database of Chess games through a neural network to create a complex web of weights and nodes. Parsing is done by inputting every move in a game and then seeing what the outcome is. That outcome is then compared to the outcome of the actual game, which leads to backwards propagation. Weights are adjusted by backwards propagation to make the AI ‘learn’ from the game.
THIS HAS NOT BEEN IMPLEMENTED FULLY YET.
Unsupervised Machine Learning using a Neural Network
This AI focuses on ‘learning’ from playing many games of chess over time. Initially, the AI will have a neural network with randomly weighted nodes. As it plays, it will parse moves through the networks to determine which ones it things are good. Once the other player makes a move, it will backward propagate the result of their move through the network to adjust the weights.
THIS HAS NOT BEEN IMPLEMENTED FULLY YET.
Three Stage Chess AI
This AI is based off of the idea that in a game of Chess, there are three phases to it: the opening, the mid-game, and the end game. This AI gets separated into those three phases and does different things depending on the phase it is in.
- Opening: The phase where the AI develops its' pieces, gets their king to safety, and tries to control the center of the board.
- Mid-Game: The phase where the AI attacks with and defends its' pieces.
- End Game: The phase where most pieces are off the board and the king is usually checked.
THIS HAS NOT BEEN IMPLEMENTED FULLY YET.
Variable Modifier AI
This AI is the same as the Optimal Decision Making AI, but it allows the user to change the values of the variables that the AI uses.
THIS HAS NOT BEEN IMPLEMENTED FULLY YET.
Random Choice AI
This AI is used as a control to test other AIs against. It looks at all possible moves that can be made, then chooses one at random. It is meant to show that the other AIs are smarter than random.
About the Chess Base
It is a digitalization of the game Chess. It has all the same rules and movements as the game, from normal Bishop movements to Pawn's en passant move. It also displays all the possible moves that a selected piece can be moved to.
The most difficult part of this piece of my personal project was figuring out if a king was in check or in checkmate. This was hard because when a king was got checked, I needed to figure out if the king could move or figure out if another piece could do something that would stop the king from being taken.
This took me about 3 weeks to create and work out all the bugs.