Finding the next move

We’ve built up a useful collection of APL tools. We’ve got almost all the code we need to implement MENACE.

In this chapter we will add another function to our toolbox. It will look at the possible moves from a given board position.

First, as usual, we will copy in work from the previous chapter and set the index origin to zero.

)copy notebook4
done
./notebook4.dws saved Wed Dec 30 11:41:51 2020 
⎕io ← 0

)vars
asymmetric board1 boards encoded hereDir i less mi mn mnp mr180 mr270 mr90 r180 r270 r90 samples start sym symmetric symmetries uc ucp ucpn v wpi

We’ll start by developing a function that will display all the possible next moves for a given board position.

We’ll develop and test our work using the positions we stored in samples. You may remember than not all of those positions could be reached in play, but they can still be used to develop and test our next function.

Here are the samples we created earlier.

samples
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 2 2 2 2 2 2 2 2 2 2 
list samples
┌───┬───┬───┬───┬───┬───┬───┬───┐ │...│...│...│...│...│...│...│○○○│ │...│...│...│...│...│...│...│○○○│ │...│..×│×..│×.×│×.○│○..│○.○│○○○│ └───┴───┴───┴───┴───┴───┴───┴───┘

The core idea is that, given a board position, we will display all the possible moves by filling in the blank squares by the appropriate digit.

Here’s an example using one of the samples with the board on the left and the output on the right.

┌───┬───┐
│...│123│
│...│456│
│×.○│×7○│
└───┴───┘

We want to put the digits one to seven into the blank cells.

There are two issues here.

  1. The result should be a character matrix, so we want to put the characters 1 to 7 into the appropriate cells of the matrix.

  2. Indexing a vector into a matrix is a bit ticky. Life wold be easier if we could index into a vector. Then we could reshape the result back to a three by three matrix afterwards.

We’ll experiment and work our way, step by step, towards a function to do that.

⊢pos4 ← samples[4;]
0 0 0 0 0 0 1 0 2 
show pos4
... ... ×.○

We want to identify the empty cells on the board. That’s easy. They are the zero items in the vector pos4.

⊢blanks ← 0=pos4
1 1 1 1 1 1 0 1 0

Where are they in the vector?

There’s an APL primitive to do that :)

It’s Where, represented by ⍸. It converts a boolean vector to a vector of indices, one index for each 1 in the vector.

⍸blanks
0 1 2 3 4 5 7

How many blank cells are there? That’s just a plus reduction written +/

+/blanks
7

Let’s create the characters 1 to 7. We’ll use our old friend ⍳ to generate the numbers, and then another APL primitive function called format ⍕ to turn the numbers into characters.

If we provide ⍕ with the vector 1 0 on its left, it will format the numbers on its right into one-character fields.

⊢1 0⍕1+⍳+/blanks
1234567

Let’s create and display a board matrix based on pos4.

⊢show pos4
... ... ×.○

We’ve created a vector of characters and a vector of of indices.

If we

  1. Turn board4 into a vector,

  2. Index the charcaters into the vector using those indices, and

  3. reshape the result back into a 3 by 3 matrix

we’re done!

bv ← ,show pos4
bv[⍸0=pos4] ← 1 0⍕1+⍳+/0=pos4
3 3⍴bv
123 456 ×7○

We can combine all of that into a function moves

moves ← {blanks ← 0=⍵ ⋄ bv ← ,show ⍵ ⋄ bv[⍸blanks] ← 1 0⍕1+⍳+/blanks ⋄ 3 3⍴bv }
moves pos4
123 456 ×7○

We’ll save the work we did in this chapter.

)save notebook5 -force
notebook5.dws saved Wed Dec 30 11:42:23 2020

In the next chapter we will start to implement a MENACE player.

Possible games Starting To Play