• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 09:11
CET 15:11
KST 23:11
  • 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
Intel X Team Liquid Seoul event: Showmatches and Meet the Pros10[ASL20] Finals Preview: Arrival13TL.net Map Contest #21: Voting12[ASL20] Ro4 Preview: Descent11Team TLMC #5: Winners Announced!3
Community News
$5,000+ WardiTV 2025 Championship2[BSL21] RO32 Group Stage1Weekly Cups (Oct 26-Nov 2): Liquid, Clem, Solar win; LAN in Philly2Weekly Cups (Oct 20-26): MaxPax, Clem, Creator win82025 RSL Offline Finals Dates + Ticket Sales!10
StarCraft 2
General
Weekly Cups (Oct 20-26): MaxPax, Clem, Creator win RotterdaM "Serral is the GOAT, and it's not close" TL.net Map Contest #21: Voting RSL S3 Round of 16 [TLCH] Mission 7: Last Stand
Tourneys
Sea Duckling Open (Global, Bronze-Diamond) $5,000+ WardiTV 2025 Championship $3,500 WardiTV Korean Royale S4 WardiTV Mondays Sparkling Tuna Cup - Weekly Open Tournament
Strategy
Custom Maps
Map Editor closed ?
External Content
Mutation # 498 Wheel of Misfortune|Cradle of Death Mutation # 497 Battle Haredened Mutation # 496 Endless Infection Mutation # 495 Rest In Peace
Brood War
General
Practice Partners (Official) SnOw's ASL S20 Finals Review [ASL20] Ask the mapmakers — Drop your questions [BSL21] RO32 Group Stage BGH Auto Balance -> http://bghmmr.eu/
Tourneys
BSL21 Open Qualifiers Week & CONFIRM PARTICIPATION [ASL20] Grand Finals Small VOD Thread 2.0 The Casual Games of the Week Thread
Strategy
Current Meta How to stay on top of macro? PvZ map balance Soma's 9 hatch build from ASL Game 2
Other Games
General Games
Dawn of War IV Nintendo Switch Thread Stormgate/Frost Giant Megathread ZeroSpace Megathread General RTS Discussion Thread
Dota 2
Official 'what is Dota anymore' discussion
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
TL Mafia Community Thread SPIRED by.ASL Mafia {211640}
Community
General
US Politics Mega-thread Dating: How's your luck? Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine Canadian Politics Mega-thread
Fan Clubs
White-Ra Fan Club The herO Fan Club!
Media & Entertainment
Anime Discussion Thread [Manga] One Piece Movie Discussion! Korean Music Discussion Series you have seen recently...
Sports
2024 - 2026 Football Thread MLB/Baseball 2023 TeamLiquid Health and Fitness Initiative For 2023 Formula 1 Discussion
World Cup 2022
Tech Support
SC2 Client Relocalization [Change SC2 Language] Linksys AE2500 USB WIFI keeps disconnecting Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
Why we need SC3
Hildegard
Career Paths and Skills for …
TrAiDoS
Reality "theory" prov…
perfectspheres
Our Last Hope in th…
KrillinFromwales
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1727 users

TicTacToe AI

Blogs > micronesia
Post a Reply
micronesia
Profile Blog Joined July 2006
United States24734 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 Kong9158 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 States24734 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 States24734 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 States24734 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 3h 49m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 421
Codebar 37
StarCraft: Brood War
Sea 17888
Bisu 2796
Pusan 361
Stork 310
Hyuk 302
Barracks 202
Leta 133
ToSsGirL 106
Aegong 47
sas.Sziky 43
[ Show more ]
Sharp 31
Yoon 26
JulyZerg 25
zelot 24
Free 18
Rock 10
Terrorterran 7
Shine 7
Dota 2
qojqva2375
Dendi886
420jenkins471
XcaliburYe362
BananaSlamJamma180
Counter-Strike
edward36
Other Games
singsing1839
hiko388
crisheroes378
DeMusliM365
B2W.Neo359
Hui .248
Pyrionflax240
Fuzer 188
XaKoH 121
oskar53
QueenE46
ArmadaUGS28
OptimusSC25
Organizations
Counter-Strike
PGL133
StarCraft: Brood War
lovetv 14
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 13 non-featured ]
StarCraft 2
• StrangeGG 84
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Jankos2879
Other Games
• Shiphtur152
Upcoming Events
LAN Event
3h 49m
OSC
8h 49m
The PondCast
19h 49m
LAN Event
1d
Replay Cast
1d 8h
OSC
1d 21h
LAN Event
2 days
Korean StarCraft League
2 days
CranKy Ducklings
2 days
WardiTV Korean Royale
2 days
[ Show More ]
LAN Event
3 days
IPSL
3 days
dxtr13 vs OldBoy
Napoleon vs Doodle
Replay Cast
3 days
Sparkling Tuna Cup
3 days
WardiTV Korean Royale
3 days
LAN Event
4 days
IPSL
4 days
JDConan vs WIZARD
WolFix vs Cross
Replay Cast
4 days
Wardi Open
4 days
WardiTV Korean Royale
5 days
Replay Cast
6 days
Kung Fu Cup
6 days
Classic vs Solar
herO vs Cure
Reynor vs GuMiho
ByuN vs ShoWTimE
Liquipedia Results

Completed

BSL 21 Points
SC4ALL: StarCraft II
Eternal Conflict S1

Ongoing

C-Race Season 1
IPSL Winter 2025-26
KCM Race Survival 2025 Season 4
SOOP Univ League 2025
YSL S2
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
CS Asia Championships 2025
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025

Upcoming

BSL Season 21
SLON Tour Season 2
BSL 21 Non-Korean Championship
Acropolis #4
HSC XXVIII
RSL Offline Finals
WardiTV 2025
RSL Revival: Season 3
Stellar Fest
META Madness #9
LHT Stage 1
BLAST Bounty Winter 2026: Closed Qualifier
eXTREMESLAND 2025
ESL Impact League Season 8
SL Budapest Major 2025
BLAST Rivals Fall 2025
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 © 2025 TLnet. All Rights Reserved.