• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 14:08
CEST 20:08
KST 03: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
Power Rank - Esports World Cup 202560RSL Season 1 - Final Week9[ASL19] Finals Recap: Standing Tall15HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16
Community News
BSL Team Wars - Bonyth, Dewalt, Hawk & Sziky teams10Weekly Cups (July 14-20): Final Check-up0Esports World Cup 2025 - Brackets Revealed19Weekly Cups (July 7-13): Classic continues to roll8Team TLMC #5 - Submission re-extension4
StarCraft 2
General
The GOAT ranking of GOAT rankings Power Rank - Esports World Cup 2025 What tournaments are world championships? RSL Revival patreon money discussion thread Jim claims he and Firefly were involved in match-fixing
Tourneys
Esports World Cup 2025 Sparkling Tuna Cup - Weekly Open Tournament FEL Cracov 2025 (July 27) - $8000 live event Master Swan Open (Global Bronze-Master 2) Sea Duckling Open (Global, Bronze-Diamond)
Strategy
How did i lose this ZvP, whats the proper response
Custom Maps
External Content
Mutation #239 Bad Weather Mutation # 483 Kill Bot Wars Mutation # 482 Wheel of Misfortune Mutation # 481 Fear and Lava
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion Dewalt's Show Matches in China [Update] ShieldBattery: 2025 Redesign Ginuda's JaeDong Interview Series
Tourneys
[Megathread] Daily Proleagues CSL Xiamen International Invitational [CSLPRO] It's CSLAN Season! - Last Chance [BSL 2v2] ProLeague Season 3 - Friday 21:00 CET
Strategy
Does 1 second matter in StarCraft? [G] Mineral Boosting Simple Questions, Simple Answers
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread [MMORPG] Tree of Savior (Successor of Ragnarok) Path of Exile CCLP - Command & Conquer League Project
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
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Things Aren’t Peaceful in Palestine Stop Killing Games - European Citizens Initiative Russo-Ukrainian War Thread US Politics Mega-thread Post Pic of your Favorite Food!
Fan Clubs
SKT1 Classic Fan Club!
Media & Entertainment
[\m/] Heavy Metal Thread Anime Discussion Thread Movie Discussion! [Manga] One Piece Korean Music Discussion
Sports
Formula 1 Discussion 2024 - 2025 Football Thread TeamLiquid Health and Fitness Initiative For 2023 NBA General Discussion
World Cup 2022
Tech Support
Installation of Windows 10 suck at "just a moment" Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Ping To Win? Pings And Their…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Eight Anniversary as a TL…
Mizenhauer
Customize Sidebar...

Website Feedback

Closed Threads



Active: 984 users

TicTacToe AI

Blogs > micronesia
Post a Reply
micronesia
Profile Blog Joined July 2006
United States24676 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 Kong9154 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 States24676 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 States24676 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 States24676 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
OSC
14:00
King of the Hill #219
davetesta22
Liquipedia
Esports World Cup
11:00
2025 - Final Day
Serral vs ClassicLIVE!
EWC_Arena32492
ComeBackTV 5048
TaKeTV 1275
JimRising 957
Hui .788
3DClanTV 699
Fuzer 454
EnkiAlexander 338
Rex266
CranKy Ducklings168
Reynor149
SpeCial96
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
EWC_Arena32492
JimRising 957
Hui .788
Fuzer 454
Rex 266
UpATreeSC 152
Reynor 149
SpeCial 96
JuggernautJason14
StarCraft: Brood War
Shuttle 2977
Bisu 2657
Mini 913
Larva 800
Soma 392
actioN 339
EffOrt 257
Rush 128
TY 102
JYJ77
[ Show more ]
Shine 68
sorry 32
Aegong 26
yabsab 24
sas.Sziky 22
zelot 19
Terrorterran 14
JulyZerg 11
Sacsri 9
NaDa 6
soO 5
Dota 2
420jenkins706
League of Legends
Trikslyr61
Counter-Strike
fl0m3752
sgares489
oskar211
Heroes of the Storm
Liquid`Hasu51
Other Games
gofns8880
FrodaN2318
tarik_tv2078
Beastyqt748
KnowMe191
crisheroes108
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 15 non-featured ]
StarCraft 2
• IndyKCrew
• sooper7s
• AfreecaTV YouTube
• Migwel
• intothetv
• LaughNgamezSOOP
• Kozan
StarCraft: Brood War
• FirePhoenix3
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• WagamamaTV961
League of Legends
• Nemesis4220
Other Games
• imaqtpie757
• Shiphtur350
Upcoming Events
CranKy Ducklings
15h 53m
BSL20 Non-Korean Champi…
19h 53m
CSO Cup
21h 53m
BSL20 Non-Korean Champi…
23h 53m
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
FEL
1d 14h
BSL20 Non-Korean Champi…
1d 19h
BSL20 Non-Korean Champi…
1d 23h
Bonyth vs Zhanhun
Dewalt vs Mihu
Hawk vs Sziky
Sziky vs QiaoGege
Mihu vs Hawk
Zhanhun vs Dewalt
Fengzi vs Bonyth
Sparkling Tuna Cup
3 days
Online Event
3 days
uThermal 2v2 Circuit
4 days
[ Show More ]
The PondCast
5 days
Replay Cast
6 days
Liquipedia Results

Completed

CSL Xiamen Invitational
Championship of Russia 2025
Murky Cup #2

Ongoing

Copa Latinoamericana 4
Jiahua Invitational
BSL20 Non-Korean Championship
Esports World Cup 2025
CC Div. A S7
Underdog Cup #2
IEM Cologne 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25

Upcoming

CSLPRO Last Chance 2025
ASL Season 20: Qualifier #1
ASL Season 20: Qualifier #2
ASL Season 20
CSLPRO Chat StarLAN 3
BSL Season 21
RSL Revival: Season 2
Maestros of the Game
SEL Season 2 Championship
uThermal 2v2 Main Event
FEL Cracov 2025
HCC Europe
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
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.