[Closed] MXS Tic Tac Toe

Cool, but very easy to win as it always does the same thing.

Thanks Paul,

The problem with the tic tac toe 3X3 game is that if both players
plays the game perfectly, then most of the times they will have a tie,
but there are some tricks that the first player can do that will always
result in a win if he with no mistakes.

I used a method described in wikipedia to calculate the best move possible by
following a priority check list, if the best move is unavailable then try the next one.

If you have any idea of how to make it smarter, I will be happy to hear :rolleyes:

Most of the time?
If they both play perfectly, then it’s always a tie

http://www.imdb.com/title/tt0086567/
http://www.everybody-dies.com/

No there is no real way. As far as I know who ever starts wins. Isn’t that the case. If you start in corner anyways. Is this not the case?

OK,
From what I read about this, a perfect game of both of the players
should always result in a tie. At first I wasn’t sure about that because
from what I’ve read in wikipedia, a perfect game is a game played by the
8 priority rules. But now I found out that this system has at list one flaw.
If the player starts with a corner then the computer
will go for the center, then the player marks the opposite corner like so:

       [X][_][_]  -->  [X][_][_]  -->  [X][_][_]
      [_][_][_]  -->  [_][O][_]  -->  [_][O][_]
       [_][_][_]  -->  [_][_][_]  -->  [_][_][X]

Now the top priority for the computer will be to block a 'Fork' possibility
from the player on the top left corner or on the bottom right corner.
This move will not save the computer from a lost. 

       [X][_][_]  -->  [X][_][O]  -->  [X][_][O]  -->  [X][_][O]  -->  [X][_][O]
      [_][O][_]  -->  [_][O][_]  -->  [_][O][_]  -->  [O][O][_]  -->  [O][O][_]
       [_][_][X]  -->  [_][_][X]  -->  [X][_][X]  -->  [X][_][X]  -->  [[b]X[/b]][[b]X[/b]][[b]X[/b]]

But if instead the computer chose to ignore the priority lows, and instead

does something like that:

[X][][] –> [X][O][] –> [X][O][] –> [X][O][] –> [X][O][X] –> [X][O][X] –> [X][O][X]
[][O][] –> [][O][] –> [][O][] –> [][O][] –> [][O][] –> [][O][O] –> [X][O][O]
[][][X] –> [][][X] –> [_][X][X] –> [O][X][X] –> [O][X][X] –> [O][X][X] –> [O][X][X]

It will leads to a Tie.

Now my problem with that is that this is not a mathematical way to solve the game.
If I start relaying on special cases like that I can’t be sure if I cover every possibility or not…

Wikipedia:
http://en.wikipedia.org/wiki/Tic-tac-toe

Any ideas?

Nope. Assuming neither side makes a mistake, Tic-Tac-Toe always ends in a draw
http://www.wikihow.com/Win-at-Tic-Tac-Toe

You must not have seen that movie; I highly recommend it, and if you come away from it not having liked it, I will fully refund your purchase/rental fee

ZeBoxx2 – I sure will see the movie ASAP, and I’m sure I’ll like it,
but now my question is how can I teach the computer to always avoid a lost
without having to specify some special cases?

tic-tac-toe is all about special cases… and it’s a good thing there’s only a few of them (remember, the board has symmetry up the wazoo).

you could have it play against itself in order to determine the next-best step – evaluating all the next possible moves (doable, for tic-tac-toe), then pic the one that leads to a draw the quickest.

OK,
Thank you ZeBoxx2 for all your help.
I’ve added another rule to my system which closes the gap I had.
I call this rule the ‘Sandwich’ rule.

 
 --	Written by: Matan Halberstadt
 --	Date: Monday 09, June 2008.
 --	Contact: Halbertism@Gmail.com
 --			    http://www.halbertism.com 
 
 --*******************************************
 
 try destroyDialog TTTRollout catch ()
 rollout TTTRollout "TTT"
 (
 -- Local Variable Declerations
 ------------------------------------------
   
 	local dim = 120
 	local valArr
 	local testValArr
 	local sequence
 	local tickTest = false
   
 -- User Interface
 ------------------------------------------
 
 	button bnNext "Next Turn" width:dim align:#center enabled:false

 	button bn02 "" width:(dim/3) height:(dim/3) align:#center
 	button bn01 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x - dim/3,bn02.pos.y]
 	button bn03 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x + dim/3,bn02.pos.y]
 	button bn04 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x - dim/3,bn02.pos.y + dim/3]
 	button bn05 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x,bn02.pos.y + dim/3]
 	button bn06 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x + dim/3,bn02.pos.y + dim/3]
 	button bn07 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x - dim/3,bn02.pos.y + dim*2/3]
 	button bn08 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x,bn02.pos.y + dim*2/3]
 	button bn09 "" width:(dim/3) height:(dim/3) pos:[bn02.pos.x + dim/3,bn02.pos.y + dim*2/3]
   
 	button bnRestart "Restart" width:dim align:#center
 	
 	label lbWins "   Wins:" align:#left
 	label lbLosts "Losts:   " align:#right offset:[0,-18]
 	spinner spWins "" fieldWidth:40 align:#left type:#integer enabled:false
 	spinner spLosts "" fieldWidth:40 align:#right type:#integer offset:[0,-22] enabled:false
 	
 	timer tmEnd interval:100 active:false
 	
 -- Functions
 ------------------------------------------
 	
 	fn updateUI =
 	(
 		fn getLabel lin row =
 		(
 			local label = ""
 			if valArr[lin][row] > 0 then label = "X"
 			if valArr[lin][row] < 0 then label = "O"
 			label
 		)
 		
 		bn01.enabled = (bn01.caption =  getLabel 1 1).count == 0
 		bn02.enabled = (bn02.caption =  getLabel 1 2).count == 0
 		bn03.enabled = (bn03.caption =  getLabel 1 3).count == 0
 		bn04.enabled = (bn04.caption =  getLabel 2 1).count == 0
 		bn05.enabled = (bn05.caption =  getLabel 2 2).count == 0
 		bn06.enabled = (bn06.caption =  getLabel 2 3).count == 0
 		bn07.enabled = (bn07.caption =  getLabel 3 1).count == 0
 		bn08.enabled = (bn08.caption =  getLabel 3 2).count == 0
 		bn09.enabled = (bn09.caption =  getLabel 3 3).count == 0
 		
 		if bnRestart.caption != "Restart" then bnNext.enabled = false
 	)
 	
 	fn testGameEnd vArr readOnly:false =
 	(
 		local test = 0
 		sequence = #()
 		for a = 1 to 3 do (
 			if vArr[a][1] == vArr[a][2] and vArr[a][1] == vArr[a][3] then
 			(
 				if vArr[a][1] > 0 then test = 1
 				if vArr[a][1] < 0 then test = -1
 				if vArr[a][1] != 0 then sequence = #([a,1],[a,2],[a,3])
 			)
 			
 			if vArr[1][a] == vArr[2][a] and vArr[1][a] == vArr[3][a] then
 			(
 				if vArr[1][a] > 0 then test = 1
 				if vArr[1][a] < 0 then test = -1
 				if vArr[1][a] != 0 then sequence = #([1,a],[2,a],[3,a])
 			)
 		) --end a loop
 		
 		if vArr[1][1] == vArr[2][2] and vArr[1][1] == vArr[3][3] then
 		(
 			if vArr[1][1] > 0 then test = 1
 			if vArr[1][1] < 0 then test = -1
 			if vArr[1][1] != 0 then sequence = #([1,1],[2,2],[3,3])
 		)
 		
 		if vArr[1][3] == vArr[2][2] and vArr[1][3] == vArr[3][1] then
 		(
 			if vArr[1][3] > 0 then test = 1
 			if vArr[1][3] < 0 then test = -1
 			if vArr[1][3] != 0 then sequence = #([1,3],[2,2],[3,1])
 		)
 		
 		if test == 0 then (
 			for lin = 1 to 3 do (
 				for row = 1 to 3 do (
 					if test == 0 and vArr[lin][row] == 0 then test = 2
 				)
 			)
 		)
 		
 		if not readOnly then (
 			case of
 			(
 				(test == 0):
 				(
 					bnRestart.caption = "Tie!"
 				)
 				(test == 1):
 				(
 					bnRestart.caption = "You Win!"
 					spWins.value += 1
 				)
 				(test == -1):
 				(
 					bnRestart.caption = "You Lose!"
 					spLosts.value += 1
 				)
 				defalut:
 				(
 					bnRestart.caption = "Restart"
 				)
 			)
 			if sequence.count == 3 then tmEnd.active = true
 		)
 		
 		test
 	)
 	
 	fn setMatrix lin row val force:false =
 	(
 		if (not bnNext.enabled or force) and bnRestart.caption == "Restart" then (
 			valArr[lin][row] = val
 			bnNext.enabled = not bnNext.enabled
 			testGameEnd valArr
 			updateUI()
 		)
 	)
 	
 	fn calculateMove =
 	(
 		local posibleMoves = #()
 		local corners = #([1,1],[1,3],[3,1],[3,3])
 		local sides = #([1,2],[2,1],[2,3],[3,2])
 		
 		-- [1] Win posibility test:
 		--------------------------------
 		for lin = 1 to 3 do (
 			for row = 1 to 3 do (
 				if valArr[lin][row] == 0 then (
 					valArr[lin][row] = -1
 					if testGameEnd valArr readOnly:true == -1 then (
 						append posibleMoves [lin,row]
 						format "Win
"
 					)
 					valArr[lin][row] = 0
 				)
 			)
 		)
 		
 		-- [2] Block posibility test:
 		---------------------------------
 		if posibleMoves.count == 0 then (
 			for lin = 1 to 3 do (
 				for row = 1 to 3 do (
 					if valArr[lin][row] == 0 then (
 						valArr[lin][row] = 1
 						if testGameEnd valArr readOnly:true == 1 then (
 							append posibleMoves [lin,row]
 							format "Block
"
 						)
 						valArr[lin][row] = 0
 					)
 				)
 			)
 		)
 		
 		-- [3] Sandwich posibility test:
 		-----------------------------------
 		if posibleMoves.count == 0 then (
 			if valArr[2][2] == -1 then (
 				for c = 1 to corners.count where valArr[corners[c].x][corners[c].y] == 1 do (
 					if valArr[corners[5 - c].x][corners[5 - c].y] == 1 do (
 						for s in sides where valArr[s.x][s.y] == 0 do (
 							append posibleMoves s
 							format "Sandwich
"
 						)
 					)
 				)
 			)
 		)
 		
 		-- [4] Fork posibility test:
 		--------------------------------
 		if posibleMoves.count == 0 then (
 			for lin = 1 to 3 do (
 				for row = 1 to 3 do (
 					if valArr[lin][row] == 0 then (
 						valArr[lin][row] = -1
 						local winCount = 0
 						for lin2 = 1 to 3 do (
 							for row2 = 1 to 3 do (
 								if valArr[lin2][row2] == 0 then (
 									valArr[lin2][row2] = -1
 									if testGameEnd valArr readOnly:true == -1 then (
 										winCount += 1
 									)
 									valArr[lin2][row2] = 0
 								)
 							)
 						)
 						if winCount > 1 then (
 							append posibleMoves [lin,row]
 							format "Fork posibility
"
 						)
 						valArr[lin][row] = 0
 					)
 				)
 			)
 		)
 		
 		-- [5] Block Fork posibility test:
 		----------------------------------------
 		if posibleMoves.count == 0 then (
 			for lin = 1 to 3 do (
 				for row = 1 to 3 do (
 					if valArr[lin][row] == 0 then (
 						valArr[lin][row] = 1
 						local winCount = 0
 						for lin2 = 1 to 3 do (
 							for row2 = 1 to 3 do (
 								if valArr[lin2][row2] == 0 then (
 									valArr[lin2][row2] = 1
 									if testGameEnd valArr readOnly:true == 1 then (
 										winCount += 1
 									)
 									valArr[lin2][row2] = 0
 								)
 							)
 						)
 						if winCount > 1 then (
 							append posibleMoves [lin,row]
 							format "Block Fork posibility
"
 						)
 						valArr[lin][row] = 0
 					)
 				)
 			)
 		)
 		
 		-- [6] Empty Centre posibility test:
 		--------------------------------------------
 		if posibleMoves.count == 0 then (
 			if valArr[2][2] == 0 then (
 				append posibleMoves [2,2]
 				format "Empty Centre
"
 			)
 		)
 		
 		-- [7] Opposite Corner posibility test:
 		------------------------------------------------
 		if posibleMoves.count == 0 then (
 			for a = 1 to sides.count do (
 				if valArr[sides[a].x][sides[a].y] == 1 then (
 					b = 5 - a
 					if valArr[sides[b].x][sides[b].y] == 0 then (
 						append posibleMoves sides[b]
 						format "Opposite Corner
"
 					)
 				)
 			)
 		)
 		
 		-- [8] Empty Corner posibility test:
 		-----------------------------------------
 		if posibleMoves.count == 0 then (
 			for i in corners do (
 				if valArr[i.x][i.y] == 0 then (
 					append posibleMoves i
 					format "Empty Corner
"
 				)
 			)
 		)
 		
 		-- [9] Empty Side posibility test:
 		--------------------------------------------
 		if posibleMoves.count == 0 then (
 			for i in sides do (
 				if valArr[i.x][i.y] == 0 then (
 					append posibleMoves i
 					format "Empty Side
"
 				)
 			)
 		)
 		
 		-- Make a move:
 		---------------------
 		local newMove = posibleMoves[random 1 posibleMoves.count]
 		setMatrix newMove.x newMove.y -1 force:true
 	)
 	
 	fn nextTurn =
 	(
 		calculateMove()
 		updateUI()
 	)
 	
 	fn restartGame =
 	(
 		tmEnd.active = true
 		valArr = #(#(0,0,0),#(0,0,0),#(0,0,0))
 		bnRestart.caption = "Restart"
 		bnNext.enabled = false
 		updateUI()
 	)
 	
 	fn showWinner  =
 	(
 		if bnRestart.caption == "You Win!" or bnRestart.caption == "You Lose!" then (
 			local char = if bnRestart.caption == "You Win!" then "X" else "O"
 			
 			for i in sequence do (
 				if i == [1,1] then bn01.caption =  if tickTest then char else ""
 				if i == [1,2] then bn02.caption =  if tickTest then char else ""
 				if i == [1,3] then bn03.caption =  if tickTest then char else ""
 				if i == [2,1] then bn04.caption =  if tickTest then char else ""
 				if i == [2,2] then bn05.caption =  if tickTest then char else ""
 				if i == [2,3] then bn06.caption =  if tickTest then char else ""
 				if i == [3,1] then bn07.caption =  if tickTest then char else ""
 				if i == [3,2] then bn08.caption =  if tickTest then char else ""
 				if i == [3,3] then bn09.caption =  if tickTest then char else ""
 			)
 			
 			tickTest = not tickTest
 		)
 	)
 	
 	fn openDialog =
 	(
 		createDialog TTTRollout width:(dim + 25)
 	)
 	  
 	fn init =
 	(
 		restartGame()
 	)
   
 	fn done =
 	(
 		-- cleanup code
 		gc light:true
 	)
   
 -- Event Handlers
 ------------------------------------------
 	  
 	on bn01 pressed do setMatrix 1 1 1
 	on bn02 pressed do setMatrix 1 2 1
 	on bn03 pressed do setMatrix 1 3 1
 	on bn04 pressed do setMatrix 2 1 1
 	on bn05 pressed do setMatrix 2 2 1
 	on bn06 pressed do setMatrix 2 3 1
 	on bn07 pressed do setMatrix 3 1 1
 	on bn08 pressed do setMatrix 3 2 1
 	on bn09 pressed do setMatrix 3 3 1
 		
 	on bnRestart pressed do restartGame()
 	on bnNext pressed do nextTurn()
 	
 	on tmEnd tick do showWinner()
 	
 	on TTTRollout open do init()
 	on TTTRollout close do done()
 
 ) -- end of rollout
 
 TTTRollout.openDialog()
 

hope this closes everything, so let me know if you find a way to win,
cause you shouldn’t have any way now…