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
Copy to clipboard
done
./notebook4.dws saved Wed Dec 30 11:41:51 2020
⎕io  0
Copy to clipboard
)vars
Copy to clipboard
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
Copy to clipboard
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
Copy to clipboard
┌───┬───┬───┬───┬───┬───┬───┬───┐ │...│...│...│...│...│...│...│○○○│ │...│...│...│...│...│...│...│○○○│ │...│..×│×..│×.×│×.○│○..│○.○│○○○│ └───┴───┴───┴───┴───┴───┴───┴───┘

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○│
└───┴───┘
Copy to clipboard

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;]
Copy to clipboard
0 0 0 0 0 0 1 0 2
show pos4
Copy to clipboard
... ... ×.○

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
Copy to clipboard
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
Copy to clipboard
0 1 2 3 4 5 7

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

+/blanks
Copy to clipboard
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 01+⍳+/blanks
Copy to clipboard
1234567

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

show pos4
Copy to clipboard
... ... ×.○

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 01+⍳+/0=pos4
3 3bv
Copy to clipboard
123 456 ×7○

We can combine all of that into a function moves

moves  {blanks  0=  bv  ,show   bv[blanks]  1 01+⍳+/blanks  3 3bv }
moves pos4
Copy to clipboard
123 456 ×7○

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

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

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