Public Group

# Tic-Tac-Toe code review request, basic AI

This topic is 1476 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'd appreciate any feedback on my Tic-Tac-Toe Pygame code. I'm making a basic clone so I can learn about minimax for the computer AI. Currently the AI is just random open blocks.

I'm using the Wikipedia page on minimax HERE, if anyone has a better reference on the algorithm I'd appreciate that information too. Here's my code, and it's available on GitHub as well.

EDIT: Added in minimax for unbeatable AI.

# coding=UTF8
import pygame, os, sys, random, copy
import pygame.freetype
from pygame.locals import *
from pprint import pprint as pp

# Constants
PLAYER = 'player'
COMPUTER = 'computer'
WINDOWWIDTH = 600
WINDOWHEIGHT= 500
TILESIZE    = 120
HALFTILE    = int(TILESIZE / 2)
BOARDWIDTH  = 3
BOARDHEIGHT = 3
FONTSIZE = 50

XMARGIN = int((WINDOWWIDTH - (BOARDWIDTH * TILESIZE)) / 2)
YMARGIN = int((WINDOWHEIGHT - (BOARDHEIGHT * TILESIZE)) / 2)

# Colors
WHITE       = (255, 255, 255)
DARKGRAY    = (40, 40, 40)

def tile_available(board):
tile_available = False
for y in range(BOARDHEIGHT):
if None in board[y]:
tile_available = True
break;
return tile_available

def player_wins(board, current_player):
if [current_player, current_player, current_player] in (
board[0], board[1], board[2],
[board[0][0], board[1][0], board[2][0]],
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]],
[board[2][0], board[1][1], board[0][2]] ):
return True
else:
return False

def minimax(board, player):
if player_wins(board, PLAYER):
return(-1, None)
elif player_wins(board, COMPUTER):
return(+1, None)
elif not tile_available(board):
return (0, None)
elif player == COMPUTER:
best_move = (-2, None)
for y in range(BOARDHEIGHT):
for x in range(BOARDWIDTH):
if board[y][x] == None:
new_board = copy.deepcopy(board)
new_board[y][x] = COMPUTER
value = minimax(new_board, PLAYER)[0]
if value>best_move[0]:
best_move = (value,(x,y))
return best_move
else:
best_move = (+2, None)
for y in range(BOARDHEIGHT):
for x in range(BOARDWIDTH):
if board[y][x] == None:
new_board = copy.deepcopy(board)
new_board[y][x] = PLAYER
value = minimax(new_board, COMPUTER)[0]
if value<best_move[0]:
best_move = (value,(x,y))
return best_move

def main():
pygame.init()
DISPLAYSURF = pygame.display.set_mode( (WINDOWWIDTH, WINDOWHEIGHT) )
pygame.display.set_caption("Tic-Tac-Toe")
FONT = pygame.freetype.Font(None, FONTSIZE)

board = [[None] * 3 for i in range(3)]
game_over = False
winner = None

while not game_over:
mouse_clicked = False
# Event handler
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
sys.exit()
elif event.type == MOUSEBUTTONUP:
mousex, mousey = event.pos
mouse_clicked = True
elif event.type == MOUSEMOTION:
mousex, mousey = event.pos
if mouse_clicked:
for tiley in range(BOARDHEIGHT):
for tilex in range(BOARDWIDTH):
leftpos = tilex * TILESIZE + XMARGIN
toppos = tiley * TILESIZE + YMARGIN
tile_rect = pygame.Rect(leftpos, toppos, TILESIZE, TILESIZE)
if tile_rect.collidepoint(mousex, mousey) and board[tiley][tilex] == None:
board[tiley][tilex] = PLAYER
if player_wins(board, PLAYER):
game_over = True
winner = PLAYER
else:
# Make computer move
if tile_available(board):
compx, compy = minimax(copy.deepcopy(board), COMPUTER)[1]
board[compy][compx] = COMPUTER
else:
game_over = True
winner = 'No one'
if player_wins(board, COMPUTER):
game_over = True
winner = COMPUTER
# Draw board lines
for x in range(TILESIZE, BOARDWIDTH * TILESIZE, TILESIZE):
pygame.draw.line(DISPLAYSURF, DARKGRAY,
(x + XMARGIN, YMARGIN), (x + XMARGIN, WINDOWHEIGHT - YMARGIN), 6)
for y in range(TILESIZE, BOARDHEIGHT * TILESIZE, TILESIZE):
pygame.draw.line(DISPLAYSURF, DARKGRAY,
(XMARGIN, y + YMARGIN), (WINDOWWIDTH - XMARGIN, y + YMARGIN), 6)
# Make tile rects
for y in range(len(board)):
for x in range(len(board[y])):
if board[y][x] in (PLAYER, COMPUTER):
if board[y][x] == PLAYER:
surf, surfrect = FONT.render('X', DARKGRAY, None)
elif board[y][x] == COMPUTER:
surf, surfrect = FONT.render('O', DARKGRAY, None)
surfrect.center = (int(XMARGIN + (x * TILESIZE) + HALFTILE), int(YMARGIN + (y * TILESIZE) + HALFTILE))
DISPLAYSURF.blit(surf, surfrect)

pygame.display.update()
print(winner, "wins!")

if __name__ == '__main__':
while True:
main()

# coding=UTF8
import pygame, os, sys, random, copy
import pygame.freetype
from pygame.locals import *
from pprint import pprint as pp

# Constants
PLAYER = 'player'
COMPUTER = 'computer'
WINDOWWIDTH = 600
WINDOWHEIGHT= 500
TILESIZE    = 120
HALFTILE    = int(TILESIZE / 2)
BOARDWIDTH  = 3
BOARDHEIGHT = 3
FONTSIZE = 50

XMARGIN = int((WINDOWWIDTH - (BOARDWIDTH * TILESIZE)) / 2)
YMARGIN = int((WINDOWHEIGHT - (BOARDHEIGHT * TILESIZE)) / 2)

# Colors
WHITE       = (255, 255, 255)
DARKGRAY    = (40, 40, 40)

class BestMove():
def __init__(self, value, location):
self.value = value
self.location = location

def tile_available(board):
tile_available = False
for y in range(BOARDHEIGHT):
if None in board[y]:
tile_available = True
break;
return tile_available

def player_wins(board, current_player):
if [current_player, current_player, current_player] in (
board[0], board[1], board[2],
[board[0][0], board[1][0], board[2][0]],
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]],
[board[2][0], board[1][1], board[0][2]] ):
return True
else:
return False

def next_player(current_player):
value = None
next = None
if current_player == COMPUTER:
value = -2
next = PLAYER
else:
value = +2
next = COMPUTER
return value, next

def minimax(board, player):
if player_wins(board, PLAYER):
return(-1, None)
elif player_wins(board, COMPUTER):
return(+1, None)
elif not tile_available(board):
return(0, None)
else:
point_value, next_person = next_player(player)
best_move = BestMove(value = point_value, location = None)
for y in range(BOARDHEIGHT):
for x in range(BOARDWIDTH):
if board[y][x] == None:
new_board = copy.deepcopy(board)
new_board[y][x] = player
value = minimax(new_board, next_person)[0]
if (value > best_move.value and player == COMPUTER) or (value < best_move.value and player == PLAYER):
best_move.value, best_move.location = value, (x,y)
return best_move.value, best_move.location

def main():
pygame.init()
DISPLAYSURF = pygame.display.set_mode( (WINDOWWIDTH, WINDOWHEIGHT) )
pygame.display.set_caption("Tic-Tac-Toe")
FONT = pygame.freetype.Font(None, FONTSIZE)

board = [[None] * 3 for i in range(3)]
game_over = False
winner = None

while not game_over:
mouse_clicked = False
# Event handler
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
sys.exit()
elif event.type == MOUSEBUTTONUP:
mousex, mousey = event.pos
mouse_clicked = True
elif event.type == MOUSEMOTION:
mousex, mousey = event.pos
if mouse_clicked:
for tiley in range(BOARDHEIGHT):
for tilex in range(BOARDWIDTH):
leftpos = tilex * TILESIZE + XMARGIN
toppos = tiley * TILESIZE + YMARGIN
tile_rect = pygame.Rect(leftpos, toppos, TILESIZE, TILESIZE)
if tile_rect.collidepoint(mousex, mousey) and board[tiley][tilex] == None:
board[tiley][tilex] = PLAYER
if player_wins(board, PLAYER):
game_over = True
winner = PLAYER
else:
# Make computer move
if tile_available(board):
compx, compy = minimax(board = board, player = COMPUTER)[1]
board[compy][compx] = COMPUTER
else:
game_over = True
winner = 'No one'
if player_wins(board, COMPUTER):
game_over = True
winner = COMPUTER
# Draw board lines
for x in range(TILESIZE, BOARDWIDTH * TILESIZE, TILESIZE):
pygame.draw.line(DISPLAYSURF, DARKGRAY,
(x + XMARGIN, YMARGIN), (x + XMARGIN, WINDOWHEIGHT - YMARGIN), 6)
for y in range(TILESIZE, BOARDHEIGHT * TILESIZE, TILESIZE):
pygame.draw.line(DISPLAYSURF, DARKGRAY,
(XMARGIN, y + YMARGIN), (WINDOWWIDTH - XMARGIN, y + YMARGIN), 6)
# Make tile rects
for y in range(len(board)):
for x in range(len(board[y])):
if board[y][x] in (PLAYER, COMPUTER):
if board[y][x] == PLAYER:
surf, surfrect = FONT.render('X', DARKGRAY, None)
elif board[y][x] == COMPUTER:
surf, surfrect = FONT.render('O', DARKGRAY, None)
surfrect.center = (int(XMARGIN + (x * TILESIZE) + HALFTILE), int(YMARGIN + (y * TILESIZE) + HALFTILE))
DISPLAYSURF.blit(surf, surfrect)

pygame.display.update()
print(winner, "wins!")

if __name__ == '__main__':
while True:
main()

# coding=UTF8
import pygame, os, sys, random, copy
import pygame.freetype
from pygame.locals import *
from pprint import pprint as pp

# Constants
PLAYER = 'player'
COMPUTER = 'computer'
WINDOWWIDTH = 600
WINDOWHEIGHT= 500
TILESIZE    = 120
HALFTILE    = int(TILESIZE / 2)
BOARDWIDTH  = 3
BOARDHEIGHT = 3
FONTSIZE = 50

XMARGIN = int((WINDOWWIDTH - (BOARDWIDTH * TILESIZE)) / 2)
YMARGIN = int((WINDOWHEIGHT - (BOARDHEIGHT * TILESIZE)) / 2)

# Colors
WHITE       = (255, 255, 255)
DARKGRAY    = (40, 40, 40)

class BestMove():
def __init__(self, value, location):
self.value = value
self.location = location

def mouse_clicked(in_board, mousex, mousey):
board = copy.deepcopy(in_board)
game_over = False
winner = None

for tiley in range(BOARDHEIGHT):
for tilex in range(BOARDWIDTH):
leftpos = tilex * TILESIZE + XMARGIN
toppos = tiley * TILESIZE + YMARGIN
tile_rect = pygame.Rect(leftpos, toppos, TILESIZE, TILESIZE)
if tile_rect.collidepoint(mousex, mousey) and board[tiley][tilex] == None:
board[tiley][tilex] = PLAYER
if player_wins(board, PLAYER):
game_over = True
winner = PLAYER
else:
# Make computer move
if tile_available(board):
compx, compy = minimax(board = board, player = COMPUTER)[1]
board[compy][compx] = COMPUTER
else:
game_over = True
winner = 'No one'
if player_wins(board, COMPUTER):
game_over = True
winner = COMPUTER
return board, game_over, winner

def tile_available(board):
tile_available = False
for y in range(BOARDHEIGHT):
if None in board[y]:
tile_available = True
break;
return tile_available

def player_wins(board, current_player):
if [current_player, current_player, current_player] in (
board[0], board[1], board[2],
[board[0][0], board[1][0], board[2][0]],
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]],
[board[2][0], board[1][1], board[0][2]] ):
return True
else:
return False

def next_player(current_player):
value = None
next = None
if current_player == COMPUTER:
value = -2
next = PLAYER
else:
value = +2
next = COMPUTER
return value, next

def draw_board(displaysurf):
for x in range(TILESIZE, BOARDWIDTH * TILESIZE, TILESIZE):
pygame.draw.line(displaysurf, DARKGRAY,
(x + XMARGIN, YMARGIN), (x + XMARGIN, WINDOWHEIGHT - YMARGIN), 6)
for y in range(TILESIZE, BOARDHEIGHT * TILESIZE, TILESIZE):
pygame.draw.line(displaysurf, DARKGRAY,
(XMARGIN, y + YMARGIN), (WINDOWWIDTH - XMARGIN, y + YMARGIN), 6)

def draw_tiles(displaysurf, in_board, x_surf, x_surfrect, o_surf, o_surfrect):
board = copy.deepcopy(in_board)
for y in range(len(board)):
for x in range(len(board[y])):
if board[y][x] in (PLAYER, COMPUTER):
if board[y][x] == PLAYER:
surf, surfrect = x_surf, x_surfrect
elif board[y][x] == COMPUTER:
surf, surfrect = o_surf, o_surfrect
surfrect.center = (int(XMARGIN + (x * TILESIZE) + HALFTILE), int(YMARGIN + (y * TILESIZE) + HALFTILE))
displaysurf.blit(surf, surfrect)

def minimax(board, player):
if player_wins(board, PLAYER):
return(-1, None)
elif player_wins(board, COMPUTER):
return(+1, None)
elif not tile_available(board):
return(0, None)
else:
point_value, next_person = next_player(player)
best_move = BestMove(value = point_value, location = None)
for y in range(BOARDHEIGHT):
for x in range(BOARDWIDTH):
if board[y][x] == None:
new_board = copy.deepcopy(board)
new_board[y][x] = player
value = minimax(new_board, next_person)[0]
if (value > best_move.value and player == COMPUTER) or (value < best_move.value and player == PLAYER):
best_move.value, best_move.location = value, (x,y)
return best_move.value, best_move.location

def main():
pygame.init()
DISPLAYSURF = pygame.display.set_mode( (WINDOWWIDTH, WINDOWHEIGHT) )
pygame.display.set_caption("Tic-Tac-Toe")
FONT = pygame.freetype.Font(None, FONTSIZE)

board = [[None] * 3 for i in range(3)]
game_over = False
winner = None

x_surf, x_surfrect = FONT.render('X', DARKGRAY, None)
o_surf, o_surfrect = FONT.render('O', DARKGRAY, None)

draw_board(displaysurf = DISPLAYSURF)

while not game_over:
# Event handler
event = pygame.event.wait()
if event.type == QUIT:
pygame.quit()
sys.exit()
elif event.type == MOUSEBUTTONUP:
mousex, mousey = event.pos
board, game_over, winner = mouse_clicked(in_board = board, mousex = mousex, mousey = mousey)
elif event.type == MOUSEMOTION:
mousex, mousey = event.pos

draw_tiles( displaysurf = DISPLAYSURF
,in_board = board
,x_surf = x_surf
,x_surfrect = x_surfrect
,o_surf = o_surf
,o_surfrect = o_surfrect )

pygame.display.update()
print(winner, "wins!")

if __name__ == '__main__':
while True:
main()

Edited by tp9

##### Share on other sites

Nothing? Is it because it's in Python or because it's too basic to review? Even that kind of feedback would be helpful so I know what to post for review in the future.

##### Share on other sites

I am betting that there aren't many replies because most people don't have time to do in depth code review even for a small project. Having specific questions is much more useful so people can address directly your concerns. Are you worried about the structure of your program? Do you want an assessment of your code style? What about the data structures and algorithms?

That said, here is some things that I noticed:

1. I feel the code could use some readability work. At a glance, I see a lot of words (which is better than using numbers everywhere) which makes it difficult for the reader to follow. One of the key tools we have in computer science is abstraction. Use it to your advantage to make the code easy to understand. The first step would be to let different files handle different logic. I understand this is a simple project, but it is good to build good habits early on. For example, Python has these handy things called classes. They allow you to group data and logic in a nice format. How can you separate your logic? Maybe a class to handle the board? One for the computer calculations? Maybe one to handle input and another for drawing? Then, your main loop won't be as hectic to understand and will be something like this:

while not game_over:

eventHandler.handle_events(pygame.event.get())

drawer.draw(board)


This is a lot easier to understand than your chunks of code and if you notice it is pretty much your comments abstracted away into classes and functions. Usually if you need comments to break up code, functions would be better.

2. It appears that after someone clicks, you check every tile to see if it was the one clicked. Is this necessary? Is there no mathematical way of transforming a click into which tile it is in?

3. I would consider adding a menu to the game where you can select to play X or O and also present the winner with pygame instead of a print statement. This would be a good extension of the current project.

4. The minimax algorithm looks pretty good. One point in readability would be to use a class instead of a tuple. Tuples are nice for quick and dirty things but hurt readability in my opinion. To me best_move.value > best_move[0] and best_move.location > best_move[1].

5. For integer division, you can use "a // b" instead of "int(a / b)" They are equivalent as far as I know, just depends on what you think is easier to read.

Other than that, looks good for a starter project! Keep at it and doing projects like these is the best way to learn.

##### Share on other sites
Couple of things:

You're modelling Tic Tac Toe, so I think using the constants "player" and "computer" is a little weaker than using "X" and "O". That the game currently uses AI is no guarantee that later you might want to allow two human players, or as TheWhisperingForest suggested you might want to allow the player to choose either X or O. Decoupling these two concepts avoids this problem.

Instead of having a function to determine if a particular player has won, you could write a function to return the player that has actually won.

I notice you're passing the board to minimax by deep copy. Given that minimax appears to already encapsulate deep copying (which is nice), this is unnecessary work.

Your minimax function ends with two nearly identical blocks of code. You may be able to collapse them together, a hint might be to have a nextPlayer(currentPlayer) function.

Given your game does not contain any background simulation, consider using a blocking input model. Pygame appears to have such a function, event.wait, this can reduce the amount of processor your game uses and increase the playtime on battery powered devices.

In your current setup, were there multiple clicks between frames, you would only process one of them. Consider instead of setting the boolean, handling the event right there. You might want to split the mouse click handling into a separate function to make it easier to read.

It appears you're rendering the text multiple times every frame. This is a relatively expensive operation, you can avoid it by pre-rendering the two characters in advance and re-using them instead.

##### Share on other sites

Thanks a lot for all those useful tips. I'll check on those functions and re-factoring suggestions and work on implementing them into my code.

About the classes and abstraction, I've been taking a minimalist approach based on the way I was taught to make simple games that don't require a team. However, that suggestion did not take into account having my code peer-reviewed and I think modularizing my code is a good idea for future code-review requests.

About specific questions, I understand that part but how do I get feedback as my abilities as a developer overall? The feedback about a blocking input model or when I'm rendering my objects might have been missed if I just asked about one particular class or a subfunction block. Is there a better way to get an overall review?

Edited by tp9

##### Share on other sites

Ok, updated my code with most of the suggestions given. It does make my code easier to read and abstracts a lot of the main block out into smaller pieces.

I also learned something new about using a blocking input and proper rendering of objects to save on processing time. Those things will come in handy for my future games that will require more intensive image management.

##### Share on other sites
Yes, for a program this small using classes probably won't buy you much. One small point I would make is that "BestMove" may be a poor class name here. There could be multiple "Best" moves, which seems a little contradictory. If you did want to keep such a class, a name like "ScoredMoved" might be better.

However, the bigger point would be is the move concept the difficult thing to model here? One key things that classes grant is the ability to define and enforce invariants. An invariant is a property that is always true, for example you might have an invariant that all entries in the board are None, X or O. By encapsulating the data and logic that work on it into a class and hiding this detail from client code you reduce the potential "surface area" where bugs could hide.

While we can certainly think of some invariants for the move concept, such as that the co-ordinates are in the range supported, I would argue the Board or GameState might be the more important concept. Much of the code might be re-structured if this concept was introduced, with methods like legal_move, make_move, get_winner all possible implementation choices. As stated, non-member functions might be preferred, thought there is an element of style here too. Modelling the board as immutable (e.g. make_move would return a new Board instance with that move played) could simplify the minimax implementation.

Another thing I noticed when first reviewing, but forgot to mention, is that you are inconsistent with your use of named constants. There are a couple of places in the code where the named constants for the size of the board are not used (where the board is initialised, and player_wins).

Finally:
if (value > best_move.value and player == COMPUTER) or (value < best_move.value and player == PLAYER)

This expression is a little more unsightly that hoped, though not too bad. Perhaps extracting this expression to a named function would help.

##### Share on other sites

However, the bigger point would be is the move concept the difficult thing to model here? One key things that classes grant is the ability to define and enforce invariants. An invariant is a property that is always true, for example you might have an invariant that all entries in the board are None, X or O. By encapsulating the data and logic that work on it into a class and hiding this detail from client code you reduce the potential "surface area" where bugs could hide.

Not sure if I fully understand this point. Are you recommending changing the board into a class and using the board methods to operate on the object? Also, would that mean I create a new board object for every iteration of the recursive function?

Another thing I noticed when first reviewing, but forgot to mention, is that you are inconsistent with your use of named constants. There are a couple of places in the code where the named constants for the size of the board are not used (where the board is initialised, and player_wins).

Thanks for catching that. I didn't notice I left out my constants in those areas. In the player_wins function are you referring to the number constants for the list locations such as board[1][0]? Are you recommending changing that to board[BOARDHEIGHT-2][BOARDWIDTH-3]? If so, that looks less readable to me.

##### Share on other sites

Are you recommending changing the board into a class and using the board methods to operate on the object?

Yes and no. I'm saying that if you're going to make anything a class, I think the board might be the more interesting one, rather than BestMove. But at the same time I don't think that making it a class is an obvious "win" for a small program like this one.

In the player_wins function are you referring to the number constants for the list locations such as board[1][0]?

Yes.

Are you recommending changing that to board[BOARDHEIGHT-2][BOARDWIDTH-3]? If so, that looks less readable to me.

That would be less readable, and doesn't really address the core problem. Ideally, if you're using named constants, you would be able to change the constant in one place and have the entire program still work. So you could change the board height to 5, and it would "just work". Now, the problem about Tic Tac Toe is that, while the code might continue to work at higher or smaller levels, the gameplay doesn't scale quite so well.

However, if we ignore this for a moment, as not all constants have drastic gameplay consequences that make them difficult to change, we can write this function in a board neutral fashion. For instance, we can write one loop to check for a winning row, another to check for winning columns, and another two for winning diagonals.

1. 1
Rutin
24
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 46
• 41
• 23
• 13
• ### Forum Statistics

• Total Topics
631749
• Total Posts
3002031
×