3D Tic Tac Toe for OTHER-1

This page last updated: 7/6/2017
Return to: Home
(Click on images to enlarge. If click does not work, refresh the page and try again.)
3D Tic Tac Toe on the IBM 1620

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 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.

The 3D program strongly favored machine-side initial moves along the four major diagonals of the cube, with each such move being within the most (7) 4-entry rows. 
My friend then re-coded the game in assembly with modifications for 4D - a fourth move coordinate and favoring the eight major diagonals through the 4D cube (such moves being within the most (15) 4-entry rows).

The 4D game was a bust, since it was trivial for the first mover (player or machine) to force a win. But I had the 3D game design that I later ported to a Philco 211 in 1968 while a grad student at the University of Wyoming, and then again to the OTHER-1.
Possible Original 1620 3D Tic Tac Toe Author

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).
However, the machine code I reverse engineered appears to be a later version, probably a rewrite in Assembly. In the machine code the 64 positions in 76 rows are numbered 0 to 63 (e.g. "00" numeric field at address 01239 in list of 76 rows at left) while they are explicitly numbered 1 to 64 in the FORTRAN code as formatted card data. Also, the machine code lists 10 machine or player sums in in it's "strategy table" (starting at address 01809 at right: 04 15 03 10 05 00 02 01 00 05), while the corresponding FORTRAN switched GOTO lists only nine such sums in the driving table NTEST (04 15 03 10 05 00 02 01 05). And the messages output during play by the programs are similar but do not exactly match.

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
I had intended to include a pseudo assembly code listing  of the 3D Tic Tac Toe game written for the Other-1.But as described on the Other-1 Instruction Set Details page, my assembly coding was just a convenient means for manually writing the machine code (sample page of 3D Tic Tac Toe to left) - code for a one-of-a-kind decommissioned machine. Similarly, the IBM 1620 machine code and Philco 211 assembly code listings I have are for obsolete and generally unavailable machines. So, the game algorithm in flowchart form is presented below.
Move-spot: A unique number 00-63 (00 - 77 base 8) assigned to each of the 64 possible positions on the 3D tic tac toe 4x4x4 playing cube. (See figure on right for assignments in base 8.) These assignments are used in the program implementation to index into the move position related Record Table & Intersection Table.

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 following figures show representative (but not the only) move configurations in any cube plane (of 18 interdependent planes), and how they would be processed at each program level to produce the next machine move. By "representative" I mean there are many ways, for example, to get 4 in a row in Level 1, or arrange two-way-traps in Level 4, but all are detected by the algorithms. Note that processing at higher levels 11, 10, and 6 work to produce the winning situation at level 5, and that winning moves/strategies at levels 2, 4, 5, 6 have  corresponding defensive counter-moves at levels 3, 7, 8, 9.
The Intersection Table is initialized here, and modified at Level 4...
Level: 1
Row-sums test value: 04
Action/Objective: If any row has 4 Player moves, the Machine loses - output "I lose"
Level: 2
Row-sums test value: 15
Action/Objective: If any row has only 3 Machine moves, the Machine wins - output winning move and "I win"
Level: 3
Row-sums test value: 03
Action/Objective: Player has 3 in a row: Machine moves to block
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.
Level: 5
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.)
Level: 6
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...
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.
Level: 8
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.
Level: 9
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...
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.
Level: Default (11)
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.
An aside: These charts do not address the specifics of game display on the OTHER-1, which was done to a "TV Typewriter" - a black/white video text  output interface, once available in kit form from South West Technical Products, which accepted ASCII character codes via interface through the Other-1 I/O Buss and output them to a connected TV set for display as 16 lines of 32 characters/line, with cursor control and basic character edit capability. The game board was first drawn with symbols !, +, and -, and machine "M" and player "P" moves added as play progressed via keyboard input. The figure to right shows teletype output of similar format.

Charts of the Main routine:
Notes on 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:

Notes on 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.)
Running 3D Tic Tac Toe
In order to verify the descriptions and example figures of the 3D tic tac toe algorithm section above, I built a Java program from the presented flowcharts and the shown 1620 list of rows, to run on Windows 7. Also I wanted to learn some Java and have some fun. I was interested in finding out how much of an edge the first mover has in the game if both players are using the implemented strategy, so I based moves at Level 11 (random machine move to an open major diagonal move) on a random number generator seeded once (msecs past start_1970) at the first new game after the application is started, and extended possible play till all board locations were taken (and Level 12: random machine move to any open location), possibly ending in a tie. An option is added to game management to provide for two copies (each separately  started manually) of the application to play each other for multiple games, with moves coordinated through a common lock file, and with first-mover, second-mover, and tie totals maintained at each copy.

The end of an automatic 1000 game run is shown here. In this run, the first mover wins about 55% of the games, the second mover 40%, with 5% ties. A subsequent run yielded 59%, 35%, and 6% - more typical figures. (The first mover alternates between copies fairly evenly.)