tictactoe-comments.bf

[-][

  Tic tac toe/naughts-and-crosses AI in brainfuck, written by mitxela

  To play, type a number between 1 and 9 to place an X there.

  I wanted to just release the minimized version and remain mysterious, but it's
  quite long with a lot of repetition and some people might think that it was
  transcompiled from something else.

  So, below is the original source code with comments that made sense at the time.
  The choose-a-number script was the first bit I wrote and is in a separate file,
  included here is the minimized version of it.

  Although a perfect AI would have been possible, I deliberately left in a few 
  possible games where the AI can lose. It would be boring otherwise.

  One thing I quickly learned while writing this is to use boolean flags as much 
  as possible. Checking if a cell is zero is so much easier than checking if it's
  exactly one, or two, etc. Another tactic I worked out was to place markers in
  memory of -1 (or 255). Lots of routines 'get lost' by not leaving the memory
  pointer in a fixed location, so in order to recover I frequently use things like

    +[->+]-

  which means, "head right until you reach a cell of value -1". This lets us put
  reference points in memory that we can always recover to. 

  The interpreter I used for developing this: https://mitxela.com/other/brainfuck

  Originally written over the weekend of 6 May 2017. An excellent weekend it was.

]



+ game end bool
home ref >-
[ endless loop
>



reference
>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> 

ref
++[-]-
ifempty bools
>>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+>>>+
back to ref
+[-<+]-

<<<<
+ bool first move
<<
++++[->++++++++<]> space
<<
++[------>+<]>++ hyphen
<<
+[--->++<]>++ X
<<
-[--->+<]>------ O



go home
<
+[-<+]-
>


main loop
<<[>> 




draw board
 goto ref
 +[->+]- 





<[-]
<<[-]+++
[
>[-]++++++++++.[-]+++
[
>
counter
+
copy to adj
[>>+<<-]
copy to home
>>
 [<<+ 
  +[-<+]-
  >+
  +[->+]-
  >-]
<< +[-<+]- home
>
-[-[-[-[-[-[-[-[->>>]>>>]>>>]>>>]>>>]>>>]>>>]>>>]

go to board

>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> 
>>> b0

 if boolempty [ +[-<+]-<<<<<<.>>>>>>> ]
 if X    >    [ +[-<+]-<<<<<<<.>>>>>>>> ]
 if O    >    [ +[-<+]-<<<<<<<<.>>>>>>>>> ]

 +[-<+]-

<<<<<.>>>>> space

<<-
]


<-
]
++++++++++.[-]
>>>









<<<<<<<<< win flag

[
<< <<<<<<<< <
+[--->++<]>+++.[->+++++++<]>.++++++.-[---->+<]>+++.---[->+++<]>.+++[->++++<]>+.+++++.-[->+++++<]>.[--->+<]>-.

 +[-<+]- <[-]>>>> end game
]


< board full == draw flag
[

<<<<< <<
++++[++++>---<]>+.[++++>---<]>-.+++[->+++<]>++.+[--->+<]>+.+[---->+<]>+++.[--->+<]>-.[-]
 +[-<+]- <[-]>>>> end game
]

< lose flag
[

<< <<<<<<<<
+[--->++<]>+++.[->+++++++<]>.++++++.-[---->+<]>+++.++++++[->++<]>.+[--->+<]>.++++.++++[->+++<]>.--[--->+<]>.[--->+<]>-.
 +[-<+]- <[-]>>>> end game
]



go home
<
+[-<+]-
>
end draw board


dont accept input on gameover
<<[>>

(choosenumber)
>>>>>>+[-<<<<[-]<<[-]>>>>-[>>[-]+<<+<[-]<[-]<[-]<[-]-[----->+<]>---<,>[-<->]<[>>+>+<<<-]>>[<<+>>-]+++++++++[->-[<<]>]>>-]<<<<[-]>>>>[-]+<<<<<<[>>+>+<<<-]>>[<<+>>-]>>]>>-<<<[-]<<[<->-]<



-[-[-[-[-[-[-[-[-
>>>]>>>]>>>]>>>]>>>]>>>]>>>]>>>]

]

move to board
>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> 
>>> b0



is space empty bool=1
[
 ->+ empty=0 and x=1


redraw=1 perhaps
 






===== check for win ========

horizontal 
  +[-<+]-
  top row
  >>>> x> b0  [ >>> b1 [ >>> b2 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

  +[-<+]- 
  mid row
  >>>> >>> >>> >>>
  x> b3  [ >>> b4 [ >>> b5 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

  +[-<+]- 
  bottom row
  >>>> >>> >>> >>> >>> >>> >>>
  x> b6  [ >>> b7 [ >>> b8 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

vertical
  left
  +[-<+]-
  >>>> x> b0 [ >>> >>> >>> b3 [ >>> >>> >>> b6 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]
  middle
  +[-<+]-
  >>>> x> >>> [ >>> >>> >>> [ >>> >>> >>> [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]
  right
  +[-<+]-
  >>>> x> >>> >>> [ >>> >>> >>> [ >>> >>> >>> [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

diagonal
  +[-<+]-
  >>>> x> b0 [ >>> >>> >>> >>> b4 [ >>> >>> >>> >>> b8 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]] 

  +[-<+]-
  >>>> x> >>> >>> b2 [ >>> >>> b4 [ >>> >>> b6 [
   +[-<+]- <<<<<<<<< [-]+ 
   +[->+]- >
  ]]] 

if not won
+[-<+]-<<<<<<<<<-[+  +[->+]- 





==== check for board full ====
  

  set fullboard=1
  <<<<<<<<<< [-]+ 

   +[->+]->
   >>> b0 
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> b1 
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> >>> b2 
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >   
   >>> >>> >>> >>> b3
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >   
   >>> >>> >>> >>> >>> b4
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> >>> >>> >>> >>> b5
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> >>> >>> >>> >>> >>> b6
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> >>> >>> >>> >>> >>> >>> b7
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >
   >>> >>> >>> >>> >>> >>> >>> >>> >>> b8
   [ +[-<+]-<<<<<<<<<< [-] +[->+]-> ] +[-<+]- >


==== Make Move ===
<<<[-]>>> move
<<[-]+>> move not chosen flag



prevent a winning move from x

horizontal
top row
 >>> > b0X  [ >>> b1X [ >> b2empty [
   +[-<+]- <[-]<[-] +++ move 3
   +[->+]- >
  ]]]>+[-<+]->

 >>> > b0X  [ >> b1empty [ >>> > b2X [
   +[-<+]- <[-]<[-] ++ move 2
   +[->+]- >
  ]]]>+[-<+]->

 >>> b0empty  [ >>> > b1X [ >>> b2X [
   +[-<+]- <[-]<[-] + move 1
   +[->+]- >
  ]]]>+[-<+]->

mid row
 >>> >>> >>> >>> > bX  [ >>> bX [ >> bempty [
   +[-<+]- <[-]<[-] ++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> > bX  [ >> bempty [ >>> > bX [
   +[-<+]- <[-]<[-] +++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> bempty  [ >>> > bX [ >>> bX [
   +[-<+]- <[-]<[-] ++++
   +[->+]- >
  ]]]>+[-<+]->
bottom row
 >>> >>> >>> >>> >>> >>> >>> > bX  [ >>> bX [ >> bempty [
   +[-<+]- <[-]<[-] +++++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> >>> >>> >>> > bX  [ >> bempty [ >>> > bX [
   +[-<+]- <[-]<[-] ++++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> >>> >>> >>> bempty  [ >>> > bX [ >>> bX [
   +[-<+]- <[-]<[-] +++++++
   +[->+]- >
  ]]]>+[-<+]->


vertical
left
 >>> > b0X  [ >>> >>> >>> b3X [ >>> >>> >> b6empty [
   +[-<+]- <[-]<[-] +++ +++ + move 7
   +[->+]- >
  ]]]>+[-<+]->

 >>> > b0X  [ >>> >>> >> b3empty [ >>> >>> >>> > b6X [
   +[-<+]- <[-]<[-] ++++ move 4
   +[->+]- >
  ]]]>+[-<+]->

 >>> bempty  [ >>> >>> >>> > bX [ >>> >>> >>> bX [
   +[-<+]- <[-]<[-] + move 1
   +[->+]- >
  ]]]>+[-<+]->
centre
 >>> >>> > bX  [ >>> >>> >>> bX [ >>> >>> >> bempty [
   +[-<+]- <[-]<[-] +++ +++ ++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> > bX  [ >>> >>> >> bempty [ >>> >>> >>> > bX [
   +[-<+]- <[-]<[-] ++++ +
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> bempty  [ >>> >>> >>> > bX [ >>> >>> >>> bX [
   +[-<+]- <[-]<[-] ++
   +[->+]- >
  ]]]>+[-<+]->
right
 >>> >>> >>> > bX  [ >>> >>> >>> bX [ >>> >>> >> bempty [
   +[-<+]- <[-]<[-] +++ +++ +++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> > bX  [ >>> >>> >> bempty [ >>> >>> >>> > bX [
   +[-<+]- <[-]<[-] ++++ ++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> bempty  [ >>> >>> >>> > bX [ >>> >>> >>> bX [
   +[-<+]- <[-]<[-] +++
   +[->+]- >
  ]]]>+[-<+]->

diagonals
se
 >>> > b0X  [ >>> >>> >>> >>> b4X [ >>> >>> >>> >> b8empty [
   +[-<+]- <[-]<[-] +++ +++ +++
   +[->+]- >
  ]]]>+[-<+]->

centre middle empty will never happen

 >>> b0empty  [ >>> >>> >>> >>> > b4X [ >>> >>> >>> >>> b8X [
   +[-<+]- <[-]<[-] +
   +[->+]- >
  ]]]>+[-<+]->

sw
 >>> >>> >>> > b2X  [ >>> >>> b4X [ >>> >> b6empty [
   +[-<+]- <[-]<[-] +++ +++ +
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> b2empty  [ >>> >>> > b4X [ >>> >>> b6X [
   +[-<+]- <[-]<[-] +++
   +[->+]- >
  ]]]>+[-<+]->

take a winning move if available


horizontal
top row
 >>> >> b0O  [ >>> b1O [ > b2empty [
   +[-<+]- <[-]<[-] +++ move 3
   +[->+]- >
  ]]]>+[-<+]->

 >>> >> b0O  [ > b1empty [ >>> >> b2O [
   +[-<+]- <[-]<[-] ++ move 2
   +[->+]- >
  ]]]>+[-<+]->

 >>> b0empty  [ >>> >> b1O [ >>> b2O [
   +[-<+]- <[-]<[-] + move 1
   +[->+]- >
  ]]]>+[-<+]->

mid row
 >>> >>> >>> >>> >> bO  [ >>> bO [ > bempty [
   +[-<+]- <[-]<[-] ++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> >> bO  [ > bempty [ >>> >> bO [
   +[-<+]- <[-]<[-] +++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> bempty  [ >>> >> bO [ >>> bO [
   +[-<+]- <[-]<[-] ++++
   +[->+]- >
  ]]]>+[-<+]->
bottom row
 >>> >>> >>> >>> >>> >>> >>> >> bO  [ >>> bO [ > bempty [
   +[-<+]- <[-]<[-] +++++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> >>> >>> >>> >> bO  [ > bempty [ >>> >> bO [
   +[-<+]- <[-]<[-] ++++++++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >>> >>> >>> >>> bempty  [ >>> >> bO [ >>> bO [
   +[-<+]- <[-]<[-] +++++++
   +[->+]- >
  ]]]>+[-<+]->


vertical
left
 >>> >> b0O  [ >>> >>> >>> b3O [ >>> >>> > b6empty [
   +[-<+]- <[-]<[-] +++ +++ + move 7
   +[->+]- >
  ]]]>+[-<+]->

 >>> >> b0O  [ >>> >>> > b3empty [ >>> >>> >>> >> b6O [
   +[-<+]- <[-]<[-] ++++ move 4
   +[->+]- >
  ]]]>+[-<+]->

 >>> bempty  [ >>> >>> >>> >> bO [ >>> >>> >>> bO [
   +[-<+]- <[-]<[-] + move 1
   +[->+]- >
  ]]]>+[-<+]->
centre
 >>> >>> >> bO  [ >>> >>> >>> bO [ >>> >>> > bempty [
   +[-<+]- <[-]<[-] +++ +++ ++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >> bO  [ >>> >>> > bempty [ >>> >>> >>> >> bO [
   +[-<+]- <[-]<[-] ++++ +
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> bempty  [ >>> >>> >>> >> bO [ >>> >>> >>> bO [
   +[-<+]- <[-]<[-] ++
   +[->+]- >
  ]]]>+[-<+]->
right
 >>> >>> >>> >> bO  [ >>> >>> >>> bO [ >>> >>> > bempty [
   +[-<+]- <[-]<[-] +++ +++ +++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> >> bO  [ >>> >>> > bempty [ >>> >>> >>> >> bO [
   +[-<+]- <[-]<[-] ++++ ++
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> bempty  [ >>> >>> >>> >> bO [ >>> >>> >>> bO [
   +[-<+]- <[-]<[-] +++
   +[->+]- >
  ]]]>+[-<+]->

diagonals
se
 >>> >> b0O  [ >>> >>> >>> >>> b4O [ >>> >>> >>> > b8empty [
   +[-<+]- <[-]<[-] +++ +++ +++
   +[->+]- >
  ]]]>+[-<+]->

 >>> b0empty  [ >>> >>> >>> >>> >> b4O [ >>> >>> >>> >>> b8O [
   +[-<+]- <[-]<[-] +
   +[->+]- >
  ]]]>+[-<+]->

sw
 >>> >>> >>> >> b2O  [ >>> >>> b4O [ >>> > b6empty [
   +[-<+]- <[-]<[-] +++ +++ +
   +[->+]- >
  ]]]>+[-<+]->

 >>> >>> >>> b2empty  [ >>> >>> >> b4O [ >>> >>> b6O [
   +[-<+]- <[-]<[-] +++
   +[->+]- >
  ]]]>+[-<+]->



=========




if move not chosen
<<[>>

+[-<+]->
>>> >>> >>> >>> >>> >>> >>> >>> >>> b8 [
   +[-<+]- <[-]<[-] +++++++++ move 9
   +[->+]- >
]
+[-<+]->
>>> >>> >>> >>> >>> >>> >>> b6 [
   +[-<+]- <[-]<[-] +++ +++ + move 7
   +[->+]- >
]
+[-<+]->
>>> >>> >>> b2 [
   +[-<+]- <[-]<[-] +++ move 3
   +[->+]- >
]
+[-<+]->
>>> b0 [
   +[-<+]- <[-]<[-] + move 1
   +[->+]- >
]
+[-<+]->
>>> >>> >>> >>> >>> >>> >>> >>>b7 [
   +[-<+]- <[-]<[-] +++ +++ ++ move 8
   +[->+]- >
]
+[-<+]->
>>> >>> >>> >>> >>> >>> b5 [
   +[-<+]- <[-]<[-] +++ +++ move 6
   +[->+]- >
]
+[-<+]->
>>> >>> >>> >>> b3 [
   +[-<+]- <[-]<[-] +++ + move 4
   +[->+]- >
]

+[-<+]->
>>> >>> b1 [
   +[-<+]- <[-]<[-] ++ move 2
   +[->+]- >
]

+[-<+]->
>>> >>> >>> >>> >>> b4 [
   +[-<+]- <[-]<[-] +++ ++ move 5
   +[->+]- >
]

+[-<+]->

]>>


+[-<+]-
<<<<[ if first move 

+[->+]->
>>> >>> >>> >>> >>> > b4X [
   +[-<+]- <[-]<[-] + move 5
   +[->+]- >
]
+[-<+]->

]>>>>


DEBUG if move chosen
+[-<+]->
<<<[>>>





copy chosen move into home cell
+[-<+]- <[-]<

[+[-<+]->  +  +[->+]- <<-]
+[-<+]->
-[-[-[-[-[-[-[-[->>>]>>>]>>>]>>>]>>>]>>>]>>>]>>>]

move to board
>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> 
>>> b0 ->>+ O




DEBUG if move chosen
+[-<+]- >
]>>>>+[-<+]- <<[-]>>>




escape
+[-<+]- 
<<<<[-]>>>> firstmove bool

>


===== check for win ========

horizontal 
  +[-<+]-
  top row
  >>>> O>> b0  [ >>> b1 [ >>> b2 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

  +[-<+]- 
  mid row
  >>>> >>> >>> >>>
  O>> b3  [ >>> b4 [ >>> b5 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

  +[-<+]- 
  bottom row
  >>>> >>> >>> >>> >>> >>> >>>
  O>> b6  [ >>> b7 [ >>> b8 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

vertical
  left
  +[-<+]-
  >>>> O>> b0 [ >>> >>> >>> b3 [ >>> >>> >>> b6 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]
  middle
  +[-<+]-
  >>>> O>> >>> [ >>> >>> >>> [ >>> >>> >>> [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]
  right
  +[-<+]-
  >>>> O>> >>> >>> [ >>> >>> >>> [ >>> >>> >>> [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]]

diagonal
  +[-<+]-
  >>>> O>> b0 [ >>> >>> >>> >>> b4 [ >>> >>> >>> >>> b8 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]] 

  +[-<+]-
  >>>> O>> >>> >>> b2 [ >>> >>> b4 [ >>> >>> b6 [
   +[-<+]- <<<<<<<<<<< [-]+ 
   +[->+]- >
  ]]] 


+[-<+]- <[-]

]+ +[->+]->
 
] end space empty check


escape
+[-<+]- 

return home
<
+[-<+]-
>

<<] back to start



game over reset
>>+[->+]- >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> > end of data
+[-[-]<+]- <
+[-[-]<+]- <+> 



]