• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 03:52
CEST 09:52
KST 16:52
  • 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
[ASL21] Ro4 Preview: On Course12Code S Season 1 - RO8 Preview7[ASL21] Ro8 Preview Pt2: Progenitors8Code S Season 1 - RO12 Group A: Rogue, Percival, Solar, Zoun13[ASL21] Ro8 Preview Pt1: Inheritors16
Community News
Weekly Cups (May 4-10): Clem, MaxPax, herO win1Maestros of The Game 2 announcement and schedule !10Weekly Cups (April 27-May 4): Clem takes triple0RSL Revival: Season 5 - Qualifiers and Main Event12Code S Season 1 (2026) - RO12 Results1
StarCraft 2
General
MaNa leaves Team Liquid Weekly Cups (May 4-10): Clem, MaxPax, herO win Code S Season 1 - RO8 Preview Behind the Blue - Team Liquid History Book Weekly Cups (April 27-May 4): Clem takes triple
Tourneys
2026 GSL Season 2 Qualifiers Maestros of The Game 2 announcement and schedule ! SC2 INu's Battles#16 <BO.9> Master Swan Open (Global Bronze-Master 2) GSL Code S Season 1 (2026)
Strategy
Custom Maps
[D]RTS in all its shapes and glory <3 [A] Nemrods 1/4 players
External Content
Mutation # 525 Wheel of Misfortune The PondCast: SC2 News & Results Mutation # 524 Death and Taxes Mutation # 523 Firewall
Brood War
General
BW General Discussion Pros React To: Leta vs Tulbo (ASL S21, Ro.8) ASL Tickets to Live Event Finals? [ASL21] Ro4 Preview: On Course Flashes ASL S21 Ro8 Review
Tourneys
[ASL21] Semifinals B [ASL21] Semifinals A [Megathread] Daily Proleagues [BSL22] RO16 Group Stage - 02 - 10 May
Strategy
[G] Hydra ZvZ: An Introduction Simple Questions, Simple Answers Fighting Spirit mining rates Muta micro map competition
Other Games
General Games
Starcraft Tabletop Miniature Game Warcraft III: The Frozen Throne Stormgate/Frost Giant Megathread PC Games Sales Thread Path of Exile
Dota 2
The Story of Wings Gaming
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Deck construction bug Heroes of StarCraft mini-set
TL Mafia
Vanilla Mini Mafia Mafia Game Mode Feedback/Ideas TL Mafia Community Thread Five o'clock TL Mafia
Community
General
US Politics Mega-thread UK Politics Mega-thread Russo-Ukrainian War Thread YouTube Thread European Politico-economics QA Mega-thread
Fan Clubs
The IdrA Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [Req][Books] Good Fantasy/SciFi books
Sports
2024 - 2026 Football Thread McBoner: A hockey love story Formula 1 Discussion
World Cup 2022
Tech Support
streaming software Strange computer issues (software) [G] How to Block Livestream Ads
TL Community
The Automated Ban List
Blogs
How EEG Data Can Predict Gam…
TrAiDoS
ramps on octagon
StaticNine
Funny Nicknames
LUCKY_NOOB
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1564 users

TicTacToe AI

Blogs > micronesia
Post a Reply
micronesia
Profile Blog Joined July 2006
United States24772 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 Kong9176 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 States24772 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 States24772 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 States24772 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 2h 8m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 143
ProTech140
StarCraft: Brood War
Britney 27973
GuemChi 3761
Killer 402
HiyA 117
soO 54
NotJumperer 25
yabsab 20
NaDa 18
Bale 17
Noble 15
[ Show more ]
ajuk12(nOOB) 13
Sharp 13
JulyZerg 12
ZergMaN 6
League of Legends
JimRising 592
Counter-Strike
Stewie2K784
olofmeister570
Other Games
summit1g11514
ceh9589
C9.Mang0463
monkeys_forever332
Organizations
Counter-Strike
PGL21408
Other Games
gamesdonequick680
StarCraft: Brood War
lovetv 20
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
[ Show 15 non-featured ]
StarCraft 2
• LUISG 11
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• iopq 2
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Nemesis2047
• Lourlo1312
• Stunt686
Upcoming Events
CranKy Ducklings
2h 8m
Afreeca Starleague
2h 8m
Light vs Flash
INu's Battles
3h 8m
ByuN vs herO
PiGosaur Cup
16h 8m
Replay Cast
1d 1h
Replay Cast
1d 16h
The PondCast
2 days
OSC
2 days
Replay Cast
2 days
RSL Revival
3 days
[ Show More ]
OSC
3 days
Korean StarCraft League
3 days
RSL Revival
4 days
BSL
4 days
GSL
5 days
Cure vs herO
SHIN vs Maru
BSL
5 days
Replay Cast
6 days
Replay Cast
6 days
Liquipedia Results

Completed

Proleague 2026-05-11
WardiTV TLMC #16
Nations Cup 2026

Ongoing

BSL Season 22
ASL Season 21
IPSL Spring 2026
KCM Race Survival 2026 Season 2
Acropolis #4
KK 2v2 League Season 1
BSL 22 Non-Korean Championship
SCTL 2026 Spring
RSL Revival: Season 5
2026 GSL S1
Asian Champions League 2026
IEM Atlanta 2026
PGL Astana 2026
BLAST Rivals Spring 2026
IEM Rio 2026
PGL Bucharest 2026
Stake Ranked Episode 1
BLAST Open Spring 2026
ESL Pro League S23 Finals
ESL Pro League S23 Stage 1&2

Upcoming

Escore Tournament S2: W7
YSL S3
Escore Tournament S2: W8
CSLAN 4
Kung Fu Cup 2026 Grand Finals
HSC XXIX
uThermal 2v2 2026 Main Event
Maestros of the Game 2
2026 GSL S2
BLAST Bounty Summer 2026: Closed Qualifier
Stake Ranked Episode 3
XSE Pro League 2026
IEM Cologne Major 2026
Stake Ranked Episode 2
CS Asia Championships 2026
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.