NCL 309: Winning the Game

In the previous lesson, we built a board, moved a selection around it, and placed Crosses into its cells.

We also built something else: a small piece of shared drawing code.

Each time we wanted to use it, we stored a label in #return, jumped to the drawing code, then jumped back through #return when it was finished.

It worked.

NCL has a better way.

Calling a subroutine

Here is the pattern we used in the previous lesson:

MOVE #return $after_draw
JUMP $draw_cell

$after_draw

The drawing code eventually returned with:

JUMP #return

We needed a different return label every time we used it. We also needed a register just to remember where the drawing code should return.

This pattern is common enough that NCL provides two instructions for it:

CALL $draw_cell

and:

RET

CALL jumps to another part of the program, much like JUMP. Unlike JUMP, it also remembers where execution came from.

RET returns to the instruction immediately following the most recent CALL.

Code designed to be called this way is called a subroutine.

Our drawing code can now end with:

$paint
D.COL #D.COL.WHITE #D.TXT.NORMAL
BEQ $paint_selected #selected 1
JUMP $paint_glyph

$paint_selected
D.COL #D.COL.WHITE #D.TXT.INVERT

$paint_glyph
D.CUR #x #y
D.CHR #glyph
RET

Whenever we need to draw a cell:

CALL $draw_cell

When $draw_cell reaches RET, execution continues immediately after that CALL.

We no longer need #return, or labels such as $after_old and $after_new.

There is another important difference: a subroutine can call another subroutine.

Each RET returns from the corresponding CALL. We do not have to manage those return destinations ourselves.

We'll take advantage of that shortly.

Adding the other player

So far, each cell has had two possible values:

Value	Meaning
`0`	Empty
`1`	Cross

Let's add Nought.

We could choose another positive number, but there is a more useful representation:

Value	Meaning
`-1`	Nought
`0`	Empty
`1`	Cross

Add a glyph for Nought:

#cross "\uE573"
#nought "\uE5CB"
#empty "\u3000"

We'll also keep track of whose turn it is:

#player r9

Cross goes first:

MOVE #player 1

Instead of always placing 1 into a cell:

MOVE #cell4 1

place the current player:

MOVE #cell4 #player

After a successful move, we need to change 1 into -1, or -1 back into 1.

We already know enough arithmetic to do that:

MUL #player #player -1

If #player contains 1:

1 × -1 = -1

If it contains -1:

-1 × -1 = 1

One instruction alternates between the two players.

The drawing subroutine also needs to recognize both values. When it has copied the selected cell into #value, it can choose the appropriate glyph:

SMOVE #glyph #empty
BEQ $use_cross #value 1
BEQ $use_nought #value -1
JUMP $paint

$use_cross
SMOVE #glyph #cross
JUMP $paint

$use_nought
SMOVE #glyph #nought

The board now remembers which player owns each occupied cell.

That choice of 1 and -1 is about to become useful for more than drawing.

What makes a winning line?

Consider the top row of the board.

If Cross owns all three cells, their values are:

1 + 1 + 1 = 3

If Nought owns all three:

-1 + -1 + -1 = -3

Because an empty cell is 0, two Crosses and an empty cell produce:

1 + 1 + 0 = 2

Two Noughts and an empty cell produce:

-1 + -1 + 0 = -2

The sum of a line therefore tells us something about its contents.

Sum	Meaning
`3`	Cross owns the complete line
`2`	Two Crosses and one empty cell
`1`	The line favors Cross
`0`	The line is numerically balanced
`-1`	The line favors Nought
`-2`	Two Noughts and one empty cell
`-3`	Nought owns the complete line

The values in the middle can describe several different arrangements. A sum of 1, for example, does not necessarily mean there is only one Cross.

For detecting a winner, however, the two extremes are unambiguous:

 3 = Cross wins
-3 = Nought wins

Our board has eight possible winning lines:

Line	Cells
Top row	0, 1, 2
Middle row	3, 4, 5
Bottom row	6, 7, 8
Left column	0, 3, 6
Middle column	1, 4, 7
Right column	2, 5, 8
Diagonal	0, 4, 8
Diagonal	2, 4, 6

Before we check all eight, let's look at a few operations that will make the job easier.

Operations we can already build

The processor already knows enough to find negative values, absolute values, larger values, and smaller values.

We could build all of these operations ourselves using instructions we've already learned.

In fact, let's do exactly that before introducing anything new.

Negating a number

To negate a number is to change its sign.

We can do that by subtracting it from zero:

SUB #result 0 #value

If #value contains 5:

0 - 5 = -5

If it contains -5:

0 - -5 = 5

NCL provides NEG for this common operation:

NEG #result #value

It produces the same result.

That also gives us a clearer way to alternate players.

Instead of:

MUL #player #player -1

we can write:

NEG #player #player

Both perform the same calculation. NEG simply says more directly what we intend to do.

Finding an absolute value

Sometimes we care about the size of a number, but not whether it is positive or negative.

The absolute value of 5 is 5.

The absolute value of -5 is also 5.

We can build that operation ourselves:

MOVE #result #value
BGE $done #result 0
NEG #result #result

$done

Start by copying the value.

If it is already zero or positive, we are finished.

If it is negative, negate it.

NCL provides ABS for the same operation:

ABS #result #value

Choosing the larger value

Suppose we have two values, #a and #b, and want to keep whichever is larger.

Again, we can build that ourselves:

MOVE #result #a
BGE $done #a #b
MOVE #result #b

$done

Start by assuming #a is the larger value.

If it is greater than or equal to #b, that assumption was correct.

Otherwise, replace it with #b.

NCL provides MAX for this pattern:

MAX #result #a #b

Choosing the smaller value

Finding the smaller value is almost identical:

MOVE #result #a
BLE $done #a #b
MOVE #result #b

$done

NCL provides MIN for that operation:

MIN #result #a #b

None of these instructions gives the processor a fundamentally new ability. We could already produce the same results using arithmetic, comparisons, branches, and moves.

They give useful operations names and let us express them in a single instruction.

Operation	Using what we already know	NCL instruction
Change the sign	Subtract from zero	`NEG`
Ignore the sign	Negate if negative	`ABS`
Choose the larger value	Compare, branch, move	`MAX`
Choose the smaller value	Compare, branch, move	`MIN`

Now we have some convenient tools for examining the board.

Checking the eight lines

We only need one register for the current line:

#line r10

The top row is cells 0, 1, and 2:

$check_top
ADD #line #cell0 #cell1
ADD #line #line #cell2
RET

The other seven follow exactly the same pattern:

$check_middle
ADD #line #cell3 #cell4
ADD #line #line #cell5
RET

$check_bottom
ADD #line #cell6 #cell7
ADD #line #line #cell8
RET

$check_left
ADD #line #cell0 #cell3
ADD #line #line #cell6
RET

$check_center
ADD #line #cell1 #cell4
ADD #line #line #cell7
RET

$check_right
ADD #line #cell2 #cell5
ADD #line #line #cell8
RET

$check_diagonal1
ADD #line #cell0 #cell4
ADD #line #line #cell8
RET

$check_diagonal2
ADD #line #cell2 #cell4
ADD #line #line #cell6
RET

Each subroutine answers one question:

What is the sum of this line?

It leaves that answer in #line.

We could call all eight and test each result individually.

Instead, let's summarize them.

Finding the strongest line

A line can have a value anywhere from -3 through 3.

We care about two things:

the highest line value on the board;
the lowest line value on the board.

Add two more registers:

#highest r11
#lowest r12

Start them at the opposite extremes:

MOVE #highest -3
MOVE #lowest 3

Then check a line:

CALL $check_top
MAX #highest #highest #line
MIN #lowest #lowest #line

Suppose the top row has a value of 2.

MAX compares -3 with 2, so #highest becomes 2.

MIN compares 3 with 2, so #lowest also becomes 2.

Then we reuse #line for the next row:

CALL $check_middle
MAX #highest #highest #line
MIN #lowest #lowest #line

We do not need to remember every line value. Once a line has been compared with #highest and #lowest, its individual value can be discarded.

Put the complete operation into another subroutine:

$check_win
MOVE #highest -3
MOVE #lowest 3

CALL $check_top
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_middle
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_bottom
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_left
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_center
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_right
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_diagonal1
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_diagonal2
MAX #highest #highest #line
MIN #lowest #lowest #line

RET

Notice what is happening here.

Our game calls $check_win.

$check_win calls $check_top.

$check_top returns to $check_win.

Later, $check_win returns to the game.

This is something our hand-made return register from the previous lesson could not safely do. A second call would overwrite the return destination stored by the first.

CALL and RET keep track of those returns for us.

Who won?

After:

CALL $check_win

#highest contains the strongest result for Cross, while #lowest contains the strongest result for Nought.

For example:

#highest = 2
#lowest  = -1

Cross has the stronger line.

Or:

#highest = 1
#lowest  = -3

Nought has won.

The sign tells us which player a line favors. Its absolute value tells us its strength.

Add another working register:

#strength r14

First, remove the sign from Nought's strongest line:

ABS #strength #lowest

Then compare its magnitude with Cross's strongest line:

MAX #strength #highest #strength

Now #strength contains the strength of the strongest line belonging to either player.

If it reaches 3, somebody has won:

BNEQ $no_winner #strength 3

BEQ $cross_wins #highest 3
JUMP $nought_wins

$no_winner

We first ask:

Does either player have a line with strength 3?

Only then do we ask:

Which player has it?

The sign tells us who.

The magnitude tells us how strongly.

When the board is full

There is one more way the game can end.

Neither player may complete a line before all nine cells are occupied.

We could inspect every cell to find out whether the board is full, but we already know something simpler: every successful move fills exactly one previously empty cell.

Add a move counter:

#moves r13

Initialize it with the board:

MOVE #moves 0

Whenever a player successfully places a piece:

INC #moves

Do not increment it when the selected cell is already occupied.

After each successful move, the game can now follow this order:

INC #moves

CALL $check_win

ABS #strength #lowest
MAX #strength #highest #strength

BNEQ $no_winner #strength 3
BEQ $cross_wins #highest 3
JUMP $nought_wins

$no_winner
BEQ $draw #moves 9

NEG #player #player
JUMP $input

Checking for a winner comes before checking for a draw.

That matters on the ninth move: filling the last cell may also complete a winning line.

Only if nobody won do we ask whether all nine moves have been made.

Notice that we are now using NEG for the same operation we originally wrote as:

MUL #player #player -1

The arithmetic has not changed.

The new instruction expresses our intention more directly.

Finishing the game

The three endings can replace the controls at the bottom of the display.

For example:

$cross_wins
D.CUR 9 9
D.TXT "CROSS WINS!    "
D.BLT
JUMP 0

$nought_wins
D.CUR 9 9
D.TXT "NOUGHT WINS!   "
D.BLT
JUMP 0

$draw
D.CUR 9 9
D.TXT "DRAW!          "
D.BLT
JUMP 0

JUMP 0 moves execution outside the program, ending it after the final screen has been drawn.

We now have a complete two-player game.

The board itself still contains nothing more complicated than nine integers:

-1 = Nought
 0 = empty
 1 = Cross

From those values, the program derives everything it needs to know.

It adds cells together to describe a line.

It uses MIN and MAX to summarize all eight lines.

It uses ABS when the magnitude matters more than the sign.

It uses NEG to move cleanly between the two sides of our signed representation.

And it uses CALL and RET to organize those operations into reusable subroutines.

None of those conveniences changed what the computer was capable of doing. We built each numerical operation from instructions we already knew, just as we built our own return mechanism in the previous lesson.

The new instructions let us express those familiar operations more directly.

The complete program

We've changed quite a lot since the previous lesson. Here is the complete two-player game assembled into one program.

The movement and drawing code should still look familiar. The important additions are #player, the move counter, the eight line-checking subroutines, and $check_win.

#selection r0
#column r1
#row r2
#x r3
#y r4

#draw_cell r6
#value r7
#selected r8
#player r9

#line r10
#highest r11
#lowest r12
#moves r13
#strength r14

#key s0
#glyph s1

#empty "\u3000"
#cross "\uE573"
#nought "\uE5CB"

#cell0 r20
#cell1 r21
#cell2 r22
#cell3 r23
#cell4 r24
#cell5 r25
#cell6 r26
#cell7 r27
#cell8 r28


-- Start the game.

MOVE #selection 0
MOVE #player 1
MOVE #moves 0


-- Draw the board.

D.FIL " "

D.CUR 11 2
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty

D.CUR 11 3
D.TXT "\uE500\uE53C\uE500\uE53C\uE500"

D.CUR 11 4
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty

D.CUR 11 5
D.TXT "\uE500\uE53C\uE500\uE53C\uE500"

D.CUR 11 6
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty
D.TXT "\uE502"
D.TXT #empty

D.CUR 9 8
D.TXT "ARROWS MOVE"

D.CUR 9 9
D.TXT "ENTER PLACE"

D.CUR 9 10
D.TXT "ESC TO EXIT"

D.BLT


-- Draw the initial selection.

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell


-- Wait for input.

$input
SYS.AKEY #key

BSEQ $left #key "LEFT"
BSEQ $right #key "RIGHT"
BSEQ $up #key "UP"
BSEQ $down #key "DOWN"
BSEQ $place #key "ENTER"
BSEQ $exit #key "ESC"

JUMP $input


-- Move left.

$left
MOD #column #selection 3
BEQ $input #column 0

MOVE #draw_cell #selection
MOVE #selected 0
CALL $draw_cell

DEC #selection

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell

JUMP $input


-- Move right.

$right
MOD #column #selection 3
BEQ $input #column 2

MOVE #draw_cell #selection
MOVE #selected 0
CALL $draw_cell

INC #selection

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell

JUMP $input


-- Move up.

$up
BLT $input #selection 3

MOVE #draw_cell #selection
MOVE #selected 0
CALL $draw_cell

SUB #selection #selection 3

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell

JUMP $input


-- Move down.

$down
BGE $input #selection 6

MOVE #draw_cell #selection
MOVE #selected 0
CALL $draw_cell

ADD #selection #selection 3

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell

JUMP $input


-- Place the current player's piece.

$place
BEQ $place0 #selection 0
BEQ $place1 #selection 1
BEQ $place2 #selection 2
BEQ $place3 #selection 3
BEQ $place4 #selection 4
BEQ $place5 #selection 5
BEQ $place6 #selection 6
BEQ $place7 #selection 7
JUMP $place8

$place0
BNEQ $input #cell0 0
MOVE #cell0 #player
JUMP $placed

$place1
BNEQ $input #cell1 0
MOVE #cell1 #player
JUMP $placed

$place2
BNEQ $input #cell2 0
MOVE #cell2 #player
JUMP $placed

$place3
BNEQ $input #cell3 0
MOVE #cell3 #player
JUMP $placed

$place4
BNEQ $input #cell4 0
MOVE #cell4 #player
JUMP $placed

$place5
BNEQ $input #cell5 0
MOVE #cell5 #player
JUMP $placed

$place6
BNEQ $input #cell6 0
MOVE #cell6 #player
JUMP $placed

$place7
BNEQ $input #cell7 0
MOVE #cell7 #player
JUMP $placed

$place8
BNEQ $input #cell8 0
MOVE #cell8 #player


-- Redraw the placed piece and check the game.

$placed
INC #moves

MOVE #draw_cell #selection
MOVE #selected 1
CALL $draw_cell

CALL $check_win

ABS #strength #lowest
MAX #strength #highest #strength

BNEQ $no_winner #strength 3
BEQ $cross_wins #highest 3
JUMP $nought_wins

$no_winner
BEQ $draw #moves 9

NEG #player #player
JUMP $input


-- Look up the requested board cell.

$draw_cell
BEQ $draw0 #draw_cell 0
BEQ $draw1 #draw_cell 1
BEQ $draw2 #draw_cell 2
BEQ $draw3 #draw_cell 3
BEQ $draw4 #draw_cell 4
BEQ $draw5 #draw_cell 5
BEQ $draw6 #draw_cell 6
BEQ $draw7 #draw_cell 7
JUMP $draw8

$draw0
MOVE #value #cell0
JUMP $choose_glyph

$draw1
MOVE #value #cell1
JUMP $choose_glyph

$draw2
MOVE #value #cell2
JUMP $choose_glyph

$draw3
MOVE #value #cell3
JUMP $choose_glyph

$draw4
MOVE #value #cell4
JUMP $choose_glyph

$draw5
MOVE #value #cell5
JUMP $choose_glyph

$draw6
MOVE #value #cell6
JUMP $choose_glyph

$draw7
MOVE #value #cell7
JUMP $choose_glyph

$draw8
MOVE #value #cell8


-- Choose the visible glyph.

$choose_glyph
SMOVE #glyph #empty
BEQ $use_cross #value 1
BEQ $use_nought #value -1
JUMP $paint

$use_cross
SMOVE #glyph #cross
JUMP $paint

$use_nought
SMOVE #glyph #nought


-- Find the Display position.

$paint
MOD #column #draw_cell 3
DIV #row #draw_cell 3

MUL #x #column 4
ADD #x #x 11

MUL #y #row 2
ADD #y #y 2


-- Choose whether the square is selected.

D.COL #D.COL.WHITE #D.TXT.NORMAL
BEQ $paint_selected #selected 1
JUMP $paint_glyph

$paint_selected
D.COL #D.COL.WHITE #D.TXT.INVERT

$paint_glyph
D.CUR #x #y
D.CHR #glyph
RET


-- Check each winning line.

$check_top
ADD #line #cell0 #cell1
ADD #line #line #cell2
RET

$check_middle
ADD #line #cell3 #cell4
ADD #line #line #cell5
RET

$check_bottom
ADD #line #cell6 #cell7
ADD #line #line #cell8
RET

$check_left
ADD #line #cell0 #cell3
ADD #line #line #cell6
RET

$check_center
ADD #line #cell1 #cell4
ADD #line #line #cell7
RET

$check_right
ADD #line #cell2 #cell5
ADD #line #line #cell8
RET

$check_diagonal1
ADD #line #cell0 #cell4
ADD #line #line #cell8
RET

$check_diagonal2
ADD #line #cell2 #cell4
ADD #line #line #cell6
RET


-- Find the highest and lowest line values.

$check_win
MOVE #highest -3
MOVE #lowest 3

CALL $check_top
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_middle
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_bottom
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_left
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_center
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_right
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_diagonal1
MAX #highest #highest #line
MIN #lowest #lowest #line

CALL $check_diagonal2
MAX #highest #highest #line
MIN #lowest #lowest #line

RET


-- Finish the game.

$cross_wins
D.CUR 9 9
D.TXT "CROSS WINS!    "
D.BLT
JUMP 0

$nought_wins
D.CUR 9 9
D.TXT "NOUGHT WINS!   "
D.BLT
JUMP 0

$draw
D.CUR 9 9
D.TXT "DRAW!          "
D.BLT
JUMP 0

$exit
JUMP 0

Try it

Run the game with another person and take turns placing pieces.

Try winning with a row, a column, and a diagonal. Then fill the board without either player completing a line and confirm that the game ends in a draw.

While playing, pick a moment and stop before making the next move. Look at the nine cell values and calculate the eight line sums yourself.

Which value should be in #highest?

Which should be in #lowest?

What should #strength contain?

In NCL 310: The Computer's Turn, we'll give Nought to the computer.

We've taught the program how to understand the board after a move. Next, we'll see what happens when it starts asking about moves that haven't happened yet.