Course:CPSC312-2021/Squava
Squava
Authors: Chris Knee, Alex Caceres-Wright, Peiyan Yang
What is the problem?
We are implementing a 2-player abstract strategy game called Squava in Haskell. Users will be able to play against other agents with different search algorithms.
What is the something extra?
We will create different algorithms and data structures in Haskell to play against and compare. Our best algorithm is Minimax with alpha-beta pruning and memorized positions.
We implemented the following AI to play against:
- Minimax
- In Squava, it is often very beneficial to make "squares", where a player will put one piece in each corner of a 4x4 square. This position can lead to many different ways of winning the game, so the AI takes this in mind when using Minimax.
- Minimax with Alpha-beta pruning
- We used Alpha-beta pruning to make Minimax more efficient, by fully observing less moves when we know that they are worse than a previously observed move.
- Minimax with Alpha-beta pruning using memoization
- We used BSTree and Hash functions used in class to improve the performance of Alpha-beta pruning.
What did we learn from doing this?
We found that it was easy to implement the structure of Squava into Haskell because of the general framework we were introduced to in class. Once we understood all the data types and functions, the game was pretty much done. It was the same for the search algorithms as most of the code can be reused and only slightly changed. However, the search power and depth felt a little bit weak and it seemed that using memorization had so much overhead computation that it slowed our algorithm considerably. The fact that everything can be abstracted makes the coding and testing parts easier, but uses a lot more computation power than other languages.