• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 15:59
CEST 21:59
KST 04:59
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11[ASL22] Ro16 Preview: Holy Diver5[ASL22] Ro16 Preview: Rough Waters10
Community News
Weekly Cups (October 5-11): Farewell to 5.0.161Rollback Netcode in Brood War845.0.17 Patch Notes - October 7, 202622Weekly Cups Results (Sep 28-Oct 4)0SC4ALL: II SC2 Complete Invited Player Lineup10
StarCraft 2
General
Weekly Cups (October 5-11): Farewell to 5.0.16 StarCraft open world shooter announced at BlizzCon 5.0.17 Patch Notes - October 7, 2026 ESL Pro Tour for SC2 discontinued [Old] StarCraft 3 Reportedly in Development
Tourneys
$3,500 WardiTV Not-Summer Championship Stellar Fest TWO the Moon (Dec 16-20) ISSL (IntoTheTV x SOOP SC2 League): Premier RSL 2026 Offline Finals LCQ Sign-Ups ScienceCraft (October 24-25) - Live Event
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[A] Nemrods 1/4 players [M] (2) Sweltering Sands [M] (2) Frigid Storage
External Content
The PondCast: SC2 News & Results Mutation # 547 Temple Of Terror Mutation # 546 Catch the Train Mutation # 545 And Drops and Rifts
Brood War
General
BW General Discussion BSL23 Confirmations Starts on New BSL Portal ASL FINALS HYPE VIDEO 2X ASL22 General Discussion Sagi.gg Launcher Released
Tourneys
ASL 22 Finals [Megathread] Daily Proleagues [ASL22] Semifinal A [ASL22] Semifinal B
Strategy
Simple Questions, Simple Answers Cliff Jump Revisited (1 in a 1000 strategy) Replay Review Process - What do you do?
Other Games
General Games
Dawn of War IV Nintendo Switch Thread Stormgate/Frost Giant Megathread General RTS Discussion Thread Warcraft III: The Frozen Throne
Dota 2
Dota 2 Champions League Season 3 Begins April 25!
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
Russo-Ukrainian War Thread US Politics Mega-thread Things Aren’t Peaceful in Palestine Canadian Politics Mega-thread Artificial Intelligence Thread
Fan Clubs
Serral Fan Club
Media & Entertainment
[Manga] One Piece Movie Discussion! Diablo Animated Series on Netflix
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023 MLB/Baseball 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Recent Gifted Posts
Blogs
The Link Between Gaming and …
TrAiDoS
[ASL22] Ro4 Day1 Ticket Giv…
bITt.mAN
38 yo Retired SWE loo…
PurE)Rabbit-SF
Can Bots Beat Pros?? Starcr…
namkraft
[meme] I finally understa…
LUCKY_NOOB
Customize Sidebar...

Website Feedback

Closed Threads



Active: 11804 users

TicTacToe AI

Blogs > micronesia
Post a Reply
micronesia
Profile Blog Joined July 2006
United States24805 Posts
Last Edited: 2015-01-11 05:57:53
January 11 2015 05:55 GMT
#1
Background: I enjoy computer programming but have not formally studied it since high school. In recent years, I have been on-and-off dabbling with python because I find it fun and easy to code with.

Brief: I had some spare time this past week during vacation/travel so I decided to play around some more with Python. Typically my code is pretty inefficient and stupidly put together, but usually it gets the job done! After warming up by making a couple of programs I was pretty sure I knew how to do + Show Spoiler +
(one that generates a histogram by flipping two 'dice' many times, another that simulates heads up texas holdem poker and determines the chances of each starting hand winning through many runs)
I decided I should try to work on something I don't know how to do. Then it occurred to me: something I was previously interested in but never figured out was how to program a board game ai that looks at all possible moves and chooses the best one.

The classic example of this is chess, but I decided to stick to something much simpler for practical reasons. In fact, I decided to write an ai for a game that can quickly be solved for all moves, even when using my crappy netbook (which is what I was using on my vacation).

I knew how to make player vs player TicTacToe (with both players using the same computer, taking turns), and knew how to code an ai by manually providing logic to the computer. What I wasn't sure how to do was show the computer how to read ahead through every move and identify the move that is 100% the best move (this doesn't usually work in more complex games like chess because you can't read through every line to a win or loss; you need to use more subjective methods of evaluation for assigning scores to board states). After talking to someone knowledgeable at a high level about how the process works, and playing around (and looking at the pictures (but not the code) here for inspiration), I came up with a program that seems to be a perfect ai for TicTacToe. It took a fair amount of adjustments to get the computer to not stupidly suicide. Here is the code:

+ Show Spoiler [My Code] +
#TIC TAC TOE with perfect brute force AI in Python 3
import time

board = [' ',' ',' ',' ',' ',' ',' ',' ',' ',' '] #index 1-9 represent board,
#according to layout of keys on numpad; 0 ignored

def printBoard(board): #prints a normal looking tic tac toe board
print('\n ', board[7], ' | ', board[8], ' | ', board[9])
print('------------------')
print(' ', board[4], ' | ', board[5], ' | ', board[6])
print('------------------')
print(' ', board[1], ' | ', board[2], ' | ', board[3])

def choosePlayers(): #identifies which players are human and which are comps (ai)
p1ok = False
while p1ok == False:
p1 = input('Is player 1 a human (h) or computer (c)?')
if p1 == 'h' or p1 == 'c':
p1ok = True
else:
print('Please enter a valid choice (h or c)')
p2ok = False
while p2ok == False:
p2 = input('Is player 2 a human (h) or computer (c)?')
if p2 == 'h' or p2 == 'c':
p2ok = True
else:
print('Please enter a valid choice (h or c)')
return (p1,p2)

def humanTurn(letter, board): #retrieves move from human player's input and changes the board accordingly
printBoard(board)
moveOk = False
while moveOk == False:
if letter == 'X':
print('Player 1,', end=' ')
elif letter == 'O':
print('Player 2,', end=' ')
move = input('enter the numpad position where you would like to move:')
if move not in '123456789':
print('Please enter a number (1-9)')
elif board[int(move)] != ' ':
print('That space is already occupied')
else:
board[int(move)] = letter
moveOk = True

def compTurn(letter, board): #retrieves move from computer and changes board accordingly
printBoard(board)
(move,score) = compMove(letter, board)
board[int(move)] = letter
time.sleep(1) #pause 1 second
return

def compMove(letter, board): #returns highest scoring move for whoever's turn it is;
#when investigating a move that doesn't end the game, the "score" of the move is reversed;
#since a high scoring move for your opponent is actually a low scoring move for you
#(see REVERSAL comments below)
if letter == 'X':
oppon = 'O'
elif letter == 'O':
oppon = 'X'
moveList = makeList(board)
moveListScore = []
for i in range(len(moveList)):
moveListScore.append(' ')
for move in moveList:
testBoard = board[:]
testBoard[int(move)]=letter
if checkForWin(testBoard) == letter:
moveListScore[moveList.index(move)] = '9' #9 means instant win
elif checkForTie(testBoard) == 'T':
moveListScore[moveList.index(move)] = '5' #5 means instant tie
elif checkForWin(testBoard) == oppon:
moveListScore[moveList.index(move)] = '1' #1 means instant loss (needed?)
else:
theNextMove = compMove(oppon,testBoard)[1]
if theNextMove == '9': #REVERSAL
theNextMove = '1'
elif theNextMove == '1': #OPPOSING REVERSAL
theNextMove = '9'
moveListScore[moveList.index(move)] = theNextMove
for score in moveListScore: #remainder of function serves to
#pull the highest scoring move available
if score == '9':
return (moveList[moveListScore.index(score)],'9')
for score in moveListScore:
if score == '5':
return (moveList[moveListScore.index(score)],'5')
for score in moveListScore:
if score == '1':
return (moveList[moveListScore.index(score)],'1')

def makeList(board): #creates a string of all viable moves, e.g., '1346'
myString = ''
for i in range(1,10):
if board[i]==' ':
myString += str(i)
return myString

def checkForWin(board): #searches for three in a row
winner = 'W'
if checkAllThree(1,2,3,board):
winner = board[1]
if checkAllThree(4,5,6,board):
winner = board[4]
if checkAllThree(7,8,9,board):
winner = board[7]
if checkAllThree(1,4,7,board):
winner = board[1]
if checkAllThree(2,5,8,board):
winner = board[2]
if checkAllThree(3,6,9,board):
winner = board[3]
if checkAllThree(1,5,9,board):
winner = board[1]
if checkAllThree(7,5,3,board):
winner = board[7]
return winner #W means no winner currently, X or O returned says which player wins;
#X is player 1; O is player 2

def checkAllThree(num1, num2, num3, board): #returns true if all three spaces are X or
#all three spaces are O
if board[num1] == board[num2]:
if board[num1] == board[num3]:
if board[num1] == 'X' or board[num1] == 'O':
return True
return False

def checkForTie(board): #tie if all spaces are filled; must always check for win before checking for;
#tie since a winning board can also be filled
tie = True
for i in range(1,10):
if board[i] == ' ':
tie = False
if tie:
return 'T'
else:
return 'W' #W means no tie currently, T means the game is a tie

#MAIN
(player1Type, player2Type) = choosePlayers() #player1Type is an h or a c; same for player2Type
gameOver = 'W' #W means no winner, otherwise X or O
p1Turn = True
while gameOver == 'W': #game loop
if p1Turn:
if player1Type == 'h':
humanTurn('X',board)
elif player1Type == 'c':
compTurn('X', board)
if not p1Turn: #p2 turn
if player2Type == 'h':
humanTurn('O', board)
elif player2Type == 'c':
compTurn('O', board)
p1Turn = not p1Turn
if gameOver == 'W':
gameOver = checkForWin(board)
if gameOver == 'W':
gameOver = checkForTie(board)
if gameOver == 'X':
printBoard(board)
input('Player 1 is the winner! Press enter to exit')
if gameOver == 'O':
printBoard(board)
input('Player 2 is the winner! Press enter to exit')
if gameOver == 'T':
printBoard(board)
input('The game is a tie! Press enter to exit')

I wrote the code in python 2 and converted it over to 3 so there could possibly be some weirdness . Also, I added some linebreaks to allow the code to fit into TL better

If you have python3 give it a go and let me know what you think. For anyone who hasn't done this before and wants to know how the computer chooses the best move, I'll try to explain it (in an attempt to improve my own understanding):

  1. The computer makes a list of each viable move currently (any empty space on the board)
  2. The computer identifies which moves on the list result in a win for the computer (high scoring move), and which moves result in a tie (medium scoring move).
  3. Any remaining moves do not end the game. To figure out what score to assign to these moves, the computer then 'pretends' to make these moves that do not end the game and then investigates what moves the opponent can make next turn.
  4. Recursively, the computer keeps calling the same function, advancing one move ahead at a time. Eventually, the computer reads through to the last possible move of each line (at most, a game consists of 9 consecutive moves)
  5. For each of the mapped and scored moves, the computer assumes the best move will be chosen (if it's the computer's turn, the computer chooses the best move, e.g., a winning move; if it's the opponents move, we assume the opponent will try to make the winning move for them <a low scoring move for the computer>)
  6. For each move that wasn't game-ending, a score is assigned equal to the worst case scenario for the player choosing the move, assuming ideal play from both players.


Steps 5-6 are where I was having difficulty. This whole procedure is called MiniMax, which involves assuming your opponent's best moves, while high-scoring for them, are conversely low-scoring for you. Trying to handle the 'opposing posture' of each player in the algorithm was proving challenging until I eventually got something that worked. I knew things were good when I played a quick game of TicTacToe vs the computer and lost!

Thoughts on introduction to minimax and AI? Thoughts on my code? If you think the above is written poorly, you should see some of my other projects!

*****
ModeratorThere are animal crackers for people and there are people crackers for animals.
itsjustatank
Profile Blog Joined November 2010
Hong Kong9179 Posts
January 11 2015 06:02 GMT
#2
Photographer"nosotros estamos backamos" - setsuko
ShadowDrgn
Profile Blog Joined July 2007
United States2497 Posts
January 11 2015 07:20 GMT
#3
The actual code for a basic chess AI is even simpler than your tic-tac-toe AI, although an ASCII terminal representation of a chess board would be a bit more complicated.

As you seem to have discovered, the simplistic method of making a minimax AI requires you to write a function to calculate the value of a board state and then recursively call that function for every possible move down to as many levels as you want your AI to look ahead. For example with chess, you can assign values to each piece (pawn 1, knight/bishop 3, rook 5, queen 9) and then calculate the value of the board based on which pieces you have and which your opponent still has with every move. There's no need to do any complicated 'reversal' procedure like with your tic-tac-toe AI. For example, if you can take a pawn with a move near the start of the game, the board will be +1. If your opponent's next move can take your queen, that board will be -8.

A very easy AI can be limited to looking ahead 1 move; a very hard AI can look ahead 6 moves or whatever. You could also build in the possibility of the AI choosing a non-optimal move to keep things interesting. A really good chess AI would want to evaluate boards considering the position of the pieces and also have special cases built-in for openings and end-game situations, but the super simple version is a few lines of code and works.
Of course, you only live one life, and you make all your mistakes, and learn what not to do, and that’s the end of you.
nunez
Profile Blog Joined February 2011
Norway4003 Posts
Last Edited: 2015-01-11 07:26:31
January 11 2015 07:21 GMT
#4
really cool!
i managed to tie it on the first and second round.

i'm not very familiar with python yet (c++ is my mother tongue),
but i managed to read your code no problem,
and i got a decent grasp of the minimax algorithm (have not seen it before)

5 stars.

edit:
what program do you use to write code?
conspired against by a confederacy of dunces.
micronesia
Profile Blog Joined July 2006
United States24805 Posts
January 11 2015 14:22 GMT
#5
ShadowDrgn, ah, thank you for the perspective. Hopefully I will do more on this topic.

nunez: I use notepad++ for python. And yea, I like python because of how easy to read and write it is.
ModeratorThere are animal crackers for people and there are people crackers for animals.
Letila
Profile Joined July 2012
Australia11 Posts
Last Edited: 2015-01-11 23:36:37
January 11 2015 23:30 GMT
#6
I think you don't actually need to write a program like this for tic tac toe since its a solved problem.

But it's good practice I guess.

I think the algorithm is something like this:

if you can win this round, place in the winning spot
if opponent can win next round, block opponents spot

if middle tile is free, put in middle tile.
if corner is free, put in corner
else put it in an edge

----
I think this will never lose, from memory, haven't really thought it through though
micronesia
Profile Blog Joined July 2006
United States24805 Posts
January 11 2015 23:32 GMT
#7
On January 12 2015 08:30 Letila wrote:
I think you don't actually need to write a program like this for tic tac toe since its a solved problem.

But it's good practice I guess.

Yes I intentionally chose a simple game for learning purposes.

I've since created a 4x4 version of connect 4 which seems to be significantly more complicated... my algorithm is able to solve it but it took a lot longer.

I've slightly improved the algorithm but stopping searching on a given branch once a limiting move has been found, but a factor of 10 improvement isn't enough to tackle a larger connect 4 board yet...
ModeratorThere are animal crackers for people and there are people crackers for animals.
Letila
Profile Joined July 2012
Australia11 Posts
January 11 2015 23:38 GMT
#8
you might be interested in getting an AI book.

I have one by russell & norvig in my room. I think it's mostly a book of techniques and algorithms (rather than ideas).
micronesia
Profile Blog Joined July 2006
United States24805 Posts
January 11 2015 23:48 GMT
#9
An edx course on ai is starting next month... maybe I will try to do that. I don't think I've studied a couple of the prerequisites for computer programming, but it's in python so I'll figure it out!
ModeratorThere are animal crackers for people and there are people crackers for animals.
Gowerly
Profile Blog Joined July 2011
United Kingdom916 Posts
January 12 2015 10:24 GMT
#10
Something that helps me when thinking about how to make an AI is making the problem in a different way, but one that works out the same.

Let's play a new game.
We have the numbers 1 to 9.
We take it in turns to pick numbers.
Once a number is picked it cannot be picked again.
If, at any point, any one of us has three numbers that add to 15, they win.

As an aside, this is a fun game to play with people who like Tic Tac Toe, as you'll win a few rounds before anyone thinks that it is the same game.

Is it the same game? Of course. The 3x3 Magic Square is as follows:


2 | 9 | 4
---------
7 | 5 | 3
---------
6 | 1 | 8

All horizontal, diagonal and vertical lines add up to 15.

I have found that making an AI to play this game and then simply rendering the game state of it in the magic square allows for simpler deduction of the moves. The AI states are, for me, easier to follow. Allows for better state choosing:
- Look at opponent, have they won?
- Can I win next turn? Look at my numbers. Do I have 2 in a way that I can take a third to make 15?
- If so, take the number if not taken.
- If not, pick 2 of their numbers. Is there a third that will make their total 15?
- If so, take it if not taken already. (Repeat for all combinations of numbers they have)
- Failing that, look at a single number I have. Remove it from 15 and look at what 2 numbers make up the remaining (e.g. I've got 8 taken, I can break the remainder to 6 + 1, 5 + 2, 4 + 3)
- Weight extra for numbers where both are still available (not really worth taking 4 if 3 is gone).
- Repeat for all numbers I have and pick number with the highest total weight.

For me, doing it with numbers removes a lot of the tricky string manipulation.

However, what you have does may the game optimally and that's pretty much the end goal of something like this! Great work!
I will reduce you to a series of numbers.
Jukado
Profile Blog Joined May 2011
805 Posts
January 12 2015 16:29 GMT
#11
I followed these tutorials:
http://inventwithpython.com/chapters/
http://inventwithpython.com/pygame/chapters/

The first one has tic tac toe with AI:
http://inventwithpython.com/chapter10.html

The second one has Connect 4 on a 7x6 board with an AI that...
Quote:
'It simulates every possible move it can make, then simulates every possible move the human player can make in response to each of those moves, and then simulates every possible move it can make in response to that, and then simulates every possible move the human player could make in response to each of those moves! After all that thinking, the computer determines which move is most likely to lead to it winning.'

The Connect 4 is lumped with 3 other games in the final chapter (Chapter 10 - Four Extra Games). Its half way down this page:
http://inventwithpython.com/pygame/chapter10.html

Might enjoy that micronesia.
Star Tale Public Domain project. Maps: (2)Gates Of Memphis, (2)Marshmallow Toast, (4)Bubbles, (4)Clay Fields, (6)Numbskull Desert. Also the Vaylu Public Domain Tileset. Also Ramp Palettes, Brood War guides and some fun stuff. Links in my profile
Please log in or register to reply.
Live Events Refresh
Next event in 4h 31m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
mouzHeroMarine 434
ProTech159
UpATreeSC 97
JuggernautJason50
Railgan 25
StarCraft: Brood War
actioN 287
firebathero 130
Dewaltoss 116
Zeus 66
sSak 43
Light 36
Sexy 28
PianO 16
HiyA 15
Sharp 10
[ Show more ]
ajuk12(nOOB) 8
Sacsri 5
Dota 2
420jenkins425
Pyrionflax158
Counter-Strike
fl0m1461
Heroes of the Storm
Grubby4095
MindelVK20
Other Games
FrodaN769
Beastyqt570
B2W.Neo481
Liquid`Hasu254
IndyStarCraft 140
C9.Mang0117
RotterdaM104
QueenE75
[ Show 16 non-featured ]
StarCraft 2
• Adnapsc2 3
• niya90s 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• ChaeLyn 6
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• C_a_k_e 2870
• masondota21383
Other Games
• imaqtpie1190
• Shiphtur805
• WagamamaTV307
Upcoming Events
PiGosaur Cup
4h 31m
Kung Fu Cup
15h 1m
The PondCast
1d 14h
Online Event
2 days
Korean StarCraft League
3 days
Afreeca Starleague
3 days
Rush vs Soulkey
CranKy Ducklings
3 days
BSL Open Qualifier
3 days
Sparkling Tuna Cup
4 days
IPSL
4 days
[ Show More ]
BSL Open Qualifier
4 days
WardiTV Weekly
5 days
IntoTheTV X SOOP
6 days
Liquipedia Results

Completed

Proleague 2026-10-12
Blizzard Classic Cup 2026
Copium Cup

Ongoing

ASL Season 22
Super Anchor Qualifying S3
Acropolis #5
HCC Season 3
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026
Esports World Cup 2026
BLAST Bounty Summer 2026

Upcoming

Acropolis #5 - GSC
BSL Season 23
SC4ALL II: Brood War
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
eXTREMESLAND 2026
PGL Major Singapore 2026
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
Stake Ranked Episode 5
PGL Masters Bucharest 2026
1win Private Club #2
Thunderpick World Champ. '26
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.