Tic-Tac-Go! A Tic-Tac-Toe solver in Golang
I’ve seen quite a bit of community interest in learning Go but not a lot of material around it. As an exercise for myself, I started writing a Tic-Tac-Toe solver in Golang to get the hang of the language. In the following series, I will share with you things as I figured them out (so get ready to see me pivot as I develop!) and I’ll explain along the way. This is a fun complement to A Tour of Go, which I highly recommend.
Prerequisites
You should have a Golang development environment already set up and working on your machine.
You should have programming experience, but you don’t need to be a wizard.
Understanding of static languages and typing systems is strongly recommended, but will be explained in detail where relevant.
You need to be able to tolerate my writing, since this entire post is, well, my writing.
Setting up the board
In case anyone here happens to be from Mars, let’s go over what Tic-Tac-Toe is real quick. Per Wikipedia
Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.
I hope that wasn’t a shock to anyone.
Design
Given that we are trying to model a 3x3 grid which holds one value per space, it seems like the ideal object to store this would be a matrix. In fact, a matrix is absolutely perfect for this. Just one problem: How do we make one? This is where we will demonstrate one of Go’s most powerful features: a strong typing system that also easily allows for the creation of new types and structs.
Golang and types
The C and C++ vets probably saw this coming from a mile away, but to represent our board, we will need to use structs. However, before we get into that, a little background on Go’s typing system is in order. Compared to most other languages, Go has a fairly strict typing system. Types don’t masquerade as other types, and even things that are compatible by virtue of content and size (int and int32 on a 32-bit system are both 32-bits wide) cannot be used interchangeably.
A note about assignment
You’ll see the := operator quite a bit. Golang uses this when declaration and assignment happen at the same time, and it automatically sets the receiving variable to the type of the initialized data.
Example:
my_string := "foo" // Declaration and assignment are simultaneous. my_string becomes a string
vs
var my_string string // my_string is declared as a string, but contains no data yet
my_string = "foo" // my_string is assigned value "foo", but does not use := operator because it was already declared
Doing it the wrong way
For the purposes of this paper, we’re going to look at the wrong way first.
For our use, we will need to create some structs to represent our data, and yes, each struct represents a unique type. Notice that we create two structs, called “Row” and “Board”. The Row struct has a single field, col, that is a integer array with a length of 3. In other words, each row has an array that can hold 3 ints.
The second struct is the Board, which holds three instances of Row in the field row. As you probably figured out, this leaves us with a 3x3 board (3 rows that have 3 columns each).
(This compiles)
package main
import (
"fmt"
)
type Row struct {
col [3]int
}
type Board struct {
row [3]Row
}
func main() {
my_board := Board{} // This is how we initialize a board
// Note how we reference a single cell on the board
my_board.row[0].col[0] = 1
// Loop over the rows of the board and print their contents
// the _ is /dev/null for variables returned that we don't care about
for i, _ := range my_board.row {
fmt.Println(my_board.row[i])
}
}
Building the board a better way
Let’s face it: that was kinda complicated. Who wants to deal with structs when they don’t have to? You might have also noticed that the board was “upside down” in a way (if you’re used looking at a Cartesian plane like me), so that [0,0] was located at the top left and [2,2] was the bottom right.
Slices
Go is known for being a stickler about types, so you might find it surprising that it gives you what turns out to be a relatively flexable data type called a slice. A slice is an abstraction of an array that has variable length. It can contain most any data type, but only one type per slice (just like an array, imagine that). For example, a slice can contain ints or strings or pointers, but cannot mix them. You won’t see an int and a string in the same array or slice. This isn’t python.
NB: py takes issue with my use of the word “contain”. I agree that it is imprecise, but assert that it’s a good mental model for how arrays and slices operate. This is not the paper to go into explaining how the typing in these data structures actually works.
And yes, you may have guessed that slices can contain other slices. We can do this without structs!
package main
import (
"fmt"
)
func main() {
my_board := [][]string{
[]string{"_", "_", "_"},
[]string{"_", "_", "_"},
[]string{"_", "_", "_"},
}
for i, _ := range my_board { // Loop over the rows of the board and print their contents
fmt.Println(my_board[i])
}
}
Cool, so we have the board, it’s still upside down (for some value of upside-down), but at least we got rid of those crazy structs. This is something that feels manageable. However, there’s still a problem: Slices can be appended to. We don’t want a board that is variable in size, so we need to limit the length of each slice by fixing it as an array instead.
The best way: Multidimensional arrays
Now, in my limited experience, this would be the best way to represent the board in a Golang-y way. We create a board that is limited by both size and type as to what can go into it (more on limiting what the contents can be later).
The last model of the board – and the one we’ll probably stick with – is a multi-dimensional array.
package main
import (
"fmt"
)
func main() {
// This is called a "multi-dimensional array"
my_board := [3][3]string{
[3]string{"_", "_", "_"},
[3]string{"_", "_", "_"},
[3]string{"_", "_", "_"},
}
my_board[0][0] = "X"
for i, _ := range my_board {
fmt.Println(my_board[i])
}
}
You’ll notice that this looks almost identical to the previous data structure, except that we have added a couple of 3s. In Golang, a slice is implied when you define an array without an explicit length (more or less). It would look something like this:
my_slice := []string{} // A string slice
my_array := [3]string{} // A string array of size(3)
By explicitly including a length in the declaration, we have changed from declaring a slice to an array of fixed size. You’ll also notice that the first array declaration uses two [3] blocks instead of one. What’s happening here? Breaking down the declaration syntax for arrays and slices, it looks like this:
[3]string{"foo", "bar", "baz"}
^ ^ ^ ^ ^
| | | | |
/ | \ | /
Length type data
In order to tell our array that each element of its data will be more arrays of n length, we supply that to the type field. This is also called a “two dimensional array”, since the data it represents can be thought of as having two axes, an X and a Y. If you wanted to, you could represent an array of any number of dimensions by extending this pattern.
// Two dimensional array
var my_board [3][3]string
// Three dimensional array
var spaaaaaaace_the_final_frontier [5][10][4]int
Conclusion
Over the course of this article, we quickly looked at Go’s typing system and then dove into three approaches to modeling a tic-tac-toe board using structs, slices, and arrays. In so doing, we demonstrated Go’s strict typing system, how to create structs and custom types, the differences between slices and arrays, and how to create multidimensional arrays. As I continue work on the solver, I’ll continue to share the development and hopefully we’ll all learn a thing or two about Go.
For futher reading, I recommend the following: