###
3D Tic Tac Toe for OTHER-1

- this page is completed, mostly

- last update 10/6/2014

- this page is completed, mostly

- last update 10/6/2014

Return to: Home

(Click on images to enlarge. If click does not work, refresh the page and try again.)

The 3D Tic Tac Toe game I implemented on the OTHER-1 was a port from a reverse engineering effort I and a friend embarked on while college students "living" in the school's IBM 1620 (Model 1) computer lab in about 1966-7. I was a physics major with an electronics hobby, while my friend was also a physics major but without the hobby, so my initial interest in the IBM 1620 (wiki link) was with its construction and basic functionality - starting with the architecture and machine language, while my friend's was more practical, starting with FORTRAN and Assembly.

The IBM 1620 in the lab had:

- 20000 6-bit characters of core storage: CF8421 parity Check bit, numeric field Flag bit, 8421bits for alphanumeric, where numeric digit is bcd range 0-9.

- bcd arithmetic (hardware does in-memory table lookups for add, subtract, multiply, divide!) & addressing

- multi-level indirect addressing

- variable-length integer and floating-point mantissa fields (Flag bit marks left-most (lowest address: most significant) digit

- variable-length alphanumeric fields - "record-mark" character follows right-most (highest address) text character

- 80-column card reader and punch

- operator console with capability to manually inspect/enter address & data, halt/continue program execution.

- Selectric typewriter operator interface

The computer lab also had:

- 80-column card sorter

- IBM 402 accounting machine for printing reports from from stacks of cards

- several keypunch machines for manually entering alphanumeric data into (punched columns) & onto (print along top) 80-column cards from a keyboard

The equipment in the lab was open access for interested students and faculty. The lab was newly opened with my arrival in 1964 as a freshmen.

The 3D tic tac toe program showed up one day as an executable card-deck, likely provided by a visiting IBM Customer Engineer. There was neither source code nor author identification. Once loaded via the card reader, play instructions were typed out on the console typewriter, first mover was selected via a console panel toggle switch, and moves were entered or output on the console typewriter as 3 digit (1-4) xyz coordinates of a 4x4x4 playing cube.

The program did not learn from successive games, but had a fixed algorithm with a clever strategy for winning that was difficult to beat or draw. After a few months of playing with it, we decided to build a 4D version of the program. I proceeded to reverse-engineer the machine code to discover the design. The program strategy was to attempt construction of (and defend against) a two-way trap, including forcing the player to move so the trap could be established. A two-way trap can be established in any 4x4 plane through the 3D or 4D cube and is a move which simultaneously establishes 3-in-a-row threats in two intersecting rows.

I've always wondered who wrote the original program that has provided me with hours of programming entertainment. During Christmas season 2013, I did some Google searches and found a suspiciously familiar 3D tic-tac-toe FORTRAN program in an IBM 1620 archive, written by BOB LOUDEN in 1962. From a cursory look, the program has many characteristics in common with the machine code I reverse engineered, such as a table of all 76 4-entry rows, a table of the four major diagonals, computed sums of weighted player and machine moves along each row, several sets of snarky comments with which to needle the player during a game, and in particular, a FORTRAN switched GOTO statement (line TTT 0079: "14 GO TO (71,72,73,74,75,75,74,75,74),J") containing nine strategy processing choices based on a strategy level (J), and activated by a row sum matching the sum at index J in the 9-entry table NTEST (at data lines TTT 0137 - TTT 0145).

During another web search in September, I came across a reference to 3D tic-tac-toe, and Robert K. Louden, author of "Programming the IBM 1130 and 1800" ("mersenneforum.org - hobbies" - poster "rcv"). The book was said to contain a FORTRAN implementation of 3D tic-tac-toe. So I got a used copy of "Programming the IBM 1130", Second Edition, Robert K. Louden and George Ledin, Jr., 1972, from Amazon. Sure enough, it contained the FORTRAN source and a design description including level diagrams similar to those here. The version in the book has a few strategy changes from the IBM 1620 version presented here. More about this later...

Thank you Mr. Louden, wherever you are!

3D Tic Tac Toe Algorithms

OLD SOURCE CODE - NOT

NOTES AND DEFINITIONS:

move-spot = 16*(tier-1) + 4*(row-1) + (column-1),

where tier (x), row (y), and column (z) coordinates are in range 1 through 4.

Note: Base 8 was used in program design and documentation for convenience in implementing on the OTHER-1.

Record Table: A 64-entry table indexed by move-spot, used to keep a record of moves made by Player and Machine. All entries are initialized to 0 at game start. An entry value of 1 indicates a Player move at the move-spot, while a value of 5 indicates a Machine move at the move-spot. This table is used to determine whether a move-spot is occupied by a move, and to calculate the total value of moves in any row.

Major Diagonal List: A list of move-spots along the 4 major cube diagonals, from which is chosen the first few machine moves.

In base 10 these are: 0 21 42 63 3 22 41 60 12 25 38 51 15 26 37 48.

In base 8 these are: 0 25 52 77 3 26 51 74 14 31 46 63 17 32 45 60.

Rows List: A list of the 76 rows (paths) through the 4x4x4 playing cube, each row consisting of 4 move-spots, numbered as illustrated above. For processing convenience, the move spots of each row can be listed in the order of processing (see Notes on Subordinate routines, below). The left-hand 1620 listing portion above is a list of 75 of the rows in base 10 (the 76th row is on the top of the right 1620 listing portion). In the 1620 listing, the center move-spots of a row are listed first, followed by the outside move-spots. The order of the rows in the list is not important.

Intersection Table: A 64-entry table indexed by move-spot. All entries are initialized to value 1 immediately before program Levels employing flow chart "Routine 1", which may change some values to 0. (This initialization is consistent with the original program and the flow chart descriptions below.)

Variables 6MOV and 9MOV: Candidate Machine moves which may have been determined at program Levels 6 and/or 9 are saved in these variables until program Level 10, where one will be used in lieu of the move otherwise determined at Level 10. These variables are initialized to null (no-move) before Level 1 processing.

Sums Table: A 76-entry table indexed by row number of the Rows List.. Each entry is the sum of any Player and Machine values for occupied move-spots in the Record Table for the referencing Row.

(Program) Level: The processing prioritizing mechanism used to implement the machine's "build a forced two-way trap" strategy. Without regard for how many moves have previously occurred in the game, the machine examines the current "board" state for the most immediate concern first at level 1 - "Have I lost?" - to the least pressing concern after level 10 - "No moves I can build on, just pick a powerful move-spot". To do this, the program pairs a row-sum value (using the Level as an index (1 - 10) into a table of row sums) with a processing routine for that level (three routines are reused by seven of the levels, possibly with different row-sums values; also results of some routines may be saved for use at higher Levels). Recall that a Player move has a value of 1, and a machine move has a value of 5, so row sums of 1-4 indicate only Player moves are present in the row, and row-sums of 5, 10, and 15 indicate only Machine moves are present in the row so both cases (along with no moves in a row) are of processing interest, while rows with combinations of Machine and Player moves are ignored, since they cannot directly cause a win. So to summarize the Machine's level objectives as processing moves from Level 1 thru Level Default (11):

The Intersection Table is initialized here, and modified at Level 4...

Row-sums test value: 10

Using Subordinate Routine One

Action/Objective: If there are two intersecting rows with 2 machine moves in each, Machine moves at intersection to make 2-way trap.

This is the first level to make use of the Intersection table initialized prior to level 1. The "subordinate routine 1" inspects all rows containing exactly two machine moves, and records the open locations of such rows in the Intersection table (indicated in gray on diagram example). If the routine 1 detects a common intersection location (dark gray in example) for two such rows, this becomes the response machine move (red M) - establishing a winning two way trap. Otherwise, the routine continues to inspect and mark empty locations in 2-machine-moves-only rows till all are processed, and the next Level is entered.

Row-sums test value: 05

Using Subordinate Routine Two

Action/Objective: (Empty move-spots in 2-machine-moves rows are still marked from Level 4.) If 2 intersects are found in a 05 sums row, move to second intersect spot: will setup 3 in row for player to block, next machine move can make 2-way trap.

In the example, all 2-machine-moves-in-row open locations for the black "M" moves have been previously recorded in the Intersection table from Level 4 (gray locations). While inspecting the second horizontal row (because it has only the single machine move, "subordinate routine 2" detects two intersections (dark gray), the second of which becomes the response machine move (red M), because it forces the player to block the 3-in-a-row win, and allows the machine to complete a two-way trap on its following move. If no such move is found, the next Level is entered. (Note that there could have been "P" moves in all the white open locations not on the second horizontal row, and the response machine move would still force a win.)

Row-sums test value: 00

Using Subordinate Routine Three

Action/Objective: Find move to set up forced two-way trap - save in "6MOV" for Level 10.

Empty move-spots in 2-machine move rows are still marked for intersect from Level 4. If an empty row intersects with empty squares of two rows each containing 2 machine moves, "subordinate routine 3" saves (for Level 10) this machine move to first non-intersection square in row, setting up the situation seen in in Level 5 (if not subsequently blocked by player). In this example the third column is processed from the bottom, center squares first. Subordinate routine 3 inspects all empty rows for for such moves, each saved move overwriting any which were previously found during this inspection.

The Intersection Table is Re-initialized here, and modified at Level 7...

Row-sums test value: 02

Using Subordinate Routine One

Action/Objective: Move to block attempt by Player to make two-way trap. Similar to Level 4, except machine moves to block Player. Also similar to Level 4, subordinate routine 1 records empty locations in 2-player-moves-in-a-rows in the Intersection table for reference in following Levels.

Row-sums test value: 01

Using Subordinate Routine Two

Action/Objective: Move to block Player attempt to set up forced two-way trap. (Empty move-spots in 2-machine move rows are still marked for intersect from Level 7.) Similar to level 5, except move blocks: If 2 intersects are found in 01 sums row, the machine move to the second intersect spot will block a 3-in-row forcing of a two-way trap by player.

Row-sums test value: 00

Using Subordinate Routine Three

Action/Objective: Find move to block Player attempt to set up forced two-way trap - save in 9MOV for Level 10.

(Empty move-spots in 2-machine move rows are still marked for intersect from Level 7.) If an empty row intersects with empty squares of two rows each containing 2 player moves, move to first intersection square in row, setting up the situation seen in in Level 5 (if not blocked by player). In this example the third column is processed from the bottom, center squares first. Again, subordinate routine 3 actually saves only the last such move found, overwriting any previous ones found.

The Intersection Table is Re-initialized here, and modified at Level 10...

Row-sums test value: 05

Using Subordinate Routine One

Action/Objective: Find a move at intersection of 2 rows containing one machine move each, and hold if found. Then along with any previously found move, select the one to make in the order: 6MOV, 9MOV, held move. In this example the horizontal and vertical row intersection table entries are first set for the upper move, then as the bottom horizontal row is scanned/set for intersections of the corner move, the intersection for the upper move is found, and becomes the new move (there being no saved move6 or move9 moves). This example situation may occur frequently in early moves of games on diagonal planes, where both corner and center move-spots are on major diagonals through the cube.

Row-sums test value: --

Action/Objective: No moves were found to build on: Machine moves to a random empty spot on the major diagonals (marked with asterisks). This typically happens (at least) for the first two or three machine moves.

In the 1620 implementation, the game ends if the machine cannot obtain an empty major diagonal location for a move when it reaches this level.

What? Flowcharts!?! Yep - this was the software documentation approach on Air Force contracts in the mid 1970s, and so was mine too at the time. I constructed these flowcharts by revisiting the 1620 machine code and messy derived flowcharts, and my Philco 211 port (written in "TAC" Assembly), and then used these to do the OTHER-1 port. The intent was to preserve the game strategy algorithms of the 1620 code.

Charts of the Main routine:

Each of the Level decision diamonds on Sheet 2 (above right) showing the "continue" return lines is shorthand to indicate a single loop through the entire 76 rows of the game cube for that Level, each row of 4 entries processed by the associated Subordinate routine (One, Two, or Three). The Subordinate routine will either continue to process the next row of 4 entries, or will exit the rows loop processing for the Level with a machine move to output (at entry point 4, Sheet 3, to left).

Charts of three reused Subordinate routines:

Each Subordinate routine must process the 4 move-spot entries of a row in the order: The 2 outside entries first, followed by the 2 inside entries (or consistently, the 2 inside followed by the 2 outside). This is a requirement to ensure the correct move position is selected for action by the Subordinate routine. For example, in the Figure associated with the definition of "Move-spot" in the "NOTES AND DEFINITIONS" section above: the horizontal row move spots "0 1 2 3" would be processed in the order "0 3 1 2", and the diagonal "34 31 26 23" would be processed in the order "34 23 31 26". (The consistent alternative processing order - seen in the 1620 left-side listing above - would be "1 2 3 0" and "31 26 23 34" respectively.)

(Google reports, April 2014: ~105000 results for 'java 3d tic tac toe' :-) )

The effects of some tweaks can be investigated this way. For instance, from the descriptions above, the base algorithm saves only the last Level 6 and/or Level 9 move found for possible later use in a calculated machine move - such possible moves are shown in the System output windows below the game boards (multiple "move6" and "move9" lines). A tweak could save all found moves from a level and pick one at random. Or, the edge the machine has over a human player who can usually only recognize and defend against a potential two-way trap could be estimated by disabling Levels 6 and 9 in the program copy representing the human player.