Course:CPSC312-2018-Crusher

From UBC Wiki

Title

Authors:

Harlan Colclough, Shreyas Naik, Tarang Mahapatra

What is the problem?

We are going to create a turn-based game called Crusher, which can be thought of as six sided checkers, where the objective is to either capture all of an opponent's pieces or force the opponent into a position where they cannot make any moves. We would be creating an AI that uses a basic heuristics, parallel processing, and a simple version of learning to challenge the player. We will document all our code and create a test suite for the entire backend.

What is the something extra?

Our something extra is to create a smart AI that can be configured for multiple difficulties. We will use 3 techniques to improve our AI:

  • Heuristics: even for a small board with side length 2 or 3, there are a huge number of possible board states, as each space can have 3 different states: empty, taken by a white piece, and taken by a black piece. Because of this, it is unrealistic to calculate every possibility as the program will run out of memory before it reaches the end. To get around this, we will create a simple function for calculating a board's 'vale' with respect to a specific player. This way, we can set a specific depth to go to (unless an end condition is met), and then we can just calculate the value of the board at that point.
  • Parallel processing: as we saw in the heuristics description, there are many different paths that need to be calculated in order for the AI to make an informed decision on its best play. This is clearly a place where parallel processing could make a difference in the 'thinking' time.
  • The brain: using a simple function in the heuristics section was useful as it sped up the decision making process and helped the AI to generally make smart plays. Unfortunately and as was expected, as long as the depth and the side length of the board are kept constant, any game between two AI players has exactly the same series of plays and the exact same result. This is boring as a player could find a way to beat the AI and use it to win every single time. To combat this, we implemented a simple version of learning for the AI.

What did we learn from doing this?

Here are our learnings about the 3 parts of our something extra:

  • Heuristics: we play tested the AI with some different functions such as where v is the value of the board, s is +1 if the AI has more pieces than its opponent and -1 otherwise, n is the absolute value of the difference between the number of pieces of both players, m is the number of the AI's pieces, and t is the number of its opponent's pieces. I found that using these more complex functions led to the AI making mistakes that, to us, would be obvious. For example, with only one piece of each colour left, the white side would move into stomping range of the black piece only to get stomped on by that piece on its next turn. It seemed like it couldn't see that that move was certainly going to lead to its death. In the end, we found that the most successful function was the simplest: with the same description for each variable. Using this, the AI would not make as many simple mistakes and would attempt to find a way to trap the opponent and force them to move into stomping position.
  • Parallel processing: we used parallel processing to split allow each of the possible plays to have its 'value' calculated simultaneously. After testing the use of parallel processing in multiple different parts of the code, we found that there were only a few places where it helped. In some places, it didn't make a difference, but, in others, the overhead of creating the threads actually slowed it down. Some simple testing showed that using parallel processing sped up the AI's decision making progress by a factor of 4. For example, when set to have a depth of 3 on a board with side length 3, using parallel processing brought the decision making time for the first move from just over 8 seconds to just over 2 seconds.
  • The brain: there is a Brain type which is a map from hash values to Ints. The hash is taken by the display string (used to print a board to the cmd line) of a board. During every game, the list of boards that have existed is kept track of in a list. After one side wins, but before beginning the next game, all visited boards are converted to hashes and added to the map if they are not already there. If white wins, the value that each hash maps to is incremented by one. If black ones, the values are decremented by one. This means that if a board has existed before, the AI can check whether it typically leads to white or black winning. This is then taken into account in the value-determining function. After implementing this, we see that almost every game is different, and after a large number of games, an AI has approximately a 50% chance of beating another AI. It also becomes very difficult to beat as a player, as the late game AI becomes very conservative and can lead the player into not having any moves remaining. It also does takes fewer risks and falls for fewer traps.

Functional programming worked excellently for this project, especially because the AI needed to calculate many values based on 'theoreticals'. The 'no side affects' quality of Haskell made these calculations much safer. Also, doing these calculations recursively (calculating a value for a board requires calculating a value for every board that can happen after that board, etc.) was very easy, and dealing with base cases is simple.

Links to code

https://github.com/hcolclou/Crusher/