NB. TTT3D game NB. DanB 2000/03/03 NB. This version is procedural and more APL like. Little tacit definition is used. NB. It uses the session manager to interact with the user. NB. Some elements are already in place for a window version but are not used here. NB. To use 2D graphics load the '2D code' AFTER this one which contains the core code NB. PLUS routines to work in line mode. NB. Last mod 2000/10/01 VERSION=: ":2j24 NB. Some utilities any=: ?@# { ] ask=: 3 : 'get 1 [ out y.' NB. get answer after showing argument dbout=: 3 : 'if. DEBUG do. out ":y. end.' each=: &.> get=: 1!:1 out=: 1!:2&2 rlb=: ] }.~ 0: i.~ ' '"_ = ] NB. Remove Leading Blanks upper=: 3 : '(a.i.y.){(A{a.)a}a.[''A a''=.(a.i.''Aa'')+/i.26' Signal=:13!:8&99 NB. all line mode commands c_allcmds=: }:upper each t=.;:'back canhe cani exec eval force help how quit bad' c_allfns=: 'c_'&,&.>t NB. all corresponding code c_back=: 'Not available yet!'"_ c_bad=:(>'*** Invalid command';'Type ")HELP" for list of commands';'')"_ c_canhe=: 3 : 0 NB. how can X win - depends if sol already found (solution in How) if. 0=#how=.How do. how=.X try O end. if. *#how do. 'XO',.':',.' ',.showslots"1 |:how else. 'THE machine cannot win.' end. ) c_cani=: 3 : 0 NB. How can O win Force=:33 [ copy=.Force if. *#how=.O try X do. r=.(2 3$'O: X: '),.showslots"1 |: how else. r=.'You cannot win.' end. r [ Force=:copy ) c_exec=: 3 : 'try. ": ".y. catch. ''Bad argument'' end.' c_eval=: 3 : 0 NB. evaluate slots (12 shown by default) i=.\:v=.FREESLOTS*evaluate 10#.|.10 10#:STATE ({.,12,~,".y.){.('=',.~i{Slots),.":,.i{v ) c_force=:3 : 0 NB. Change level of the game if. #y.-.' ' do. Force=:".y. [ How=:0#How [f=.Force 'was ',":f else. 'is ',":Force end. ) c_help=:3 : 0 >('* Choose one of: ',;' )'&,&.>c_allcmds) NB. ;' or ")HELP commands" for details' ) c_how =: 3 : 0 NB. display how we think we can win if. #How do. (2 3$'I: U: '),.showslots"1 |: How else. 'I don''t know how to win... yet!' end. ) c_quit=: 3 : 'Signal ''quitting''' NB. =========== * end of line mode commands * =========== cursor=: 3 : 0 NB. milinta 20000127 set shape of cursor i.0 0 NB. nothing in this version ) DESCRIBE=: 0 : 0 3-D X and Os (Tic-Tac-Toe) You can play this game by typing 'ttt '''''. The game is played in a cube 4*4*4 and we play one after the other aiming at filling in 4 slots in a row, pretty much like in the traditional 3*3 game. The cube is shown as 4 planes of 4*4 positions side by side. To play, simply specify the position chosen by entering the number of the slot where you want to play. To win you must line up 4 slots with your Os. I, the program, am your opponent. I use the Xs, you use the Os. My strength may be specified at the prompt where a list of options are available. By default I play at "Block" level, meaning that I will block your attempts at lining up 4 slots but I won't use any strategy to win. At the "Easiest" level I play randomly and I won't try to block you. At higher levels I try to foresee a winning situation. The higher the level, the better I am. At high levels you don't stand many chances. If I am about to win I will announce my move and how many moves you have left. Here's an example. See the 4 planes side by side: 旼컴컴컴컴컴컴쩡컴컴컴컴컴컴쩡컴컴컴컴컴컴쩡컴컴컴컴컴컴� 넬컴쩡컫컴쩡커넬컴쩡컫컴쩡커넬컴쩡컫컴쩡커넬컴쩡컫컴쩡커� 납O �13�14�15납�28�29�30�31납�44�45�46�47납�60�61�62�63납 냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑� 납08�09�10�11납�24�25�26�27납�40�41�42�43납�56�57�58�59납 냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑� 납04�05�06�07납�20�21�22쿦 납�36�37�38�39납�52�53�54�55납 냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑냉컴탠컵컴탠캑� 납00�01�02�03납�16�17�18�19납�32�33�34�35납�48�49�50�51납 냅컴좔컨컴좔켸냅컴좔컨컴좔켸냅컴좔컨컴좔켸냅컴좔컨컴좔켸� 읕컴컴컴컴컴컴좔컴컴컴컴컴컴좔컴컴컴컴컴컴좔컴컴컴컴컴컴� Here, the 'X' is at position 23 and the 'O' at position 12. Examples of winning sequences (using another system of 4 different planes A, B, C & D): x: A11 A12 A13 A14 Note that winning slots are o: D14 D23 D32 D41 always either on the same plane or y: A31 B31 C31 D31 on a different plane for each slot. z: A41 B42 C43 D44 The same rule applies to columns #: A44 B33 C22 D11 and rows...! A B C D 4 z . . # . z . . . . z . o . . z 3 y . . . y . # . y . . . y o . . 2 . . . . . . . . . # . . . . o . 1 x x x x . . . . . . . . # . . o 1 2 3 4 Again, you play with the Os and I with the Xs. Good luck. Dan Baronet. ) draw=:out NB. "send to screen" in line mode NB. s=.X evalstate O evalstate=: 4 : '+/"1 Lines{ 1 y.} 10 x.}64$0' evaluate=: 3 : 0 NB. value=.evaluate STATE NB. return a value for each slot according to the state of each line NB. note that some globals are in index representation to account for the NUL case lw=.LVALUE{~i=. 0 1 2 10 20 i. y. NB. each Line's Weight excess=. +/"1 (ILP{i){NSLOTS NB. excess 'valuable' slots on each plane value =. plval excess NB. transformation fn: value of each plane value =. 0,lw*+/"1 IPL{0,value NB. each line's evaluation value =. 1>.+/"1 ISL{value NB. each slot's evaluation ) frees=: 3 : '(y.{F_s_) # y.' NB. keep free slots only histurn=: 3 : 0 NB. player routine - ask which slot to play; allow commands to be executed N=. {: $Slots [ p=.'Select a position: ' while. +./(n=.')'=1{.t),(0=#t),0=+/s=.FREESLOTS *. Slots-:"1 N pad0 t=.rlb ask p do. if. n do. 'cmd arg'=. }.each t ({. ; }.)~ t i. ' ' NB. a command? out(>(c_allcmds i.msg;'Type )HELP for list of commands';'' end. end. FREESLOTS=: FREESLOTS > s STATE =: STATE + +./"1 Lines = o=.s i. 1 Moves_s_ =: Moves_s_,0 game we check a few things: elseif. poor<30 e. STATE do. NB. we win (we don't at level 1) r=.play {.frees sline 30 elseif. 3 e. STATE do. NB. we are forced at level>0 r=.play frees l=.4{.sline 3 r=. r,lbl#' to block your ',showslots l elseif. ino do. NB. we found a solution a while back r=.play 1$,How NB. and we play it How=:}.How NB. remove the move from the list elseif. poor do. NB. Level 1 has checked if it can block or won before r=.play any where FREESLOTS elseif. 20 e. STATE do. NB. it might be possible to win, let's check cursor 1 NB. hourglass shape to show we're "thinking" if. l=.#How=:X try O do. NB. Yes! r=.'I win within ',(":l),' moves. ' r=.r,play {.,How How=:}.How [ dbout 'Winning solution:';|:How [ cursor 0 end. end. NB. 'r' should contain our answer if. 0=#r do. NB. if it doesn't (because we haven't been able to find a spot), if. +./2 10 1 0 30 e. STATE do. NB. it is still possible to win, cunningly... NB. let's rank each slot dbout |:(21{.\:value){ALL,.value=.FREESLOTS*evaluate STATE NB. and see if the opponent can win dbout 'S/he can win at:';l=.,0 _1}.O try X NB. see if player can win NB. then pick the most valuable of them if. 0=#l do. l=.where FREESLOTS end. v=. l{value NB. the value of each possible slot l=. (v=>./v)#l NB. the best ones r=. play any l NB. play one of them elseif. do. NB. no more slots to win either side r=.'* NUL game' end. end. if. 40 e. STATE do. NB. program won r=.'* ',r,' and I win',lbl#' on ',,showslots WinLine=: sline 40 [ winner=.'I' elseif. 30 e. STATE do. NB. help player r=. r,'!!!' end. cursor 0 Moves_s_=:Moves_s_,.et*1000),' ms) ' ) plval=: 2: ^ | NB. used in (heuristic) evaluation run=: 4 : 0 NB. run through the tree starting at 'br' br=.x.,y. NB. this branch if. #nbr=.simulate br do. NB. find new branches br run"_ 1 nbr NB. try each one end. i.0 0 ) showcube =: 4 : 0 NB. display each plane of the game out <@|."2 ]4 4 4$(<'X')x.} (<'O')y.} <"1 Slots NB. variation: NB.out(<"0 'GBRP'),:<@|."2 ]4 4 4$(<'X')x.} (<'O')y.} <"1 Slots ) showslots=: 3 : 0 NB. r=.showslots s ,' ',"1~ y.{Slots ) simulate=: 3 : 0 NB. Given a list of moves return a list of possible forcing new moves NB. 'State' is the original state of the game before any move in the list. r=.0#xo=.y. NB. assume no possible new move if. Force>#xo do. NB. exit if max search level reached FREESLOTS=.F_s_=:0 (,xo)}Free_s_ NB. free slots=original free-used so far STATE=.S_s_=:State_s_+evalstate&>/<"1 |:xo NB. the state of each line if. 30 e. STATE do. NB. Can I win? Seq_s_=. xo,2{.frees sline 30 NB. Yes. take note of the winning sequence Signal 'end' elseif. 3 e. STATE do. NB. Can S/HE win? NB. here we are forced to play. If at more than 1 place then this is hopeless. if. 1=#slots=.frees sline 3 do. NB. only 1 place? NB. we may be able to continue if we also force opponent when we play if. +./which=.(STATE=20)*.+./"1 Lines={.slots do. NB. indeed we are: r=. ,:(slots~:1$t)|.t=.2{.frees ,which#Lines end. end. NB. we cannot win but we might be able to further force opponent to play elseif. 20 e. STATE do. slots=. frees sline 20 value=.0,StateValue{~0 1 2 10 20 i. STATE NB. value of each line value=.+/"1 value{~ISL{~slots NB. value of each slot ord=.(MAXBR<.#r){.r=.\:value NB. select MAXBR branches r=.slots{~ord,.ord+_1^ord NB. alternate pairs NB. no more possible move end. end. r ) sline=: 3 : ',(S_s_=y.) # Lines' ssss =: 6!:1 NB. Seconds Since Start of Session try=: 4 : 0 NB. Seq=.X try O;Free;State;Search NB. try to find a winning sequence given x and o NB. Use locale 's' for searching purposes NB. Set initial state variables Free_s_=. -.ALL e. x.,y. [ State_s_=.x. evalstate y. try. run~ Seq_s_=.0 2$0 NB. assume an empty result catch. end. Seq_s_ ) ttt=: 3 : 0 NB. Main program initttt y. if. LineMode do. whilst. '*'~:{.out myturn '' do. X showcube O histurn '' end. WIN_MSG 'The game lasted ',(0":(ssss 0)-{.Total),' secs of which I used ',":{:Total end. ) where=: ] # i.@# ALL=: i. 64 CanChangeLevel=: 0 ChangeLevel=: 3 : 0 NB. ChangeLevel yn NB. milinta 20000126 set global to dis/allow to change level CanChangeLevel=.y. ) ColoredSlots=: 64 3 $ 'G11G12G13G14G21G22G23G24G31G32G33G34G41G42G43G44B11B12B13B14B21B22B23B24B31B32B33B34B41B42B43B44R11R12R13R14R21R22R23R24R31R32R33R34R41R42R43R44P11P12P13P14P21P22P23P24P31P32P33P34P41P42P43P44' CR=: 10{a. History=: 0 : 0 This workspace was written over the period of about 20 years...! It was first attempted in 1976 and the "real" interesting version came out in 1979 while I was studying at the university. It included most of the logic which allows it to play in line mode today. In 1985 I rewrote it on the Sharp APL system and added some commands (help, go back, end, etc) and put it in public library (where it still resided in 1999) over there. In 1987 I transfered it onto Sharp APL on the PC and STSC's APL*PLUS. It was slow (specially on Sharp's) but ran just the same (I had to modify the search procedure but the logic remained identical). In 1993 I added the ability to play using graphics with STSC's #G functions and "see" the cube better. It's was not perfect yet (rotating the cube more than 90 degrees created problems) but it was getting there! In 1999 I merged the whole playing logic with a workspace in Dyalog APL's outprods\tools to play using Windows' objects. Later on, I rewrote the graphics' part to look like the APL*PLUS version and to fix early problems like extreme rotations. In 2000 I ported the Dyalog APL ws into J. DanB 2000/03/04 ) Istart=: 3 : 0 NB. machine starts a new game ChangeLevel 1 NB. allow to change level initglobals y. draw myturn '' ) ILP=: 18 10 $<: 1 2 3 8 11 14 15 20 27 34 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 2 4 6 21 28 35 37 48 58 68 8 9 10 23 30 39 40 50 60 70 11 12 13 24 31 41 42 51 61 71 15 17 19 26 33 44 46 53 63 73 1 4 5 9 12 16 17 47 57 67 20 21 22 23 24 25 26 54 64 74 27 28 29 30 31 32 33 55 65 75 34 37 38 40 42 45 46 56 66 76 1 6 7 10 13 18 19 54 65 76 34 35 36 39 41 43 44 55 64 67 3 4 7 23 31 43 46 49 59 69 14 17 18 24 30 36 37 52 62 72 2 5 7 22 29 36 38 50 61 73 15 16 18 25 32 43 45 51 60 68 NB. those use index representation because 0 is used to denote something else IPL=: 76 3 $ 1 9 13 1 5 17 1 15 0 5 9 15 9 17 0 5 13 0 13 15 17 1 6 0 6 9 0 6 13 0 1 7 0 7 9 0 7 13 0 1 16 0 1 8 18 9 18 0 8 9 16 13 16 18 8 13 0 1 10 0 5 10 0 10 17 0 6 10 15 7 10 16 10 18 0 8 10 0 1 11 0 5 11 0 11 17 0 6 11 16 7 11 15 11 18 0 8 11 0 1 12 14 5 14 0 14 16 17 5 12 16 12 17 0 6 14 0 6 12 0 7 14 0 7 12 0 14 15 18 8 14 0 12 18 0 8 12 15 2 9 0 2 5 0 2 15 0 2 6 17 2 7 18 2 16 0 2 8 0 2 10 13 2 11 14 2 12 0 3 9 0 3 5 0 3 15 0 3 6 18 3 7 17 3 16 0 3 8 0 3 10 14 3 11 13 3 12 0 4 9 14 4 5 18 4 15 0 4 6 0 4 7 0 4 16 0 4 8 17 4 10 0 4 11 0 4 12 13 ISL=: 64 7 $ 1 2 3 4 5 6 7 1 8 9 10 0 0 0 1 11 12 13 0 0 0 1 14 15 16 17 18 19 2 20 21 22 0 0 0 3 8 20 23 0 0 0 11 14 20 24 0 0 0 15 20 25 26 0 0 0 2 27 28 29 0 0 0 8 14 27 30 0 0 0 3 11 27 31 0 0 0 15 27 32 33 0 0 0 2 14 34 35 36 37 38 8 34 39 40 0 0 0 11 34 41 42 0 0 0 3 15 34 43 44 45 46 4 47 48 49 0 0 0 5 9 47 50 0 0 0 12 16 47 51 0 0 0 17 47 52 53 0 0 0 6 21 48 54 0 0 0 7 10 22 23 49 50 54 13 18 24 25 51 52 54 19 26 53 54 0 0 0 28 35 48 55 0 0 0 29 30 36 39 50 52 55 31 32 41 43 49 51 55 33 44 53 55 0 0 0 37 48 52 56 0 0 0 38 40 50 56 0 0 0 42 45 51 56 0 0 0 46 49 53 56 0 0 0 4 57 58 59 0 0 0 9 16 57 60 0 0 0 5 12 57 61 0 0 0 17 57 62 63 0 0 0 21 35 58 64 0 0 0 23 25 39 43 59 60 64 22 24 36 41 61 62 64 26 44 63 64 0 0 0 6 28 58 65 0 0 0 10 18 30 32 60 62 65 7 13 29 31 59 61 65 19 33 63 65 0 0 0 37 58 62 66 0 0 0 40 45 60 66 0 0 0 38 42 61 66 0 0 0 46 59 63 66 0 0 0 4 16 35 43 67 68 69 9 39 67 70 0 0 0 12 41 67 71 0 0 0 5 17 36 44 67 72 73 21 25 68 74 0 0 0 23 69 70 74 0 0 0 24 71 72 74 0 0 0 22 26 73 74 0 0 0 28 32 68 75 0 0 0 30 70 72 75 0 0 0 31 69 71 75 0 0 0 29 33 73 75 0 0 0 6 18 37 45 68 72 76 10 40 70 76 0 0 0 13 42 71 76 0 0 0 7 19 38 46 69 73 76 Level=: 0: NB. dummy fn replaced in graphics mode LineMode=: 1 Lines=: 76 4 $<: 1 2 3 4 1 5 9 13 1 6 11 16 1 17 33 49 1 18 35 52 1 21 41 61 1 22 43 64 2 6 10 14 2 18 34 50 2 22 42 62 3 7 11 15 3 19 35 51 3 23 43 63 4 7 10 13 4 8 12 16 4 19 34 49 4 20 36 52 4 23 42 61 4 24 44 64 5 6 7 8 5 21 37 53 5 22 39 56 6 22 38 54 7 23 39 55 8 23 38 53 8 24 40 56 9 10 11 12 9 25 41 57 9 26 43 60 10 26 42 58 11 27 43 59 12 27 42 57 12 28 44 60 13 14 15 16 13 25 37 49 13 26 39 52 13 29 45 61 13 30 47 64 14 26 38 50 14 30 46 62 15 27 39 51 15 31 47 63 16 27 38 49 16 28 40 52 16 31 46 61 16 32 48 64 17 18 19 20 17 21 25 29 17 22 27 32 18 22 26 30 19 23 27 31 20 23 26 29 20 24 28 32 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 33 37 41 45 33 38 43 48 34 38 42 46 35 39 43 47 36 39 42 45 36 40 44 48 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 49 53 57 61 49 54 59 64 50 54 58 62 51 55 59 63 52 55 58 61 52 56 60 64 53 54 55 56 57 58 59 60 61 62 63 64 LVALUE=: 1 1 5 3 0 0 MAXBR=: 3 NSLOTS=: 0 1 2 _1 _2 0 NB. planes are G B R & P Slotsgbrp0_15 =: ;<"2 'GBRP',."0 2]>":&.>i.16 Slotsgbrp00_15=: ;<"2 'GBRP',."0 2]>2&pad0@":&.>i.16 Slotsgbrp00_33=: ;<"2 'GBRP',."0 2]>2&pad0@":&.>,4 4{.i.4 10 Slotsgbrp11_44=: ;<"2 'GBRP',."0 2]>2&pad0@":&.>,11+4 4{.i.4 10 Slotsabcd11_44=: ;<"2 'ABCD',."0 2]>2&pad0@":&.>,11+4 4{.i.4 10 Slots0_63=: 2&pad0@": & >i.64 Slots=:Slots0_63 NB. pick desired format here StateValue=: 1 1 0 5 20 0 TECHNIQUE=: 0 : 0 Tic-Tac-Toe 3D The design of this program is based on 3 known theories: 1) sequential machines 2) tree searching 3) heuristic evaluation The 4x4x4 cube consists of 76 lines and 18 planes. The 8 slots in the corners and the 8 slots in the center belong to 7 lines. All others to 4 lines. The former are therefore more important at the beginning. 1 - the vector 'STATE' shows the state of all 76 possible lines in the cube. Each element is a 2 digits integer, the first showing the number of X's, the second the number of O's. Ex.: 12 means 1 X, 2 Os; 3 means 0 X, 3 Os. 2 - the function uses tree searching technique to foresee a winning sequence of X over O (as in X try O). The fn , used by , is recursive and manages the search in the tree while will make a "best" choice of branches to generate at each level. The function does not attempt to find a shorter solution. It stops as soon as it finds one. It can be made to search more or less by limiting the depth of the search. To find a winning situation, function uses variable 'statevalue' which gives a value to each line according to its state and 'MAXBR' determines the maximum number of branches to generate at each level. 3 - if no winning situation is found function will give each slot a value, the higher the better, based on the variable LVALUE and the fn : LVALUE contains a factor for each possible state plval returns a value for each of the planes, given the number of Xs over Os in each plane. Function summarizes the above. ) Ustart=: 3 : 0 NB. start new game - player starts ChangeLevel 1 initglobals y. NB. nothing else to do draw i.0 0 ) WIN_ASK=: 3 : 0 NB. r=. WIN_ASK txt (1{.ask y.)e. 'yY' ) WIN_MSG=: empty@out NB. other code used in graphics version NB. =================================================== NB. Last minute changes here... DisplaySlots=: 1 DisplayTime =: 1 DEBUG=: 0 Force=: 1 NB. easy mode Slots=: Slots0_63 out 'To start enter "ttt ''''" or see "DESCRIBE" for details.'