Category Archives: Difficulty Level Hard

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:

24 Game Solver with Python Turtle (Source Code Included)

Posted on by

24 Game is a mathematical puzzle that make 4 numbers make evaluate to 24 with basic arithmetical operators ( +, -, ×, ÷). For example, given 4 numbers 1,5,5,5, we can make expression (5-(1÷5))×5, which equals to 24.

We can use brute force to solve this problem with a Python Program. There are at most 24×5×4×4×4 = 7,680 different expressions can be made with 4 numbers. It may appear to be hard for us to do by hand, it should be very easy for computer program to solve. The following is the source code for this project:

import turtle
screen = turtle.Screen()
screen.setup(500,500)
screen.title("24 Game Solver - PythonTurtle.Academy")
turtle.hideturtle()
turtle.speed(0)
turtle.up()

def permutation(a):
    if len(a) == 1: return [[a[0]]]
    res = permutation(a[1:])
    r = []
    for x in res:
        # need to insert n into x: into all possible position
        for i in range(len(x)+1):
            y = x.copy()
            y.insert(i,a[0])
            if y not in r:
                r.append(y)
    return r

op = ['+', '−', '×', '÷']
def evaluate(a):
    v = []
    for x in a:
        if type(x) is int:
            v.append(x)
        else:
            num2 = v.pop()
            num1 = v.pop()
            if x=='+': v.append(num1+num2)
            elif x=='−': v.append(num1-num2)
            elif x=='×': v.append(num1*num2)
            else:
                if num2 != 0: v.append(num1/num2)
                else: return 0
    return v[0]


class tree_node:
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

def inorder(root):
    if type(root.value) is int: return str(root.value)
    if type(root.left.value) is not int: left = '('+inorder(root.left)+')'
    else: left = inorder(root.left)
    if type(root.right.value) is not int: right = '('+inorder(root.right)+')'
    else: right = inorder(root.right)    
    return left + root.value + right
    
def convert_to_infix(a):
    # convert to infix
    # convert to tree first
    v = list()
    for x in a:
        if type(x) is int:
            v.append(tree_node(x,None,None))
        else:
            t2 = v.pop()
            t1 = v.pop()
            v.append(tree_node(x,t1,t2))
    return inorder(v[0])
            
def twentyfour(a):
    # postfix
    # try n,n,n,n, p,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a.copy()
                b.append(op[i])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,n,p,p,n,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:3]
                b.append(op[i])
                b.append(op[j])
                b.append(a[3])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,n,p,n,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:3]
                b.append(op[i])
                b.append(a[3])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))

    # try n,n,p,n,p,n,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:2]
                b.append(op[i])
                b.append(a[2])
                b.append(op[j])
                b.append(a[3])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))
    # try n,n,p,n,n,p,p
    for i in range(4):
        for j in range(4):
            for k in range(4):
                b = a[:2]
                b.append(op[i])
                b.append(a[2])
                b.append(a[3])
                b.append(op[j])
                b.append(op[k])
                v = evaluate(b)
                if v==24.0:
                    return(convert_to_infix(b))
    return ''            

while True:
    fournumbers = []
    while len(fournumbers) != 4:
        numbers = screen.textinput("24 Game Solver", "Enter four numbers separated by spaces: ")
        fournumbers = list(map(int,numbers.split()))
    p = permutation(fournumbers)
    foundsolution = False
    turtle.clear()
    for a in p:
        r = twentyfour(a)
        if len(r)>0:
            turtle.goto(0,0)
            turtle.color('royal blue')
            turtle.write(r,font=('Courier', 45, 'bold'), align='center')
            foundsolution = True
            break
    if not foundsolution:
        turtle.color('red')
        turtle.write("No solution",font=('Courier', 45, 'bold'), align='center')

Asteroids Game with Python Turtle

Posted on by

Develop the Asteroids Game with Python Turtle. Because this project is fairly large, you may want to use Object Oriented Programming by defining several classes and put them in separate files. You may also need to know how to detect collisions. These projects will help you develop this game:

You can also add music and sound effects to this game with PyGame’s sound library.

Apollonian Gasket (Full) with Python Turtle

Posted on by

Given any three tangent circles, there are exactly two other circles that are tangent to the three circles. Starting from three big tangent circles of the same size, use recursion to draw more tangent circles.

To figure out the radius of the tangent circle, you may need to look up Soddy Circles.

Apollonian Gasket (Full) with Python Turtle

Connect Four Game with Monte Carlo Tree and Python Turtle

Posted on by

Monte Carlo Tree is a method based on random numbers that is very effective in playing two player games. You don’t have to teach anything to the program, it will figure out the good moves based on random simulations.

Use Monte Carlo Tree Search Algorithm with Python Turtle to make a smart connect 4 player.

Connect Four with Monte Carlo Tree Algorithm Implemented with Python Turtle
Connect Four with Monte Carlo Tree Algorithm Implemented with Python Turtle