Tic Tac Toe Artificial Intelligence

Read all posts about "" game

During these days I played a bit with Artificial Intelligence for a project I am working on (big news on the horizon) and I’m coming with a brief introduction to the simplest game you can use to test artificial intelligence. Tic Tac Toe.

It’s a pencil-and-paper game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. (source: Wikipedia).

But most of all, it’s a good playground to apply artificial intelligence for four reasons:

It’s a perfect information game: all players know all moves that have taken place.

It’s a sequential game: when a player moves, the other player waits. And have the waiting player see the moves of the playing one.

It’s a zero sum game: if one player wins, the ohter loses. No cooperation.

It’s a non-random game: there isn’t any randomizing element such as dices, dealing of cards, and so on. Non-random games are pure strategy.

How many board configurations?

Now, we need to know how many boards configurations can exist in a Tic Tac Toe game. We’ll do it using php. We’ll code an empty board like a string with nine points (.........). Every point represents an empty cell. Then, with a recursive function, we’ll generate all possible board combinations, assuming the first player puts an X and the second player uses the O.

Here it is the script:

 $values){
	echo "

Combinations with ".trim(9-$empty_spots)." symbol(s): $values

"; } echo "

Elapsed time: ".trim($end-$start)."

"; ?>

And the result is:

Combinations with 1 symbol(s): 9 – easy to see, in an empty board you can place an X in any of the nine spots

Combinations with 2 symbol(s): 72 – for each of the 9 different combinations with one symbol, you can place a O in any of the remaining eight spots. 9*8 =72.

Combinations with 3 symbol(s): 504 – for each of the 72 previous combinations, you can place an X in any of the remaining seven spots. 72*7 = 504.

Combinations with 4 symbol(s): 3024 – 504*6

Combinations with 5 symbol(s): 15120 – 3024*5

Combinations with 6 symbol(s): 60480 – 15120*4

Combinations with 7 symbol(s): 181440 – 60480*3

Combinations with 8 symbol(s): 362880 – 181440*2

Combinations with 9 symbol(s): 362880 – 362880*1. Same number as the combinations with 8 symbols, because when there are 8 symbols in game, you can only place an O in just one spot.

Elapsed time: 6.0569689273834 – six seconds to calculate 986409 different combinations. So the total possible board configurations are 986410, including the empty board.

According to these results, we can say the number of possible combinations in a board with n symbols is 9!/(9-n)!.

How many REAL board configurations?

Obviously there’s something wrong with this script because it does not consider when a player wins. If a player wins, the game is over and there are no more moves. So a lot of board configurations are impossible to reach.

So let’s modify a bit the script to check for victories and the number of necessary moves to win:

 $values){
	echo "

Combinations with ".trim(9-$empty_spots)." symbol(s): $values

"; } for($x=5;$x<=9;$x++){ echo "

Wins in ".$x." moves: $wins[$x]

"; } echo "

Elapsed time: ".trim($end-$start)."

"; ?>

And the result is:

Combinations with 1 symbol(s): 9

Combinations with 2 symbol(s): 72

Combinations with 3 symbol(s): 504

Combinations with 4 symbol(s): 3024

Combinations with 5 symbol(s): 15120

Combinations with 6 symbol(s): 54720

Combinations with 7 symbol(s): 148176

Combinations with 8 symbol(s): 200448

Combinations with 9 symbol(s): 127872

Wins in 5 moves: 1440

Wins in 6 moves: 5328

Wins in 7 moves: 47952

Wins in 8 moves: 72576

Wins in 9 moves: 81792

Elapsed time: 4.7160170078278 – Less than five seconds to generate all possible Tic Tac Toe combinations.

This means X will win 1440+47952+81792 = 131184 times while O will win 5328+72576 = 77904 times. The first player has more chances to win.

How can we determine the drawn games? They are represented by the number of possible boards with nine symbols (127872) minus the number of wins at the 9th move (81792) = 46080 draws.

According to these results, next time we’ll introduce an algorithm to make the computer play Tic Tac Toe.

Meanwhile enjoy these results.

PS: anyone willing to translate this into AS3 or other languages?

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers