• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 15:08
CEST 21:08
KST 04:08
  • 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
Serral wins HomeStory Cup 2915Serral wins Maestros of the Game 243ByuL, and the Limitations of Standard Play3Team Liquid Map Contest #22: Results and Winners7Code S Season 2 (2026): RO4 and Finals Preview12
Community News
GSTL Returns in 2026!21Weekly Cups (Aug 3-9): Protoss get shut out7RSL goes to London! 2026 Offline Finals Nov 21-2212Weekly Cups (July 27-Aug 2): SHIN's big week0SC4ALL II: Brood War - $2500 - Dec 5-611
StarCraft 2
General
GSTL Returns in 2026! SC4ALL: II Talent Announcement! Balance hotfix patch 5.0.16b (July 16) Protoss AoE skill expression Weekly Cups (Aug 3-9): Protoss get shut out
Tourneys
PIG STY FESTIVAL 8.0! (13 - 23 August) Sea Duckling Open (Global, Bronze-Diamond) 2026 KungFu Cup Announcement Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22
Strategy
[G] Having the right mentality to improve
Custom Maps
Nexus Wars 2021 GUIDE [M] (2) Industrial Park
External Content
Mutation # 538 Media Blackout The PondCast: SC2 News & Results Mutation # 537 Hostile Territory Mutation # 536 Railroad Switch
Brood War
General
BW General Discussion BGH Auto Balance -> http://bghmmr.eu/ ASL22 General Discussion Best Games Kespa era StarCraft 64 is coming to Philly at SC4ALL II
Tourneys
Escore Tournament - Season 3 Small VOD Thread 2.0 [Megathread] Daily Proleagues SC4ALL II: Brood War - $2500 - Dec 5-6
Strategy
Odyssey Mineral Stack Saturation Fighting Spirit mining rates Any training maps people recommend? Simple Questions, Simple Answers
Other Games
General Games
Nintendo Switch Thread Anyone here play Quakeworld back in the day? Stormgate/Frost Giant Megathread EVE Corporation General RTS Discussion Thread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
[TL LoL EUW IHs] Teemo shall perish TSM pausing esports and CLG Dead
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Power Rank TL Mafia Community Thread NeO.D_StephenKing vs This Guy From 1 Million Dance
Community
General
US Politics Mega-thread European Politico-economics QA Mega-thread Russo-Ukrainian War Thread Artificial Intelligence Thread The Letting Off Steam Thread
Fan Clubs
MarineLorD Fan Club The ShoWTimE Fan Club The herO Fan Club!
Media & Entertainment
Movie Discussion! Anime Discussion Thread Series you have seen recently... [Req][Books] Good Fantasy/SciFi books
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023 NBA General Discussion Formula 1 Discussion MLB/Baseball 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread Simple Questions Simple Answers FPS when play League Of Legend on laptop
TL Community
The Automated Ban List Northern Ireland Global Starcraft
Blogs
LOCKPICKING NOOB
LUCKY_NOOB
Chinese Gen Z: Between Dream…
TrAiDoS
Cathedral Of CS And NY pizza a…
FuDDx
Please support my new stand…
Peanutsc
Hello guys!
LIN1s
Customize Sidebar...

Website Feedback

Closed Threads



Active: 2957 users

TicTacToe AI

Blogs > micronesia
Post a Reply
micronesia
Profile Blog Joined July 2006
United States24788 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 States24788 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 States24788 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 States24788 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
Big Brain Bouts
16:00
#126
Nicoract vs Neeb
TriGGeR vs ShoWTimE
RotterdaM807
IndyStarCraft 187
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 807
PiGStarcraft520
IndyStarCraft 187
ProTech71
UpATreeSC 52
ZombieGrub44
MindelVK 24
EmSc Tv 12
StarCraft: Brood War
Britney 18974
actioN 328
Soma 318
Rush 232
Mong 67
ZZZero.O 54
Terrorterran 26
Rock 18
Dota 2
qojqva3696
XaKoH 387
BananaSlamJamma301
canceldota56
Counter-Strike
fl0m4326
Other Games
Grubby1903
shahzam372
B2W.Neo300
Liquid`VortiX219
ArmadaUGS124
Livibee90
C9.Mang088
KnowMe60
QueenE60
Mew2King56
Trikslyr37
Organizations
StarCraft 2
EmSc Tv 12
EmSc2Tv 12
[ Show 14 non-featured ]
StarCraft 2
• StrangeGG 67
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Nemesis1684
• Jankos1494
• TFBlade795
Other Games
• imaqtpie1366
• Shiphtur395
Upcoming Events
CranKy Ducklings
14h 52m
PiG Sty Festival
16h 52m
herO vs Krystianer
Solar vs Cure
IPSL
20h 52m
Sparkling Tuna Cup
1d 14h
PiG Sty Festival
1d 16h
Maru vs Shameless
Reynor vs TriGGeR
IPSL
1d 20h
OSC
2 days
Afreeca Starleague
2 days
Rush vs Hm
Bisu vs Shuttle
WardiTV Weekly
2 days
The Patches Monday
2 days
[ Show More ]
Afreeca Starleague
3 days
Sharp vs Shinee
Action vs Shine
PiGosaur Cup
4 days
Replay Cast
4 days
Afreeca Starleague
4 days
BeSt vs Paralyze
Jaedong vs Speed
Kung Fu Cup
4 days
The PondCast
5 days
KCM Race Survival
5 days
Replay Cast
6 days
PiG Sty Festival
6 days
Liquipedia Results

Completed

Proleague 2026-08-13
CranK Gathers Season 4: BW vs SC2 Team League
Eternal Conflict S2 Finale

Ongoing

KCM Race Survival 2026 Season 3
K-JUNGMAN
Acropolis #5
Escore Tournament S3: W7
RSL Revival: Season 6
PiG Sty Festival 8.0
Esports World Cup 2026
Esports World Cup 2026: LCQ
BLAST Bounty Summer 2026
BLAST Bounty Summer Qual
Stake Ranked Episode 3
XSE Pro League 2026
IEM Cologne Major 2026

Upcoming

CSLAN 4
ASL Season 22
Escore Tournament S3: W8
Acropolis #5 - TRS
Blizzard Classic Cup 2026
Acropolis #5 - GSA
Acropolis #5 - GSB
HSC XXX
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
Big Dog Cup 2026 Div 1
META DYMY #4
Stake Ranked Episode 5
PGL Masters Bucharest 2026
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #5
BLAST Open Fall 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.