Exploring the game¶
In this notebook we’ll explore the game in more depth.
First, we’ll load in the work we did on symmetries in the previous notebook.
)copy notebook2
)fns
)vars is another useful system command. It shows us the names of the variables that )copy brought in for us.
)vars
As we saw earlier, ⎕io is not copied, so we’ll need to set it to zero.
⎕io ← 0
Using symmetries¶
Let’s start by looking at how we can use our work on symmetries to reduce the number of board positions we need to consider when playing.
For any given board position there are up to seven other positions that are equivalent to it.
Why did I say up to?
Some board configurations are symmetric, so some transformations will leave them unchanged.
Here’s an extreme example. Imagine that x has played in the centre of the board.
The board is the same whether you rotate it, reflect it, combine rotations and reflections or leave it unchanged.
⊢ symmetric ← 3 3⍴'....×....'
To examine the symmetries using APL we need to convert the board to its vector representation.
Let’s create a function to do that.
see←{{,'.×○'⍳⍵}⍤2⊣⍵}
It’s a little more complicated than you might expect because it can handle arrays of boards as well as individual boards.
Let’s try it out.
⊢ sym ← see symmetric
You can think of see as an inverse to show.
Let’s check the symmetric transformations on the board.
sym[symmetries]
They are all identical (as they should be).
How can we get rid of the redundant copies?
APL has a primitive function Unique represented as ∪ which does just that.
∪sym[symmetries] ⍝ the unique version
Let’s look at a position with less symmetry.
⊢ asymmetric ← 3 3⍴'.×.×○×...'
+less ← see asymmetric
less[symmetries]
∪less[symmetries]
Now there are four distinct transformations.
Let’s see what they are.
⊂⍤2 show ∪less[symmetries]
show board1
⊂⍤2 show ∪board1[symmetries]
board1 is asymmetric and so it has eight distinct symmetries.
Canonical representations¶
In order to apply Michie’s first simplification we need a way of converting every board position to just one of its symmetries.
We’ll use the idea of a canonical representation. I’ve borrowed that term from Mathematics, but the mathematical details don’t matter to us. You’ll see how we create and use canonical representations in below.
Defining a position’s canonical representation¶
As we’ve seen, every board position is a member of a set of one to eight boards which can be regarded as the same as far as the game is concerned.
The functions encode and decode allow us to switch between the vector representation of the position and a number in the range zero to 19682.
The symmetries of a given position form a set of up to eight vectors, and each vector can be converted to its unique number using decode.
We’ll take the smallest of those numbers and use that as the canonical representation of the position.
Let’s do that for the boards we just considered: sym, less and board1.
We are going to perform the same operation on each, so we can save time by defining a function to do it.
canonical ← { ⌊⌿ decode ⍵[symmetries]}
show encode canonical sym
show encode canonical less
show encode canonical board1
Can we find out the canonical representations of all positions?
Let’s try
all ← canonical encode ⍳3*9
RANK ERROR
canonical[0] canonical←{⌊⌿decode ⍵[symmetries]}
∧
What’s gone wrong?
We’ve used a simple version of indexing in the definition of canonical.
The [] form of indexing corresponds to the notation that is used in a lot of programming languages,
but the format is slightly different for vectors and matrices.
The syntax above works for vectors, but we’re using it with a matrix.
Luckily APL has another form of indexing based on the Index function represented as ⌷.
Index can solve the problem we hit above.
You can see how Index works in the example below.
(⊂0 3 2)⌷7 8 9 10 20 ⍝ the same as 7 8 9 10 20[0 3 2]
Below you’ll see a function called ild, which is short for index last dimension.
Here’s the definition for ild, along with an updated definition of canonical.
ild ← {(⊂⍺)⌷⍤1⊢⍵} ⍝ index last dimension
canonical ← {⌊⌿decode symmetries ild ⍵}
⍴ canonical encode ⍳3*9
How many of these are distinct? We’d expect quite a few repetitions.
⍴∪canonical encode ⍳3*9
That’s a big simplification, but we can further reduce the number of board positions by eliminating some of the positions that can’t crop up in play.
One example: in any valid board position, there will be one fewer ○’s than ×’s after the first player has moved,
and the number of × and ○ characters will be the same after the second player has moved.
If we count the number of ones and twos in the vector representation, for any valid board position the number of ones will be the same or one greater than the number of twos.
There’s a neat way to check that in APL. Below you’ll see the approach working on a small set of position vectors.
⊢ samples ← encode 0 1 9 10 11 18 20 19682
Of these, let’s decide which are valid by counting the 1’s and 2’s by eye:
0 0 0 0 0 0 0 0 0 is valid
0 0 0 0 0 0 0 0 1 is valid
0 0 0 0 0 0 1 0 0 is valid
0 0 0 0 0 0 1 0 1 is invalid because × has played twice but ○ has not played at all
0 0 0 0 0 0 1 0 2 is valid
0 0 0 0 0 0 2 0 0 is invalid, because ○ has played before ×
0 0 0 0 0 0 2 0 2 is invalid because ○ has played twice but × has not played at all
2 2 2 2 2 2 2 2 2 is invalid, because ○ has binged and covered the whole board!
How can we implement these rules in APL?
Let’s start by considering the vector 0 0 0 0 0 0 1 0 2.
v ← 0 0 0 0 0 0 1 0 2
1 2 ∘.= v
∘.= is an equals outer product.
It produces an array which shows where each value in the argument on its left is equal to each value in the argument
on its right.
In this case, one argument is a 2-element vector, and the other is a 9 element vector, so the result is a 2 by 9 matrix of zeros and ones.
+/1 2 ∘.= v
+/ is a plus reduction. It sums the values along the first dimension of n array.
In this case it totals the number of 0s and the number of 1s in the original vector.
We can find the difference between the counts of 1s and 2s by applying -/. That’s a minus reduction.
-/+/1 2 ∘.= v
That tells us that the number of ×s and ○s is the same.
Let’s put that code in a function I’ve named cd (short for count difference) and try another vector.
cd ← {-/+/1 2 ∘.=⍵}
cd 0 0 0 0 0 0 1 0 1
This tells us that there are two more ×s than ○s, which means that the position cannto occur in play.
For the position to be possible the difference must be 0 or 1.
APL has a primitive function membership, represented by ∊, which returns a 0 for each element on its left that is’nt in the vector on its right.
1 2 0 5 1 2 ∊ 0 1
We can check the result of cd using ∊
(cd 0 0 0 0 0 0 1 0 1) ∊ 0 1 ⍝ not a possible position
(cd 0 0 0 0 0 0 1 2 1) ∊ 0 1 ⍝ a possible position
Those brackets are distracting! The code would be easier to read if the arguments to ∊ were reversed.
APL has an operator switch ⍨ to do that.
0 1 ∊⍨ cd 0 0 0 0 0 0 1 2 1
In APL a function returns data as its result. An operator corresponds to what other languages call a higher order function. It takes functions and/or data and returns a function as its result.
Let’s create a new function that will determine if a given position is ok (in other words, possible).
Rather than using cd we will copy its code in-line
ok←{0 1∊⍨-⌿+/1 2∘.=⍵} ⍝ do positions have counts of × and ○ that could occur in play?
ok 0 0 0 0 0 0 1 2 1
ok 0 0 0 0 0 0 1 0 1
What happens if we apply it to a matrix?
ok samples
That’s not right. The problem is that cd works on a vector but not a matrix. One small change will fix that.
We need to make sure that the minus reduction will always be applied to the first dimension of its argument.
Here’s the updated version ofcd
cd ← {-⌿+/1 2 ∘.=⍵}
ok samples
Let’s check that the updated code has picked the possible configurations.
list samples⌿⍨ok samples
Let’s explore the whole set of canonical positions.
⍴uc ← encode ∪ canonical encode ⍳3*9
uc is the matrix of unique canonical positions.
Let’s see which ones look possible.
⍴ucp ← uc⌿⍨ok uc
ucp contains a matrix of the unique coanonical possible positions.
There are only 850, which is manageable.
Here are the first 19. They just fit across the page without wrapping.
list 19↑ucp
It would be interesting to see a few ordered by move mumber.
It’s easy to find the move number for each row in ucp.
It’s just the total of non-zero values in that row.
⍴mn ← +/ucp≠0
APL has a pair of sorting functions called upgrade ⍋and downgrade ⍒.
They return permutation vectors that will sort their arguments into ascending or descending order.
TODO: include some discussion of this article: https://devblogs.microsoft.com/oldnewthing/20170102-00/?p=95095
We can use upgrade on mn to reorder ucp and then display the first few plausible game positions.
We’ll also show which move number they ocurr at.
mnp ← ⍋mn
↑(list 19↑ucp[mnp;]) (19↑mn[mnp])
As you can see there are only three types of first move to which there are a total of twelve repsonses.
Later in the game there will be positions in ucp that cannot happen in a real game. These are positions that could only happen after a player has won the game.
We’ll ignore that for now, as we have greatly reduced the number of positions we need to consider.
What we will do is to save the decoded (integer) values for each plausible position, as these will be useful later. We’ll display the first few values
⊢19↑ucpn ← decode ucp
Let’s save the workspace.
)save notebook3 -force
)fns