\. This is a simple and fast implementation of the game TIC TAC TOE. The first two responsive moves made by the computer are done by table lookup (when the computer moves first, this is in addition to its initial move, which is always the upper left corner). Subsequent moves follow a simple end-game strategy: 1) Finish a row of three if possible (and win!) 2) Block a row of three, to prevent an opposing win 3) Fill in an empty corner next to one of your tokens 4) Pick any side square 5) Pick any other squre This strategy seems to be optimal, given the initial play. Note that we never do any checking for rows that are empty except for one of our tokens, nor for the intersection of two such rows. .\ \* The game board is layed out like this: 0 | 1 | 2 ----------- 3 | 8 | 5 ----------- 6 | 7 | 4 We have two sets of lookup tables: one set is used if the human moves first, the other set is used if the computer moves first. When the latter happens, the computer always takes the upper left corner. *\ 0 constant computer-first-move -1 constant u ( illegal ) : human-first-table {{ 8 8 8 8 8 8 8 8 0 }} ; : comp-first-table {{ u 8 6 8 2 8 2 8 4 }} ; : hf0 {{ u 2 1 6 3 7 3 5 u }} ; : hf1 {{ 2 u 0 6 3 4 5 3 u }} ; : hf2 {{ 1 0 u 7 5 4 7 3 u }} ; : hf3 {{ 6 6 7 u 1 7 0 4 u }} ; : hf4 {{ 7 3 5 1 u 2 7 6 u }} ; : hf5 {{ 7 0 4 1 2 u 1 2 u }} ; : hf6 {{ 3 5 5 0 7 1 u 4 u }} ; : hf7 {{ 5 5 3 4 6 6 4 u u }} ; : hf8 {{ u 7 6 5 2 3 2 1 u }} ; : human-first-table-n {{ hf0 hf1 hf2 hf3 hf4 hf5 hf6 hf7 hf8 }} ; : cf0 {{ u u u u u u u u u }} ; : cf1 {{ u u c c 6 c c c u }} ; : cf2 {{ u b u 4 b b u b b }} ; : cf3 {{ u c c u 1 c c c u }} ; : cf4 {{ u 6 u 9 u 9 9 9 9 }} ; : cf5 {{ u c c c 2 u c c u }} ; : cf6 {{ u 4 u 9 9 9 u 9 9 }} ; : cf7 {{ u c c c 6 c c u u }} ; : cf8 {{ u 7 6 5 u 3 2 1 u }} ; : comp-first-table-n {{ cf0 cf1 cf2 cf3 cf4 cf5 cf6 cf7 cf8 }} ; \* Squares in our array can have three values: x-token, o-token, or empty. Note that "#empty" is used to keep track of how many squares on the board are empty -- this lets us know when the game is over. This is set to 9 when we clear the game-board. It is decremented whenever we store a token on the board. It is set to 1 whenever we generate a winning move (so that it will go to zero when we store that move). *\ create game-board 9 allot 0 constant #empty : square@ (s square# -- value ) game-board + c@ ; : square! (s value square# -- ) game-board + c! #empty 1- is #empty ; 0 constant empty 1 constant x-token 2 constant o-token 0 value win : clear-game-board game-board 9 erase 9 is #empty 0 is win ; 0 constant computer-token 0 constant computer-move \* To win or to block, we need to check the 8 possible rows on the game board. We keep the result of these checks in 8 values, so that once we've computed all of these (in order to tell whether we can win, need to block, or can do something else), we don't need to recompute them in order to determine our move. Note that if we can't win, and don't need to block, we try to fill in corners next to one of our tokens, in order to win games such as (opponent=X to move) | X | 0 | 1 | 2 ----------- ----------- O | O | 3 | 4 | 5 ----------- ----------- | X | 6 | 7 | 8 If none of these are available, then we try to fill in sides, in order to make games such as (computer=X to move) as difficult as possible for the opponent. X | | O 0 | 1 | 2 ----------- ----------- O | X | X 3 | 4 | 5 ----------- ----------- | | O 6 | 7 | 8 *\ 0 constant row0 0 constant row1 0 constant row2 0 constant row3 0 constant row4 0 constant row5 0 constant row6 0 constant row7 : row-n {{ row0 row1 row2 row3 row4 row5 row6 row7 }} ; : n1 (s row# -- element#1 ) {{ 0 3 6 0 1 2 0 2 }} ; : n2 (s row# -- element#1 ) {{ 1 8 7 3 8 5 8 8 }} ; : n3 (s row# -- element#1 ) {{ 2 5 4 6 7 4 4 6 }} ; : row? (s row# -- who.wins ) dup n1 square@ over n2 square@ rot n3 square@ 3dup xor xor 0= -rot or and nip ; : any-move-order {{ 1 7 3 5 0 2 6 4 8 }} ; : any-move u is computer-move 9 0 do i any-move-order square@ 0= if i any-move-order is computer-move leave then loop ; : end-game-move (s -- move ) 0 row? dup is row0 1 row? dup is row1 or 2 row? dup is row2 or 3 row? dup is row3 or 4 row? dup is row4 or 5 row? dup is row5 or 6 row? dup is row6 or 7 row? dup is row7 or ?dup if computer-token and if 1 is #empty computer-token else true then 8 0 do dup i row-n and if i n1 square@ 0= if i n1 is computer-move then i n2 square@ 0= if i n2 is computer-move then i n3 square@ 0= if i n3 is computer-move then leave then loop drop else 0 square@ empty = 1 square@ computer-token = 3 square@ computer-token = or and if 0 is computer-move else 2 square@ empty = 1 square@ computer-token = 5 square@ computer-token = or and if 2 is computer-move else 6 square@ empty = 3 square@ computer-token = 7 square@ computer-token = or and if 6 is computer-move else 8 square@ empty = 5 square@ computer-token = 7 square@ computer-token = or and if 8 is computer-move else any-move then then then then then computer-move ; \* For the actual play, we define a board that we print out, an input routine to get the human's moves, and a routine to play a game (broken into the human-first and computer-first cases, with a common end game strategy). The number of empty squares left is used to tell when we're done, and this value is set to 1 by the end-game-move routine if it finds a win, so that the loop will exit early. *\ : .x (s val -- ) dup x-token = if ." X " then dup o-token = if ." O " then empty = if ." " then ; : .board cr ." " 0 square@ .x ." |" 1 square@ .x ." |" 2 square@ .x ." 0 | 1 | 2" cr ." ----------- -----------" cr ." " 3 square@ .x ." |" 8 square@ .x ." |" 5 square@ .x ." 3 | 4 | 5" cr ." ----------- -----------" cr ." " 6 square@ .x ." |" 7 square@ .x ." |" 4 square@ .x ." 6 | 7 | 8" ; : get-move (s -- move ) cr .board cr cr ." Move? " key ascii 0 - dup 8 = if 4 nip else dup 4 = if 8 nip then then dup square@ empty <> abort" Illegal move!" computer-token o-token = if x-token else o-token then over square! ; : play1 clear-game-board cr ." Do you wish to go first? (y/n)" key ascii y = if o-token is computer-token get-move dup human-first-table computer-token swap square! get-move swap human-first-table-n computer-token swap square! else x-token is computer-token computer-token computer-first-move square! get-move dup comp-first-table computer-token swap square! get-move swap comp-first-table-n dup 8 >= if 8 - -1 is win then computer-token swap square! then win not if begin #empty 0> if get-move drop then #empty 0> while computer-token end-game-move square! repeat then cr .board cr cr ." Thanks for the game!" ; : play cr ." Welcome to TIC TAC TOE! " begin play1 ." Play again? (y/n)" key ascii y <> until ; play