Monthly Archives: July 2020

AI Tic-Tac-Toe with Minimax Tree (Source Code Included)

Posted on by

Use minimax tree search algorithm with alpha-beta pruning to write AI Tic-Tac-Toe player. You may also want to add randomness to your AI player so that it won’t play the same move every time. Here is more detail information on minimax tree and alpha-beta pruning. Your program should play against a human player. Therefore, you need to use onclick() function to handle mouse click events.

Tic-Tac-Toe with Minimax Tree

Source Code:

import turtle
import copy
import random

screen = turtle.Screen()
screen.setup(800,800)
screen.title("Tic Tac Toe - PythonTurtle.Academy")
screen.setworldcoordinates(-5,-5,5,5)
screen.bgcolor('light gray')
screen.tracer(0,0)
turtle.hideturtle()

def draw_board():
    turtle.pencolor('green')
    turtle.pensize(10)
    turtle.up()
    turtle.goto(-3,-1)
    turtle.seth(0)
    turtle.down()
    turtle.fd(6)
    turtle.up()
    turtle.goto(-3,1)
    turtle.seth(0)
    turtle.down()
    turtle.fd(6)
    turtle.up()
    turtle.goto(-1,-3)
    turtle.seth(90)
    turtle.down()
    turtle.fd(6)
    turtle.up()
    turtle.goto(1,-3)
    turtle.seth(90)
    turtle.down()
    turtle.fd(6)

def draw_circle(x,y):
    turtle.up()
    turtle.goto(x,y-0.75)
    turtle.seth(0)
    turtle.color('red')
    turtle.down()
    turtle.circle(0.75, steps=100)

def draw_x(x,y):
    turtle.color('blue')
    turtle.up()
    turtle.goto(x-0.75,y-0.75)
    turtle.down()
    turtle.goto(x+0.75,y+0.75)
    turtle.up()
    turtle.goto(x-0.75,y+0.75)
    turtle.down()
    turtle.goto(x+0.75,y-0.75)
    
def draw_piece(i,j,p):
    if p==0: return
    x,y = 2*(j-1), -2*(i-1)
    if p==1:
        draw_x(x,y)
    else:
        draw_circle(x,y)
    
def draw(b):
    draw_board()
    for i in range(3):
        for j in range(3):
            draw_piece(i,j,b[i][j])
    screen.update()

# return 1 if player 1 wins, 2 if player 2 wins, 3 if tie, 0 if game is not over
def gameover(b):
    if b[0][0]>0 and b[0][0] == b[0][1] and b[0][1] == b[0][2]: return b[0][0]
    if b[1][0]>0 and b[1][0] == b[1][1] and b[1][1] == b[1][2]: return b[1][0]
    if b[2][0]>0 and b[2][0] == b[2][1] and b[2][1] == b[2][2]: return b[2][0]
    if b[0][0]>0 and b[0][0] == b[1][0] and b[1][0] == b[2][0]: return b[0][0]
    if b[0][1]>0 and b[0][1] == b[1][1] and b[1][1] == b[2][1]: return b[0][1]
    if b[0][2]>0 and b[0][2] == b[1][2] and b[1][2] == b[2][2]: return b[0][2]
    if b[0][0]>0 and b[0][0] == b[1][1] and b[1][1] == b[2][2]: return b[0][0]
    if b[2][0]>0 and b[2][0] == b[1][1] and b[1][1] == b[0][2]: return b[2][0]
    p = 0
    for i in range(3):
        for j in range(3):
            p += (1 if b[i][j] > 0 else 0)
    if p==9: return 3
    else: return 0
    
def play(x,y):
    global turn
    if turn=='x': return
    
    i = 3-int(y+5)//2
    j = int(x+5)//2 - 1
    if i>2 or j>2 or i<0 or j<0 or b[i][j]!=0: return
    if turn == 'x': b[i][j], turn = 1, 'o'
    else: b[i][j], turn = 2, 'x'
    draw(b)
    r = gameover(b)
    if r==1:
        screen.textinput("Game over!","X won!")
    elif r==2:
        screen.textinput("Game over!","O won!")
    elif r==3:
        screen.textinput("Game over!", "Tie!")
    if r>0: turtle.bye()
    _,move = max_node(b,-2,2)
    b[move[0]][move[1]] = 1
    draw(b)
    r = gameover(b)
    if r==1:
        screen.textinput("Game over!","X won!")
    elif r==2:
        screen.textinput("Game over!","O won!")
    elif r==3:
        screen.textinput("Game over!", "Tie!")
    if r>0: turtle.bye()
    turn = 'o'
    
b = [ [ 0,0,0 ], [ 0,0,0 ], [ 0,0,0 ] ]    
draw(b)
turn = 'x'
screen.onclick(play)
#turtle.mainloop()

def max_node(b,alpha,beta):
    r = gameover(b)
    if r==1: return 1,None
    elif r==2: return -1,None
    elif r==3: return 0,None

    score = -2
    # find all possible next moves
    pm = list()
    for i in range(3):
        for j in range(3):
            if b[i][j] == 0: pm.append((i,j))
    random.shuffle(pm)
    for (i,j) in pm:
        if b[i][j] == 0:
            nb = copy.deepcopy(b)
            nb[i][j] = 1
            cs,_ = min_node(nb,alpha,beta)
            if score<cs:
                score=cs
                move = (i,j)
            alpha = max(alpha,cs)
            if alpha>=beta: return score,move
    return score,move

def min_node(b,alpha,beta):
    r = gameover(b)
    if r==1: return 1,None
    elif r==2: return -1,None
    elif r==3: return 0,None

    score = 2
    # find all possible next moves
    pm = list()
    random.shuffle(pm)
    for i in range(3):
        for j in range(3):
            if b[i][j] == 0: pm.append((i,j))
    for (i,j) in pm:
        if b[i][j] == 0:
            nb = copy.deepcopy(b)
            nb[i][j] = 2
            cs,_ = max_node(nb,alpha,beta)
            if score>cs:
                score=cs
                move = (i,j)
            beta = min(beta,cs)
            if alpha>=beta: return score,move
    return score,move

_,move = max_node(b,-2,2)
b[move[0]][move[1]] = 1
draw(b)
turn = 1
screen.mainloop()

Related Projects:

Connect 4 with Python Turtle (Source Code Included)

Posted on by

Write a connect 4 program with Python and Turtle graphics. Your game should be able to let two human players play against each other and declare winner or tie when the game ends. You need to use onclick() event to handle the mouse click.

Connect 4 with Python Turtle

Source Code:

import turtle
import time

screen = turtle.Screen()
screen.setup(800,800)
screen.setworldcoordinates(-500,-500,500,500)
screen.title("Connect 4 - PythonTurtle.Academy")
turtle.speed(0)
turtle.hideturtle()
screen.tracer(0,0)
score = turtle.Turtle()
score.up()
score.hideturtle()

ROWS = 6
COLS = 7
STARTX = -450
STARTY = -450*ROWS/COLS
WIDTH = -2*STARTX
HEIGHT = -2*STARTY

def draw_rectangle(x,y,w,h,color):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.fillcolor(color)
    turtle.begin_fill()
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.end_fill()

def draw_circle(x,y,r,color):
    turtle.up()
    turtle.goto(x,y-r)
    turtle.seth(0)
    turtle.down()
    turtle.fillcolor(color)
    turtle.begin_fill()
    turtle.circle(r,360,150)
    turtle.end_fill()

def draw_board():
    draw_rectangle(STARTX,STARTY,WIDTH,HEIGHT,'light blue')

def draw_pieces():
    global board
    row_gap = HEIGHT/ROWS
    col_gap = WIDTH/COLS
    Y = STARTY + row_gap / 2;
    for i in range(ROWS):
        X = STARTX + col_gap/2
        for j in range(COLS):
            if board[i][j] == 0:
                draw_circle(X,Y,row_gap/3,'white')
            elif board[i][j] == 1:
                draw_circle(X,Y,row_gap/3,'black')
            else:
                draw_circle(X,Y,row_gap/3,'red')
            X += col_gap
        Y += row_gap

def draw():
    draw_board()
    draw_pieces()
    screen.update()
    
def game_over_lastmove(bb,turn,r,c):
    # check horizontals
    cnt = 1
    i = c+1
    while i<COLS and bb[r][i]==turn: cnt, i = cnt+1, i+1
    i = c-1
    while i>=0 and bb[r][i]==turn: cnt, i = cnt+1, i-1
    if cnt>=4: return turn
    
    # check vertical
    if r>=3 and bb[r-1][c]==turn and bb[r-2][c]==turn and bb[r-3][c]==turn: return turn

    # check diag 2
    cnt = 1
    i = 1
    while r+i<ROWS and c+i<COLS and bb[r+i][c+i]==turn: cnt, i = cnt+1, i+1
    i = -1
    while r+i>=0 and c+i>=0 and bb[r+i][c+i]==turn: cnt, i = cnt+1, i-1
    if cnt>=4: return turn

    # check diag 1
    cnt = 1
    i = 1
    while r+i<ROWS and c-i>=0 and bb[r+i][c-i]==turn: cnt, i = cnt+1, i+1
    i = -1
    while r+i>=0 and c-i<COLS and bb[r+i][c-i]==turn: cnt, i = cnt+1, i-1
    if cnt>=4: return turn
    
    for i in range(COLS):
        if bb[ROWS-1][i] == 0:
            return -2
    return 0

# place piece in col for turn
def place_piece(bb,turn,col):
    for i in range(ROWS):
        if bb[i][col] == 0:
            bb[i][col] = turn
            return i

def init_board():
    global board
    for i in range(ROWS):
        row = []
        for j in range(COLS):
            row.append(0)
        board.append(row)
    
def place_piece_and_draw(bb,turn,col):
    row = place_piece(bb,turn,col)
    row_gap = HEIGHT/ROWS
    col_gap = WIDTH/COLS
    Y = STARTY + row_gap*row + row_gap / 2;
    X = STARTX + col_gap*col + col_gap/2
    i = row
    j = col
    if board[i][j] == 0:
        draw_circle(X,Y,row_gap/3,'white')
    elif board[i][j] == 1:
        for k in range(5):
            draw_circle(X,Y,row_gap/3,'white')
            screen.update()
            time.sleep(0.05)
            draw_circle(X,Y,row_gap/3,'black')
            screen.update()
            time.sleep(0.05)
    else:
        for k in range(5):
            draw_circle(X,Y,row_gap/3,'white')
            screen.update()
            time.sleep(0.05)
            draw_circle(X,Y,row_gap/3,'red')
            screen.update()
            time.sleep(0.05)
    return row

def play(x,y):
    global turn,working
    if working: return
    working = True
    cols = [ 900/7*i-450+900/14 for i in range(7) ]
    for i in range(len(cols)):
        if abs(x-cols[i]) < 900/14*2/3 and board[ROWS-1][i]==0:
            rn = place_piece_and_draw(board,turn,i)
            r = game_over_lastmove(board,turn,rn,i)
            if r==0:
                screen.textinput('Game over','tie')
            elif r==1:
                screen.textinput('Game over','player 1 won')
            elif r==-1:
                screen.textinput('Game over','player 2 won')
            if r!=-2: screen.bye()
            turn = -turn
    working = False

board = []
init_board()
draw_board()
draw_pieces()
turn=1
working=False
screen.onclick(play)
screen.mainloop()