Discuss Scratch

#1Jan. 3, 2020 21:11:22
Mr_Custom
Scratcher
100+ posts

Minimax algorithm help python

I have created a tic-tac-toe minimax algorithm in python 3 that is supposed to be unbeatable, however there are a few things both weird and broken about it.

It does not always win or choose the best option

It is very clunky and not very well written (I would be open to improvements about this aspect even if they did not solve the main issues)

It is written so as to try and avoid strange errors (eg. 
if Maxdepth <= 1
should be 0 not 1 but I did it to avoid it messing up when the search
depth was more than 3!

#AI minimax tic tac toe V2

import os

def display(board):
    print(board[0] + " | " + board[1] + " | " + board[2])
    print(board[3] + " | " + board[4] + " | " + board[5])
    print(board[6] + " | " + board[7] + " | " + board[8])

def getPossible(board, turn):
    possible = []
    temp2 = board.copy()
    while "-" in temp2:
        count1 = 0
        while temp2[count1] != "-" and count1 < len(temp2)-1:
            count1 += 1
        possible.append(board.copy())
        temp2[count1] = turn
        possible[-1][count1] = turn
    return possible

def getScore(board, AIturn):
    if AIturn:
        if board[0] == "X" and board[1] == "X" and board[2] == "X":
            return 10
        elif board[3] == "X" and board[4] == "X" and board[5] == "X":
            return 10
        elif board[6] == "X" and board[7] == "X" and board[8] == "X":
            return 10
        elif board[0] == "X" and board[4] == "X" and board[8] == "X":
            return 10
        elif board[2] == "X" and board[4] == "X" and board[6] == "X":
            return 10
        elif board[0] == "X" and board[3] == "X" and board[6] == "X":
            return 10
        elif board[1] == "X" and board[4] == "X" and board[7] == "X":
            return 10
        elif board[2] == "X" and board[5] == "X" and board[8] == "X":
            return 10
        elif board[0] == "O" and board[1] == "O" and board[2] == "O":
            return -10
        elif board[3] == "O" and board[4] == "O" and board[5] == "O":
            return -10
        elif board[6] == "O" and board[7] == "O" and board[8] == "O":
            return -10
        elif board[0] == "O" and board[4] == "O" and board[8] == "O":
            return -10
        elif board[2] == "O" and board[4] == "O" and board[6] == "O":
            return -10
        elif board[0] == "O" and board[3] == "O" and board[6] == "O":
            return -10
        elif board[1] == "O" and board[4] == "O" and board[7] == "O":
            return -10
        elif board[2] == "O" and board[5] == "O" and board[8] == "O":
            return -10
        else:
            return 0
    else:
        if board[0] == "X" and board[1] == "X" and board[2] == "X":
            return -10
        elif board[3] == "X" and board[4] == "X" and board[5] == "X":
            return -10
        elif board[6] == "X" and board[7] == "X" and board[8] == "X":
            return -10
        elif board[0] == "X" and board[4] == "X" and board[8] == "X":
            return -10
        elif board[2] == "X" and board[4] == "X" and board[6] == "X":
            return -10
        elif board[0] == "X" and board[3] == "X" and board[6] == "X":
            return -10
        elif board[1] == "X" and board[4] == "X" and board[7] == "X":
            return -10
        elif board[2] == "X" and board[5] == "X" and board[8] == "X":
            return -10
        elif board[0] == "O" and board[1] == "O" and board[2] == "O":
            return 10
        elif board[3] == "O" and board[4] == "O" and board[5] == "O":
            return 10
        elif board[6] == "O" and board[7] == "O" and board[8] == "O":
            return 10
        elif board[0] == "O" and board[4] == "O" and board[8] == "O":
            return 10
        elif board[2] == "O" and board[4] == "O" and board[6] == "O":
            return 10
        elif board[0] == "O" and board[3] == "O" and board[6] == "O":
            return 10
        elif board[1] == "O" and board[4] == "O" and board[7] == "O":
            return 10
        elif board[2] == "O" and board[5] == "O" and board[8] == "O":
            return 10
        else:
            return 0

def endState(board):
    if board[0] == "X" and board[1] == "X" and board[2] == "X":
        return True
    elif board[3] == "X" and board[4] == "X" and board[5] == "X":
        return True
    elif board[6] == "X" and board[7] == "X" and board[8] == "X":
        return True
    elif board[0] == "X" and board[4] == "X" and board[8] == "X":
        return True
    elif board[2] == "X" and board[4] == "X" and board[6] == "X":
        return True
    elif board[0] == "X" and board[3] == "X" and board[6] == "X":
        return True
    elif board[1] == "X" and board[4] == "X" and board[7] == "X":
        return True
    elif board[2] == "X" and board[5] == "X" and board[8] == "X":
        return True
    elif board[0] == "O" and board[1] == "O" and board[2] == "O":
        return True
    elif board[3] == "O" and board[4] == "O" and board[5] == "O":
        return True
    elif board[6] == "O" and board[7] == "O" and board[8] == "O":
        return True
    elif board[0] == "O" and board[4] == "O" and board[8] == "O":
        return True
    elif board[2] == "O" and board[4] == "O" and board[6] == "O":
        return True
    elif board[0] == "O" and board[3] == "O" and board[6] == "O":
        return True
    elif board[1] == "O" and board[4] == "O" and board[7] == "O":
        return True
    elif board[2] == "O" and board[5] == "O" and board[8] == "O":
        return True
    elif not "-" in board:
        return True
    else:
        return False

def minimax(board, Maxdepth, AIturn, final):
    global state
    if Maxdepth <= 1 or endState(board):
        return getScore(board, AIturn)
    elif AIturn:
        value = float("-inf")
        for node in getPossible(board, "X"):
            if final and max(value, minimax(node, Maxdepth - 1, False, False)) != value:
                state = node
            value = max(value, minimax(node, Maxdepth - 1, False, False))
    else:
        value = float("inf")
        for node in getPossible(board, "O"):
            if final and min(value, minimax(node, Maxdepth - 1, True, False)) != value:
                state = node
            value = min(value, minimax(node, Maxdepth - 1, True, False))
    if Maxdepth != 0 and not endState(board):
        return value

board = ["-", "-", "-", "-", "-", "-", "-", "-", "-"]
while not endState(board):
    minimax(board, 4, True, True)
    board = state
    display(board)
    print("")
    if not endState(board):
        usri = 0
        while usri < 1 or usri > 9 or board[usri-1] != "-":
            usri = int(input("Pos: "))
        board[usri-1] = "O"
        os.system("cls")
        print("")
    

es = getScore(board, True)
if es == 10:
    print("AI wins!")
elif es == -10:
    print("You win!")
else:
    print("Draw!")

while True:
    pass


Powered by DjangoBB