Tag Archives: events

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()

Game of SIM with Python Turtle (Source Code Included)

Posted on by

Game of SIM was invented in 1969 by Gustavus Simmons. In this two player (red and blue) game, each player takes turn to connect two vertices of a hexagon with the player’s color (either red or blue). The first player who draws all three sides of the triangle with the player’s color loses the game. There is always a winner for this game.

Write a Game of SIM with Python and Turtle graphics. Your game should be able to declare the winner when the game ends. You will need to use onclick() even of Turtle graphics.

Game of SIM with Python Turtle

Source Code:

import turtle
import math

screen = turtle.Screen()
screen.setup(800,800)
screen.title("Game of SIM - PythonTurtle.Academy")
screen.setworldcoordinates(-1.5,-1.5,1.5,1.5)
screen.tracer(0,0)
turtle.hideturtle()

def draw_dot(x,y,color):
    turtle.up()
    turtle.goto(x,y)
    turtle.color(color)
    turtle.dot(15)

def gen_dots():
    r = []
    for angle in range(0,360,60):
        r.append((math.cos(math.radians(angle)),math.sin(math.radians(angle))))
    return r

def draw_line(p1,p2,color):
    turtle.up()
    turtle.pensize(3)
    turtle.goto(p1)
    turtle.down()
    turtle.color(color)
    turtle.goto(p2)
    
def draw_board():
    global selection
    
    for i in range(len(dots)):
        if i in selection: draw_dot(dots[i][0],dots[i][1],turn)
        else: draw_dot(dots[i][0],dots[i][1],'dark gray')
        
def draw():
    draw_board()
    for i in range(len(red)):
        draw_line((math.cos(math.radians(red[i][0]*60)),math.sin(math.radians(red[i][0]*60))),\
                  (math.cos(math.radians(red[i][1]*60)),math.sin(math.radians(red[i][1]*60))),\
                  'red')
    for i in range(len(blue)):
         draw_line((math.cos(math.radians(blue[i][0]*60)),math.sin(math.radians(blue[i][0]*60))),\
                  (math.cos(math.radians(blue[i][1]*60)),math.sin(math.radians(blue[i][1]*60))),\
                  'blue')      
    screen.update()

def play(x,y):
    global selection,turn,red,blue
    
    for i in range(len(dots)):
        dist = (dots[i][0]-x)**2 + (dots[i][1]-y)**2
        if dist<0.001:
            if i in selection: selection.remove(i)
            else: selection.append(i)
            break
    if len(selection)==2:
        selection=(min(selection),max(selection))
        if selection not in red and selection not in blue:
            if turn=='red':
                red.append(selection)
            else:
                blue.append(selection)
            turn = 'red' if turn=='blue' else 'blue'
        selection = []
    draw()
    r = gameover(red,blue)
    if r!=0:
        screen.textinput('game over',r+' won!')
        turtle.bye()

def gameover(r,b):
    if len(r)<3: return 0
    r.sort()
    for i in range(len(r)-2):
        for j in range(i+1,len(r)-1):
            for k in range(j+1,len(r)):
                if r[i][0]==r[j][0] and r[i][1]==r[k][0] and r[j][1]==r[k][1]: return 'blue'
    if len(b)<3: return 0
    b.sort()
    for i in range(len(b)-2):
        for j in range(i+1,len(b)-1):
            for k in range(j+1,len(b)):
                if b[i][0]==b[j][0] and b[i][1]==b[k][0] and b[j][1]==b[k][1]: return 'red'
    return 0

selection = []
turn = 'red'
dots = gen_dots()
red = [ ]
blue = [ ]
draw()
screen.onclick(play)
turtle.mainloop()

Synchronous Fireflies

Posted on by

In a previous project, you animated a lot of fireflies that are moving and lighting up at different phases. In the nature fireflies sometime synchronize making a wonderful show! It is one of the swarm behavior in the nature and we will try to simulate it.

We can make our computer fireflies synchronize by following a very simple rule:

If a firefly sees another another firefly lights up, it will increase its phase slightly to catch up with the nearby firefly.

Synchronized Fireflies with Python Turtle

Read tutorial on this project.

Fireflies

Posted on by

Previously you animated a moving and lighting up dot. Now create many such dots with much smaller size. They all light up every 5 seconds but they light up at different times. We can say they have different phases. Randomize their initial positions and initial phases.

Here is video demo of the project:

Fireflies with Python Turtle

In a next project, we will make these fireflies synchronize.

Read tutorial on this project.