I’m very certain many of the readers play board games against computer AIs; however, I have not noticed a large level of public awareness about the mechanics of said AIs. It is rather intriguing, since it is actually quite easy to build a simple AI opponent. These AI opponents are not very powerful though; depending on the game, a professional will be able to hold their ground with little effort.
One marked limitation is the ineffectiveness of brute force in some games. Brute force AIs calculate all possible moves starting from a certain position to a certain depth in the game tree (a tree describing the possible turns/changes in the game from a certain point), and then deciding the best course of action. The algorithm I’m going to use is based on that; select the best solution out of a given set. However, in some games the amount of possible different moves from a position is so high that a brute-force AI quickly becomes very inefficient: for instance, in Go the average amount of possible moves per turn is 250 (according to researcher Victor Allis), which quickly leads to a very high amount of possibilities within a very few turns.
Therefore, modern AIs use more effective methods; for example, AlphaGo, the AI that beat the Go master Lee Se-dol used neural networks which enabled it to “learn” from the training games presented to it, and therefore have an effective strategy markedly beyond raw calculation.
On the other hand, the game I’m going to discuss now has the average move per turn count of just 10. And that is..
Apologies, the picture seems to have a 10x10 grid instead of 8x8 you get
In this series of posts, I intend to build a simple, yet fully functional model of the Othello board game. This model shall also have an AI that one can play against, or put to play against itself, if that’s what one likes :D. For those unaware of the rules of the game, a short description is linked in the further reading list.
Unlike with many games, I decided to select a somewhat more unusual language, Haskell for the job. For those unaware, Haskell is a purely functional programming language markedly different from more “common” languages like Python and Java; casually, this difference could be described as Haskell functions being more alike to mathematical functions. Generally, functions in mathematics can cause no side effects to their environment, and always return the same result with the same input. This is not something one should be scared of though, as the basics are fairly easy to get started with.
As of prerequisites, you will need a reasonably modern computer (for GLOSS, an OpenGL based graphics library), an ability to use a command line prompt and a editor that preferably supports syntax highlighting and automatic tabulation (Haskell, like Python, cares about the whitespace in source code). You will also need to be able to install your own software, and with Stack a working Internet connection is a must due to the dynamic updating.
Even though I tried to ensure that the code is reasonably simple, straightforward and well-commented, I have to remark that my experience in Haskell isn’t nearly as consistent as in several other programming languages (plus that a big part of the code was written quickly during late night) - all comments on improvements are highly welcome. You will also likely get most out of this code-along of you know some Haskell already - although I’ve tried my best to make the instructions simple enough to follow even without much knowledge :)
Before we can get started on the programming itself, we need to install our development tools. The overwhelmingly easiest way to do that is to use Haskell Stack.
stack new haskellversi simple- this creates a new empty, simple project. Change into this folder.
stack setupto install the prerequisite GHC compiler and associated tools; after that,
stack exec haskellversi.
Before moving on, I highly recommend you to familiarize yourself with the elementary principles of Haskell, and the GHCi interactive interpreter, stack ghci - both will be very useful for the latter posts.
The full source is available also on GitLab
NEXT PART: Data Structures and Basic Functionality