NCL 410: Refactoring the Computer
At the end of NCL 409, our game was much easier to follow.
Board access, placement, drawing, and movement all gained clearer structures. Several large branch trees disappeared because the program could finally select board registers at runtime.
Most of the remaining bulk is concentrated in the computer player.
Consider two of its routines:
$check_cell0
MOVE #highest -3
MOVE #lowest 3
CALL $check_top
MAX #highest #highest #line
MIN #lowest #lowest #line
CALL $check_left
MAX #highest #highest #line
MIN #lowest #lowest #line
CALL $check_diagonal1
MAX #highest #highest #line
MIN #lowest #lowest #line
RET
and:
$check_cell4
MOVE #highest -3
MOVE #lowest 3
CALL $check_middle
MAX #highest #highest #line
MIN #lowest #lowest #line
CALL $check_center
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
These routines repeat operations, but that's only part of what makes them different.
They also describe relationships.
Cell 0 belongs to the top row, the left column, and the first diagonal.
Cell 4 belongs to the middle row, the center column, and both diagonals.
Right now, the program knows those facts because we wrote different instructions into different routines.
We can give those relationships a representation of their own.
The Winning Lines
There are eight ways to win at Noughts and Crosses:
| Line | First | Second | Third |
|---|---|---|---|
| Top | 0 | 1 | 2 |
| Middle | 3 | 4 | 5 |
| Bottom | 6 | 7 | 8 |
| Left | 0 | 3 | 6 |
| Center | 1 | 4 | 7 |
| Right | 2 | 5 | 8 |
| Diagonal 1 | 0 | 4 | 8 |
| Diagonal 2 | 2 | 4 | 6 |
This table contains the same relationships that were previously spread across our line and cell-checking routines.
If the program can read the table, it doesn't need a different routine for every relationship.
We already have somewhere suitable to store it.
Storing the Lines
In NCL 402, we used the upper half of the value stack as indexed storage.
We'll continue using that convention:
#data_start 64
#lines_base 65
#line_count 8
#line_width 3
The first value will be stored physically at stack[64].
Remember that sp points to the next available stack position and sv means stack[sp - 1]. To select the value at physical position 64, we therefore use an indexed base of 65.
Each winning line contains three cell numbers, so #line_width is 3.
To build the table, we'll temporarily move sp to the beginning of our indexed-data region and use ordinary PUSH operations:
MOVE r31 sp
MOVE sp #data_start
PUSH 0 -- Top.
PUSH 1
PUSH 2
PUSH 3 -- Middle.
PUSH 4
PUSH 5
PUSH 6 -- Bottom.
PUSH 7
PUSH 8
PUSH 0 -- Left.
PUSH 3
PUSH 6
PUSH 1 -- Center.
PUSH 4
PUSH 7
PUSH 2 -- Right.
PUSH 5
PUSH 8
PUSH 0 -- Diagonal 1.
PUSH 4
PUSH 8
PUSH 2 -- Diagonal 2.
PUSH 4
PUSH 6
MOVE sp r31
The data remains in those stack positions after we restore sp.
We've stored 24 values, but the ordinary value stack can continue using its lower half exactly as before.
Naming Scratch Registers
Our convention from NCL 405 gives r0 through r7 to routines as scratch registers.
Scratch registers don't have to remain anonymous.
NCL aliases can be defined wherever they're useful, and multiple aliases can refer to the same register. We can give a routine's scratch registers names that describe what they mean inside that routine:
#check_filter r0
#check_line r1
#check_pointer r2
#check_first r3
#check_second r4
#check_third r5
#check_highest r6
#check_lowest r7
These aliases aren't locally scoped. They remain aliases throughout the program.
The check_ prefix tells us which routine they're intended for and prevents generic names such as #line or #value from colliding with scratch aliases used elsewhere.
We'll use underscores for these programmer-defined prefixes. Dotted names remain visually distinct as peripheral and system namespaces.
Another routine can give the same physical registers completely different names:
#draw_index r0
#draw_selected r1
#draw_register r2
#draw_value r3
#draw_column r4
#draw_row r5
#draw_x r6
#draw_y r7
Both sets describe the same scratch register range.
The aliases describe what those registers mean while a particular routine is using them.
Reading a Line
Suppose #check_line contains the line number we want to inspect.
Each line occupies three values, so its offset is:
MUL #check_pointer #check_line #line_width
Adding the base gives us the sp value that selects the first item:
ADD #check_pointer #check_pointer #lines_base
Now we can borrow sp and read the record:
MOVE r31 sp
MOVE sp #check_pointer
MOVE #check_first sv
INC sp
MOVE #check_second sv
INC sp
MOVE #check_third sv
MOVE sp r31
For example, line 6 contains:
0, 4, 8
After reading it:
#check_first = 0
#check_second = 4
#check_third = 8
The program can now discover the contents of a winning line from data instead of choosing a different subroutine.
One Routine, Two Questions
The old program asks two closely related questions.
After every move:
What are the strongest lines anywhere on the board?
While considering an empty cell:
What are the strongest lines passing through this cell?
The same table can answer both.
We'll give our new $check_lines routine this interface:
-- Consumes: cell index, or -1 for every line.
-- Produces: highest line sum, lowest line sum.
A non-negative argument filters the table to lines containing that cell.
-1 means every line should be included.
The routine begins:
$check_lines
POP #check_filter
MOVE #check_highest -3
MOVE #check_lowest 3
MOVE #check_line 0
It then reads one line record at a time.
If the filter is negative, the line is always included:
BLT $include_line #check_filter 0
Otherwise, at least one of the three cell numbers must match:
BEQ $include_line #check_filter #check_first
BEQ $include_line #check_filter #check_second
BEQ $include_line #check_filter #check_third
JUMP $skip_line
The same routine can therefore inspect all eight lines or only the lines relevant to one particular cell.
From Cell Numbers to Values
Our table contains cell numbers:
0, 4, 8
The board itself still lives in registers r20 through r28.
We already know how to bridge those representations.
For the first cell:
ADD #check_pointer #check_first #board_base
#check_pointer is an alias for r2, so the board value is available through:
rr2
We can use r3 to accumulate the line sum.
Earlier in the routine, that register was named:
#check_first r3
We can give it another alias for its new role:
#check_sum r3
Then:
ADD #check_pointer #check_first #board_base
MOVE #check_sum rr2
ADD #check_pointer #check_second #board_base
ADD #check_sum #check_sum rr2
ADD #check_pointer #check_third #board_base
ADD #check_sum #check_sum rr2
Once we've used #check_first, #check_second, and #check_third to find the board registers, their original values are no longer needed.
Reusing r3 for the sum doesn't require moving anything somewhere else. We're simply giving the same scratch register a new job.
Then we update the strongest values seen so far:
MAX #check_highest #check_highest #check_sum
MIN #check_lowest #check_lowest #check_sum
After processing the line, move to the next one:
$skip_line
INC #check_line
BLT $next_line #check_line #line_count
Returning Two Results
The old checking routines wrote their results into agreed registers such as #highest and #lowest.
Our new routine doesn't need to claim those registers from the rest of the program.
It can return both results on the value stack.
We want the caller to be able to write:
POP r0 -- Highest.
POP r1 -- Lowest.
Since the value stack is last-in, first-out, $check_lines pushes them in reverse order:
PUSH #check_lowest
PUSH #check_highest
RET
The complete interface is now explicit.
The caller supplies a filter:
PUSH -1
CALL $check_lines
and receives two results:
POP r0 -- Highest.
POP r1 -- Lowest.
$check_lines can use every scratch register from r0 through r7 internally. None of those registers form part of its interface.
Checking for a Winner
Our old $check_win routine called all eight line routines one after another.
The table has replaced all of them.
To inspect the entire board:
PUSH -1
CALL $check_lines
POP r0 -- Highest.
POP r1 -- Lowest.
The winner test can then continue directly:
ABS r2 r1
MAX r2 r0 r2
BNEQ $no_winner r2 3
BEQ $cross_wins r0 3
JUMP $nought_wins
Eight line routines and $check_win have disappeared.
The winning lines still exist.
They're data now.
Scanning the Board
The computer player has another large repeated section.
In NCL 409, it inspected cell 0, then cell 1, then cell 2, all the way through cell 8.
Each cell needed a different $check_cellN routine because the program had no other representation of which lines belonged to that cell.
$check_lines now accepts the cell number as an argument.
That means the computer can scan the board with a loop.
We'll give the scratch registers names for this part of the program:
#scan_cell r0
#scan_register r1
#scan_highest r1
#scan_lowest r2
#scan_register and #scan_highest both refer to r1, but they're used at different times.
Begin at cell 0:
MOVE #scan_cell 0
Then find its board register:
$scan_cell_loop
ADD #scan_register #scan_cell #board_base
BNEQ $next_cell rr1 0
Occupied cells don't need to be considered.
For an empty cell, ask $check_lines about only the lines passing through it:
PUSH #scan_cell -- Preserve our loop position.
PUSH #scan_cell -- Argument for $check_lines.
CALL $check_lines
POP #scan_highest
POP #scan_lowest
POP #scan_cell -- Restore our loop position.
The two identical PUSH instructions have different purposes.
The first copy belongs to the caller. It preserves the loop position because $check_lines may change r0.
The second copy belongs to the called routine. $check_lines consumes it as its argument.
The returned sums tell the computer what the cell could accomplish.
A lowest sum of -2 means Nought can complete a line there:
BNEQ $check_danger #scan_lowest -2
BNEQ $check_danger #opportunity -1
MOVE #opportunity #scan_cell
A highest sum of 2 means Cross could complete a line there:
$check_danger
BNEQ $next_cell #scan_highest 2
BNEQ $next_cell #danger -1
MOVE #danger #scan_cell
Then continue:
$next_cell
INC #scan_cell
BLT $scan_cell_loop #scan_cell #cell_count
The nine manually written scan sections are gone.
So are $check_cell0 through $check_cell8.
Another Relationship Hiding in Control Flow
After checking for an immediate win or danger, the old computer player used this fallback:
- center;
- corners;
- edges.
Its code looked roughly like this:
BEQ $choose4 #cell4 0
BEQ $choose0 #cell0 0
BEQ $choose2 #cell2 0
BEQ $choose6 #cell6 0
BEQ $choose8 #cell8 0
BEQ $choose1 #cell1 0
BEQ $choose3 #cell3 0
BEQ $choose5 #cell5 0
JUMP $choose7
followed by a collection of labels whose only job was to assign a cell number to #selection.
What information is that control flow actually expressing?
This sequence:
4, 0, 2, 6, 8, 1, 3, 5, 7
That's data too.
Storing the Move Priority
Our winning-line table contains 24 values in physical stack positions 64 through 87.
The next physical position is 88, so its indexed base is 89:
#priority_base 89
#priority_count 9
We can append the fallback order while building our indexed data:
PUSH 4 -- Center.
PUSH 0 -- Corners.
PUSH 2
PUSH 6
PUSH 8
PUSH 1 -- Edges.
PUSH 3
PUSH 5
PUSH 7
Now the fallback code only needs to walk that sequence until it finds an empty cell.
We'll give this work its own scratch aliases:
#fallback_index r0
#fallback_cell r1
#fallback_register r2
Start at the beginning:
MOVE #fallback_index 0
Read one priority entry:
$fallback_loop
MOVE r31 sp
ADD sp #priority_base #fallback_index
MOVE #fallback_cell sv
MOVE sp r31
Find the corresponding board register:
ADD #fallback_register #fallback_cell #board_base
If it's empty, we've found our move:
BEQ $fallback_found rr2 0
Otherwise continue:
INC #fallback_index
BLT $fallback_loop #fallback_index #priority_count
When we find one:
$fallback_found
MOVE #selection #fallback_cell
JUMP $place
The computer still prefers the center, then corners, then edges.
The preference now lives in the sequence itself instead of in a branch tree.
Choosing a Representation
Our program now stores several kinds of information in different ways.
| Information | Representation | Why |
|---|---|---|
| Board | Consecutive registers | Small, frequently accessed directly and by index |
| Winning lines | Indexed stack data | Repeated fixed records |
| Move priority | Indexed stack data | Fixed ordered sequence |
| Persistent game state | Named registers | Small values that live across many operations |
| Subroutine arguments and results | Value stack | Temporary communication between caller and subroutine |
| Intermediate calculations | Scratch registers | Short-lived working values |
There isn't one representation that everything should use.
The board didn't need to move into indexed stack storage just because we learned how to store collections there. Indirect registers already make its existing representation convenient.
The winning lines are different. Their important property is the relationship between groups of three cells.
The move priority is different again. Its important property is order.
Representation depends on how the data is used.
There's another useful question we can now ask when repeated branches begin accumulating:
Is this control flow making decisions, or is it describing fixed data?
If the branches mostly describe a fixed sequence, mapping, or relationship, giving that information a representation of its own can make the actual decisions much simpler.
The Refactored Program
Here is the complete game after this second refactoring pass:
-- Noughts and Crosses
-- Cross is controlled by the keyboard.
-- Nought is controlled by the computer.
-- Persistent game state.
#selection r8
#player r9
#moves r10
#opportunity r11
#danger r12
-- String scratch.
#key s0
#glyph s1
-- Board layout.
#board_base 20
#board_limit 29
#cell_count 9
#cell0 r20
#cell1 r21
#cell2 r22
#cell3 r23
#cell4 r24
#cell5 r25
#cell6 r26
#cell7 r27
#cell8 r28
-- Indexed data.
#data_start 64
#lines_base 65
#line_count 8
#line_width 3
#priority_base 89
#priority_count 9
-- Visible board values.
#empty "\u3000"
#cross "\uE573"
#nought "\uE5CB"
-- Scratch aliases used by $move_selection.
#move_amount r0
-- Scratch aliases used by $try_place.
#place_index r0
#place_value r1
-- Scratch aliases used by $draw_cell.
#draw_index r0
#draw_selected r1
#draw_register r2
#draw_value r3
#draw_column r4
#draw_row r5
#draw_x r6
#draw_y r7
-- Scratch aliases used by $check_lines.
#check_filter r0
#check_line r1
#check_pointer r2
#check_first r3
#check_sum r3
#check_second r4
#check_third r5
#check_highest r6
#check_lowest r7
-- Scratch aliases used while scanning the board.
#scan_cell r0
#scan_register r1
#scan_highest r1
#scan_lowest r2
-- Scratch aliases used for fallback selection.
#fallback_index r0
#fallback_cell r1
#fallback_register r2
-- Starting state.
MOVE #selection 0
MOVE #player 1
MOVE #moves 0
-- Clear the board.
MOVE r0 #board_base
$clear_board
MOVE rr0 0
INC r0
BLT $clear_board r0 #board_limit
-- Build indexed game data.
MOVE r31 sp
MOVE sp #data_start
-- Winning lines.
PUSH 0 -- Top.
PUSH 1
PUSH 2
PUSH 3 -- Middle.
PUSH 4
PUSH 5
PUSH 6 -- Bottom.
PUSH 7
PUSH 8
PUSH 0 -- Left.
PUSH 3
PUSH 6
PUSH 1 -- Center.
PUSH 4
PUSH 7
PUSH 2 -- Right.
PUSH 5
PUSH 8
PUSH 0 -- Diagonal 1.
PUSH 4
PUSH 8
PUSH 2 -- Diagonal 2.
PUSH 4
PUSH 6
-- Preferred moves.
PUSH 4 -- Center.
PUSH 0 -- Corners.
PUSH 2
PUSH 6
PUSH 8
PUSH 1 -- Edges.
PUSH 3
PUSH 5
PUSH 7
MOVE sp r31
-- Draw the static board.
D.PALRST
D.COL #D.COL.WHITE #D.TXT.NORMAL
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.
PUSH #selection
PUSH 1
CALL $draw_cell
-- Wait for Cross to move.
$input
SYS.AKEY #key
BSEQ $move_left #key "LEFT"
BSEQ $move_right #key "RIGHT"
BSEQ $move_up #key "UP"
BSEQ $move_down #key "DOWN"
BSEQ $place #key "ENTER"
BSEQ $exit #key "ESC"
JUMP $input
-- Move left.
$move_left
MOD r0 #selection 3
BEQ $input r0 0
PUSH -1
CALL $move_selection
JUMP $input
-- Move right.
$move_right
MOD r0 #selection 3
BEQ $input r0 2
PUSH 1
CALL $move_selection
JUMP $input
-- Move up.
$move_up
BLT $input #selection 3
PUSH -3
CALL $move_selection
JUMP $input
-- Move down.
$move_down
BGE $input #selection 6
PUSH 3
CALL $move_selection
JUMP $input
-- Try to place the current player's piece.
$place
PUSH #selection
PUSH #player
CALL $try_place
POP r0
BEQ $input r0 0
JUMP $placed
-- A piece was placed.
$placed
INC #moves
PUSH #selection
PUSH 1
CALL $draw_cell
-- Check every winning line.
PUSH -1
CALL $check_lines
POP r0 -- Highest.
POP r1 -- Lowest.
ABS r2 r1
MAX r2 r0 r2
BNEQ $no_winner r2 3
BEQ $cross_wins r0 3
JUMP $nought_wins
$no_winner
BEQ $draw #moves 9
NEG #player #player
BEQ $input #player 1
JUMP $computer_turn
-- Nought's turn.
$computer_turn
PUSH #selection
PUSH 0
CALL $draw_cell
MOVE #opportunity -1
MOVE #danger -1
MOVE #scan_cell 0
-- Inspect each empty cell.
$scan_cell_loop
ADD #scan_register #scan_cell #board_base
BNEQ $next_cell rr1 0
PUSH #scan_cell -- Preserve the loop position.
PUSH #scan_cell -- Argument for $check_lines.
CALL $check_lines
POP #scan_highest
POP #scan_lowest
POP #scan_cell -- Restore the loop position.
BNEQ $check_danger #scan_lowest -2
BNEQ $check_danger #opportunity -1
MOVE #opportunity #scan_cell
$check_danger
BNEQ $next_cell #scan_highest 2
BNEQ $next_cell #danger -1
MOVE #danger #scan_cell
$next_cell
INC #scan_cell
BLT $scan_cell_loop #scan_cell #cell_count
-- Prefer a winning move.
BEQ $no_opportunity #opportunity -1
MOVE #selection #opportunity
JUMP $place
-- Otherwise block Cross.
$no_opportunity
BEQ $no_danger #danger -1
MOVE #selection #danger
JUMP $place
-- Nothing is urgent.
-- Walk through the stored fallback order.
$no_danger
MOVE #fallback_index 0
$fallback_loop
MOVE r31 sp
ADD sp #priority_base #fallback_index
MOVE #fallback_cell sv
MOVE sp r31
ADD #fallback_register #fallback_cell #board_base
BEQ $fallback_found rr2 0
INC #fallback_index
BLT $fallback_loop #fallback_index #priority_count
$fallback_found
MOVE #selection #fallback_cell
JUMP $place
-- Move the current selection.
-- Consumes: movement amount.
$move_selection
POP #move_amount
PUSH #move_amount -- Preserve it across $draw_cell.
PUSH #selection
PUSH 0
CALL $draw_cell
POP #move_amount
ADD #selection #selection #move_amount
PUSH #selection
PUSH 1
CALL $draw_cell
RET
-- Try to place a value in a board cell.
-- Consumes: cell index, player value.
-- Produces: 1 if placed, 0 if occupied.
$try_place
POP #place_value
POP #place_index
ADD #place_index #place_index #board_base
BNEQ $place_failed rr0 0
MOVE rr0 #place_value
PUSH 1
RET
$place_failed
PUSH 0
RET
-- Draw one board cell.
-- Consumes: cell index, selected state.
$draw_cell
POP #draw_selected
POP #draw_index
ADD #draw_register #draw_index #board_base
MOVE #draw_value rr2
SMOVE #glyph #empty
BEQ $use_cross #draw_value 1
BEQ $use_nought #draw_value -1
JUMP $paint_position
$use_cross
SMOVE #glyph #cross
JUMP $paint_position
$use_nought
SMOVE #glyph #nought
$paint_position
MOD #draw_column #draw_index 3
DIV #draw_row #draw_index 3
MUL #draw_x #draw_column 4
ADD #draw_x #draw_x 11
MUL #draw_y #draw_row 2
ADD #draw_y #draw_y 2
BEQ $paint_selected #draw_selected 1
D.COL #D.COL.WHITE #D.TXT.NORMAL
JUMP $paint_glyph
$paint_selected
D.COL #D.COL.WHITE #D.TXT.INVERT
$paint_glyph
D.CUR #draw_x #draw_y
D.CHR #glyph
D.COL #D.COL.WHITE #D.TXT.NORMAL
RET
-- Examine winning lines.
-- Consumes: cell index, or -1 for every line.
-- Produces: highest line sum, lowest line sum.
$check_lines
POP #check_filter
MOVE #check_highest -3
MOVE #check_lowest 3
MOVE #check_line 0
$next_line
MUL #check_pointer #check_line #line_width
ADD #check_pointer #check_pointer #lines_base
MOVE r31 sp
MOVE sp #check_pointer
MOVE #check_first sv
INC sp
MOVE #check_second sv
INC sp
MOVE #check_third sv
MOVE sp r31
BLT $include_line #check_filter 0
BEQ $include_line #check_filter #check_first
BEQ $include_line #check_filter #check_second
BEQ $include_line #check_filter #check_third
JUMP $skip_line
$include_line
ADD #check_pointer #check_first #board_base
MOVE #check_sum rr2
ADD #check_pointer #check_second #board_base
ADD #check_sum #check_sum rr2
ADD #check_pointer #check_third #board_base
ADD #check_sum #check_sum rr2
MAX #check_highest #check_highest #check_sum
MIN #check_lowest #check_lowest #check_sum
$skip_line
INC #check_line
BLT $next_line #check_line #line_count
PUSH #check_lowest
PUSH #check_highest
RET
-- Game endings.
$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
The game still makes the same decisions.
But the computer player no longer contains separate code for every cell, every line, and every fallback choice.
The relationships are stored once, and the program operates on them.
Try It
The computer's fallback preference is currently stored as:
4, 0, 2, 6, 8, 1, 3, 5, 7
That means:
- center;
- corners;
- edges.
Change the stored sequence to:
0, 2, 6, 8, 4, 1, 3, 5, 7
Now the computer prefers corners before the center.
Run the game and watch how its choices change.
You changed the computer's behavior by changing its data.
Its fallback control flow didn't change at all.
The program now has much less repeated structure. Its board, winning lines, move priorities, subroutine interfaces, and temporary state each have representations suited to how they're used.
We've deliberately kept the source spread across many physical lines while making those changes.
In the next lesson, we'll keep this structure and change how it is laid out for execution.