January 4 2017

## Functional JavaScript: Tic-Tac-Toe Game

Functional programming often leads to some pretty elegant solutions. One of the reasons for this is the paradigms so-called ‘composability’ when compared with, say, C-style imperative programming. Composition in computer science is a way of taking smaller, simpler objects or data types and aggregating them into a more complex whole. Functional decomposition, a related concept, is the ability to take a problem, split it up into a series of small functions which solve small problems, and then combine them into a single function by means of a top-level function. It is the top-level function that is said to have ‘composed’ the function.

To demonstrate this, we will adapt Brian Harvey and Matthew Wrights implementation of a tic-tac-toe game with Artificial Intelligence from their book *Simply Scheme*, rewriting the program in JavaScript. For those so inclined, I enjoyed the book and recommend reading it for an introduction to both the Scheme language and computer science in general.

Now JavaScript may not be Scheme, but it is expressive enough for the task we have planned for it. This is due in no small part to its compatibility with Higher-Order functions such as map, reduce and filter, and of course its ability to freely pass functions around as arguments for other functions to consume.

I will not be covering in any depth what methods such as map, reduce, and filter actually do in this post. I feel that there’s a large enough pool of other resources written in JavaScript from which to draw on for that kind of thing. Instead, this post aims to take the ideas that the functional paradigm gives us and apply them to a problem that’s a bit larger in scope. For this goal, a simple tic-tac-toe game with computer-controlled AI serves well enough to realize that the ways in which functional programming goes about solving problems is quite different from an approach more informed by something like object-oriented programming.

### Tic-Tac-Toe Board

We need to represent the information of a tic-tac-toe game board in a way that makes sense to a computer. To do so, we can number a board to look like this:

1 | 2 | 3 |

4 | 5 | 6 |

7 | 8 | 9 |

which easily translates into an array data type. Additionally, a game in session can have a board position that looks like this:

x | ||

x | ||

o |

which can be be represented in an array like so:

`var position = ["x","_","_","_","x","_","_","_","o"]`

In this way, we can say that we have an “x” in positions 1 and 5, with an “o” in position 9. Nine elements in the `position`

array, 9 numbers on a tic-tac-toe board. Got it?

### Playing the Game

We will be defining a top-level function, `ttt`

that will return the computer’s next move when given a current board position.

A sample game might look like this:

```
ttt(["_","_","_","_","x","_","_","_","_"], "o")
// 1
ttt(["o","_","_","x","x","_","_","_","_"], "o")
// 6
ttt(["o","_","x","x","x","o","_","_","_"], "o")
// 7
ttt(["o","_","x","x","x","o","o","x","_"], "o")
// 2
```

This represents the following series of events:

- Human goes first in square 5
- Computer moves in square 1
- Human moves in square 4
- Computer blocks in square 6
- Human moves in square 3
- Computer blocks in square 7
- Human moves to square 8
- Computer blocks again at square 2

It’s important to note at the outset that we won’t be discussing how to implement a visual component for our game — we’ll instead be focusing on the programs logic.

### Function Composition

The ‘composability’ of functional programming really shows when writing programs from a top-down, architectural perspective. One could say that when a person plays a game of tic-tac-toe, they follow an algorithm for determining their next actions:

- Can I win on the next move?
- If not, can my opponent?
- If so, I should block his next move
- Can I set myself up to win?
- And so on …

This algorithm can be expressed in the following pseudo-code, written from the point of view of the AI:

```
function ttt(position, me) {
if (iCanWin)
chooseWinningMove
else if (opponentCanWin)
blockOpponent
else if (iCanWinNextMove)
prepareWin
else
whatever
}
```

The top-level function `ttt`

composes the smaller functions found in the if / else statements into a single complex function. The composability of functional programming lets us immediately begin thinking about the data structures our program will have in a “Big Picture” sort of way, and gives us insight into what helper functions we will need to define to complete the program.

Thus, we can already see that we will need at least 4 more functions for `iCanWin`

, `opponentCanWin`

, `iCanWinNextMove`

and `whatever`

. We also already know that they will all need to consume data the same data-types that are provided to `ttt`

, the top-level function.

In its current form the `ttt`

function receives a `position`

and a player identification in the form of an x or an o for the parameter `me`

. Then the computer decides if it can win it will `chooseWinningMove`

. If not, it will `blockOpponent`

if needed. And so on.

Each one of the functions in the if / else logic will receive the same kind of functional decomposition as the top-level `ttt`

function. And those smaller level helper functions will have the same data, `position`

and to work with.

When people talk about functional programming, they throw around such terms as “stateless”, “immutable data” or “functional purity”. All these terms essentially describe this process of taking data in, manipulating the form that data is represented, and returning it. When compared to imperative programming, which dictates to the computer step by step how to directly change the program’s state, functional programming is much more like plumbing, piecing together portions of functions to route the incoming data into the desired representations.

Next, we will take a look at how we want to represent our data.

### Triples

A person looking at a tic-tac-toe board studies the rows, columns and diagonals, and begins asking themselves some questions. The question of “can I win on this move?” is essentially the same as the question “are there three squares in a line such that two of them are mine and the last one is blank?”.

There are 8 possible ways to win in a tic-tac-toe game — three vertical wins, three horizontal wins, and two diagonal wins. A “triple” is any of one these 8 possible win conditions, and we can use a two-dimensional array to represent them by adapting our representation of a numbered board:

1 | 2 | 3 |

4 | 5 | 6 |

7 | 8 | 9 |

such that it looks like this:

`var combinations = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]`

.

You can see that `[1,2,3]`

represents a top horizontal win, and that `[1,5,9]`

represents a diagonal win.

The next step would be to take the two-dimensional array of just numbered triples and swap in “x’s” and “o’s” for the numbers when given an actual position as a one-dimensional array.

For example, something like this:

`["_","x","o","_","x","_","o","_","_"]`

becomes this after the swapping-in:

`[[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]]`

You may need to look this over in order to convince yourself that all the information needed about the board’s current position is there in that two-dimensional array.

Consider 3 different triples:

`[1,"x","o"]`

`["x","x",8]`

`[4,"x",6]`

If you are x’s, then triple #1 is useless to you because an o already exists inside of it. Triple #3 is interesting to you, because by taking the 4 or 6, you can set yourself up to win on your next turn. But it’s triple #2 that’s most interesting of all because it represents a winning triple by means of moving to square number 8.

The whole program really functions on just 3 different representations of the same information. You have the human friendly, computer unfriendly, visual-spatial board:

x | ||

x | ||

o |

You have the human-readable but also machine-readable single-dimensional array: `["x","_","_","_","x","_","_","_","o"] `

.

And third, you have a format that is human unfriendly, but very computer compatible in that the computer can *reason* about this representation. The two-dimensional array: `[[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]]`

.

All we’re doing with the triples is just manipulating data from one form into another.

Here’s the part of our program that performs this conversion:

```
function findTriples(position) {
return combinations.map(function(combination) {
return combination.map(function(square) {
if (position[square-1] === "_")
return square
else
return position[square-1]
})
})
}
```

Remember that we defined `combinations`

above?

`var combinations = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]`

Okay, good. The function `findTriples`

takes `combinations`

, a two-dimensional array and, using `map`

, passes individual `combination`

single-dimensional arrays onto yet another `map`

function which questions each `square`

found in the single-dimensional array of `combination`

. If the corresponding number found in `position`

is just an `_`

, we return `square`

to retain its number. Otherwise, it must be an x or an o, and in that case we swap that value in.

Right? Here’s a code example if that bunch of words seems useless to you:

```
var testPosition = ["_","x","o","_","x","_","o","_","_"]
findTriples(testPostition); //[[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]]
```

We’ve done this because the data returned from `findTriples`

is in a format more inherently useful to the AI for our program than a single-dimensional array in itself. We pass the board position and an x or and o to `ttt`

, which will pass the same parameters to `tttChoose`

, which outputs triples and an x or an o. Moreover, the rest of our program will consume this data, making the program so far look more like this:

```
function ttt(position, me) {
return tttChoose(findTriples(position), me)
}
function tttChoose(triples, me) {
if (iCanWin(triples, me))
return chooseWinningMove(triples, me)
else if (opponentCanWin(triples, me))
return blockOpponentWin(triples, me)
else ... // And so on
}
```

### Can the Computer Win?

With `findTriples`

out of the way, we can finally begin working on the `iCanWin`

procedure. Based on the current way we have our program structured, `iCanWin`

should return `true`

if the computer can win on the current move so that `chooseWinningMove`

can be executed.

We already know that a winning move is one which a player owns two squares of a triple whose third square is empty. For example, the triples `["x",6,"x"]`

and `["o","o",7]`

fit these criterion.

To begin with, a function that counts how many instances of a given element occur in array would be useful here. We’ll just roll our own primitive, `appearances`

for this:

```
function appearances(key, array) {
var count = 0
for (var i = 0; i < array.length; i++) {
if (key === array[i])
count++
}
return count
}
appearances("o", ["o","o",7])
// 2
appearances("x", ["o","o",7])
// 0
```

Additionally, we need a way to tell if the computer really "owns" the triple, because `appearances`

would still return 2 for o's even if the triple were `["o","o","x"]`

, for example. So we can implement a `myPair`

function to do just that. To help with that, we'll also throw in an `opponent`

function that just returns an x if given an o and vice-versa:

```
function myPair(triple, me) {
return (appearances(me, triple) === 2) && (appearances(opponent(me), triple) === 0)
}
myPair(["o","o",7], "o")
// true
myPair(["x","o",7], "o")
// false
function opponent(letter) {
return letter === "x" ? "o" : "x"
}
opponent("o")
// x
opponent("x")
// o
```

So, to complete our `iCanWin`

procedure as we have planned, all we would need to do is filter a list of triples with `myPair`

, and if the length of the array after filtering isn't empty, we return `true`

. We'll break this up into two separate procedures -- `iCanWin`

, which returns a boolean value, and a new helper function `winningTriples`

that returns an array of all so-called winning triples:

```
function iCanWin(triples, me) {
return winningTriples(triples, me).length > 0
}
iCanWin([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "x")
// true
iCanWin([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "o")
// false
function winningTriples(triples, me) {
return triples.filter(function(triple) {
return myPair(triple, me)
})
}
winningTriples([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "x")
// [["x","x",8]]
winningTriples([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "o")
// []
```

Because we abstracted out the `winningTriples`

procedure, implementing `chooseWinningMove`

, the function which executes if `iCanWin`

returns `true`

, is fairly straight-forward. All that we need to do is extract the number from the first element of the `winningTriples`

array. We can do this because we don't really care which square is chosen to be the winning square if presented multiple options -- we just care that one gets picked at all:

```
function chooseWinningMove(triples, me) {
let solutions = winningTriples(triples, me)
return solutions[0].filter(function(square) {
return typeof square === "number"
})
}
chooseWinningMove([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "x")
// [8]
```

### Can the Opponent Win?

What if the computer can't win on this turn, but the opponent can win on the next turn unless we block a triple immediately? Well, all we would need to do is reverse perspectives, and move to the square that would cause a such a winning move for the opponent. We already implemented the `opponent`

helper function which does just this:

```
function opponentCanWin(triples, me) {
return iCanWin(triples, opponent(me)).length > 0
}
function blockOpponentWin(triples, me) {
return chooseWinningMove(triples, opponent(me))
}
opponentCanWin([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "x")
// false
blockOpponentWin([[1,"x","o"],[4,"x",6],["o",8,9],[1,4,"o"],["x","x",8],["o",6,9],[1,"x",9],["o","x","o"]], "o")
// [8]
```

Pretty slick. Code re-usability is one of the chief advantages that functional programming has over more imperative approaches. Yes, something like object-oriented programming promotes code re-usability as well, but the ease in which we can plug in a function like `opponent`

into existing program structures and logic to compose new functions is a fundamentally different concept of re-usability than what inheritance or polymorphism have to offer.

### Let's talk Strategy

After we've checked if either player can win on the next move or not, we need to look for situations in which some move will give rise to *two* winning triples on the next move:

x | o | |

x | ||

o |

Neither x nor o have a winning triple here, but if x were to move to square 7, it would result in two winning triples in combinations `[1,4,7]`

and `[3,5,7]`

:

x | o | |

x | ||

x | o |

What were looking for here are instances in which there are two triples where one square is taken by the computer and the other two are free, and where one of these free squares is shared. In the previous example, this one such square is square 7.

We'll refer to situations like these 'forks' and the square-in-common a 'pivot' for the sake of making the game-logic easier to discuss.

### Strategizing

The next step is to write an `iCanFork`

procedure which will determine whether or not the computer has a pivot square or not.

```
function iCanFork(triples, me) {
return choosePivot(triples, me).length > 0
}
```

This will return `false`

if no pivot squares exist in an empty array, or true if otherwise. Upon returning true, `choosePivot`

will be ran again and returned to resolve the if statement.

The program so far, for clarity:

```
function ttt(position, me) {
return tttChoose(findTriples(position), me)
}
function tttChoose(triples, me) {
if (iCanWin(triples, me))
return chooseWinningMove(triples, me)
else if (opponentCanWin(triples, me))
return blockOpponentWin(triples, me)
else if (iCanFork(triples, me))
return choosePivot(triples, me)
else ... // and so on
}
```

Our `choosePivot`

procedure will need to filter out all of the triples that have the possibility of holding pivots -- that is, triples with one square taken by the computer with the other two squares in the triple being free. From among those triples that *may* hold pivots, `choosePivot`

will then return the number of a square that appears twice.

```
function choosePivot(triples, me) }
let singles = filterSingles(triples, me)
return organizeSingles(singles, me)
}
function filterSingles(triples, me) {
return triples.filter(function(triple) {
return mySingle(x, me)
})
}
function mySingle(triple, me) {
return (appearances(me, triple) === 1) && (appearances(opponent(me), triple) === 0)
}
```

If we begin `choosePivot`

with an array of triples:

`[["x","o",3],[4,"x",6],[7,8,"o"],["x",4,7],["o","x",8],[3,6,"o"],["x","x","o"],[3,"x",7]]`

And `filterSingles`

the ones that may hold pivots for a computer playing as x with the help of `mySingle`

:

`[[4,"x",6],["x",4,7],[3,"x",7]]`

We will be left with the numbers 4, and 7. In our case, the computer would return 4 because the function we're going to write will just pick the first valid pivot from a sorted array via `organizeSingles`

. Which pivot is chosen is unimportant strategically because if the opponent has let themselves get into a position where the computer has two avenues of winning the game, they have already lost:

```
function organizeSingles(singles, me) {
let flattened = singles.reduce(function(a, b) {
return a.concat(b)
}, [])
let sortedList = flattened.sort()
return selectPivot(sortedList)
}
function selectPivot(sortedList) {
let temp = []
for (var i = 0; i < sortedList.length; i++) {
if (sortedList[i] === sortedList[i+1] && typeof sortedList[i] !== 'string')
temp.push(sortedList[i+1])
}
return temp
}
```

`organizeSingles`

uses the `flattened`

function through reduce in order to turn the two-dimensional `singles`

array it receives into a single-dimensional array:

`[4,"x",6,"x",4,7,3,"x",7]`

Then, it uses the array method `sort()`

with no arguments, defaulting it to unicode value sorting, meaning that numbers come before letters:

`[3,4,4,6,7,7,"x","x","x"]`

Finally, `selectPivot`

returns only the valid pivot numbers -- that is, elements that occur more than once in the `sortedList`

array. Note that the `selectPivot`

function has a very imperative structure. While it's true that to keep in line with the focus on functional programming we've set out for ourselves, JavaScript is by nature an imperative language with functional capabilities. The use of a for loop here to iteratively suss out the pivot squares should be seen as a strength to our approach, and to the JavaScript language itself, rather than a weakness. Moreover, because the `selectPivot`

procedure doesn't pass any arguments to other functions, that fact that it relies on state isn't a hindrance. If in the future we should find that `selectPivot`

needs to be refactored into a more functional approach, we can easily do so because it won't require changing any of our programs structure outside of the function itself.

```
choosePivot([["x","o",3],[4,"x",6],[7,8,"o"],["x",4,7],["o","x",8],[3,6,"o"],["x","x","o"],[3,"x",7]], "x")
// 4
```

### Offensive Strategy

The final version of `tttChoose`

will look like this:

```
function tttChoose(triples, me) {
if (iCanWin(triples, me))
return chooseWinningMove(triples, me)
else if (opponentCanWin(triples, me))
return blockOpponentWin(triples, me)
else if (iCanFork(triples, me))
return choosePivot(triples, me)
else if (iCanAdvance(triples, me))
return chooseAdvance(triples, me)
else
return bestFreeSquare(triples)
}
```

Yes, we only have two functions left to define -- `iCanAdvance`

and `bestFreeSquare`

. It may have occurred to you that we could write some function `blockOpponentFork`

next. This would certainly make sense, except that blocking an opponents fork can only negate one of the two possible winning conditions of theirs. Instead, we should take an offensive strategy, forcing the opponent to block on their next turn instead of simply advancing or forking. In going offensive, we need to be careful not to accidentally set up the opponent for a fork.

Consider this board position, if we are o's:

x | o | |

x | ||

o |

Opponent x has pivots in squares 4 and 7, and o can't take them both. However, if o were to move to squares 3, 6, 7 or 8, x would need to use up their turn in order to block the win. But, o shouldn't actually ever move to square 8:

x | o | |

x | ||

o | o |

because it would set up x for a fork while simultaneously blocking o:

x | o | |

x | ||

x | o | o |

The algorithm for `iCanAdvance`

will basically find all of the relevant triples, take the first one of the returned array if one exists, and then choose between the two empty squares found in the triple:

```
function iCanAdvance(triples, me) {
return chooseAdvance(triples, me)
}
function chooseAdvance(triples, me) {
let myTriples = filterSingles(triples, me)
return bestMove(myTriples, triples, me)
}
function bestMove(myTriples, triples, me) {
if (myTriples.length === 0)
return false
else
return bestSquare(myTriples[0], triples, me)
}
```

With `iCanAdvance`

, what we're really doing is let `chooseAdvance`

do the heavy lifting. We're doing this because `bestMove`

will return either false if there are no squares to advance with or it will return the number of the square to advance to, which is a truthy value. For the sake of more intuitive code, I think that breaking up the code to read *if iCanAdvance returns true, then execute chooseAdvance*, as opposed to `iCanAdvance`

executing itself twice. Consider it a stylistic abstraction choice.

Moving on, lets look at `bestMove`

. It takes 3 arguments. `myTriples`

uses our previously defined `filterSingles`

function to return a two-dimensional array consisting only of combinations in which we can advance to a second square. We also pass `triples`

and `me`

along because we'll use them in `bestSquare`

in order to look at the board position from the opponents perspective to search for any forks:

```
function bestSquare(myTriple, triples, me) {
let numbersOnly = myTriple.filter(square) {
return typeof x === "number"
})
return bestSquareHelper(choosePivot(triples, opponent(me)), numbersOnly)
}
function bestSquareHelper(opponentPivots, pair) {
if (appearances(pair[0], opponentPivots) > 0)
return pair[0]
else
return pair[1]
}
```

With `numbersOnly`

we keep the two numbers of the selected triple from `bestMove`

. By passing `choosePivot(triples, opponent(me))`

to `bestSquareHelper`

, we also get a list of all the opponents possible pivots from `triples`

. Finally, if one of our two possible moves from `numbersOnly`

is an opponent's pivot square, we'll move there at `pair[0]`

. Otherwise, we pick the other number found in `pair`

.

We might stop to think about where here are situations in which both of the two squares in `pair`

can be pivots for the opponent. Well, those situations only occur on diagonals:

x | ||

o | ||

x |

Because triples with diagonal combination wins like the above are listed last in the `combinations`

array utilized by `findTriples`

, we know that we'll only ever have to deal with this if there are no other choices due to `bestSquare`

taking the first available array available to it.

### Just Pick One

Finally, we've come to the last part of our `ttt`

program. If all else fails, just pick a square. The choice of best square isn't arbitrary, however, because some squares are better than others due to them belonging to more combinations/triples. If the center is available, we pick that. Otherwise a corner, and as a last resort, we pick an edge square:

```
function bestFreeSquare(triples) {
let flattened = triples.reduce(function(a, b) {
return a.concat(b)
}, [])
return firstChoice(flattened, [5,1,3,7,9,2,4,6,8])
}
function firstChoice(possibilities, preferences) {
let squareOptions = preferences.filter(function(square) {
return (appearances(x, possibilities))
})
}
```

### Closing Thoughts

I hope that you got some value out of looking at the uses of functional programming for larger problems. Artificial Intelligence is one area of computer science that has a long tradition of functional programming, and so I think that the tic-tac-toe game we've implemented here serves as a pretty good field test for some of the underlying ideas in the paradigm.

The program can be extended in many ways. A visual component can be added for playing against a computer player in a browser. As it stands, the program has only one difficulty -- to either win or tie. Mistakes can be factored into the algorithm by either removing certain steps to be taken by the computer or having `Math.random()`

decide with probability whether or not the computer moves optimally or not. The program also doesn't allow for two human players to face one another.