python-3.xminimax

Minimax algorithm not working in tic tac toe game


I have recently learned about minimax and I am trying to make an unbeatable AI tic tac toe game. I don't know why my minimax function does not work and my computer sometime plays un optimal moves.

This is my full code:

from random import randint
import os

def play_again():
    print()
    t=True
    while t:
        p=input("Do you want to play again? Y or N  ").upper()
        if p=='Y' or p=='YES':
            t=False
            return True
        elif p=='N' or p=='NO':
            t=False
            print("Thank You!!")
            return False
        else:
            print('Enter a valid input!')
            
    
        
while True:

    board1=['1','2','3','4','5','6','7','8','9']
    print('    |   |')
    print(' ',board1[0],'|',board1[1],'|',board1[2])
    print('____|___|____')
    print('    |   |')
    print(' ',board1[3],'|',board1[4],'|',board1[5])
    print('____|___|____')
    print('    |   |')
    print(' ',board1[6],'|',board1[7],'|',board1[8])
    print('    |   |')

    
    board=[' ',' ',' ',' ',' ',' ',' ',' ',' ']
    def print_board():
        
        print('    |   |')
        print(' ',board[0],'|',board[1],'|',board[2])
        print('____|___|____')
        print('    |   |')
        print(' ',board[3],'|',board[4],'|',board[5])
        print('____|___|____')
        print('    |   |')
        print(' ',board[6],'|',board[7],'|',board[8])
        print('    |   |')


    if randint(0,1)==0:
        player='Player 1'
    else:
        player='Player 2'


    a='a'
    while a not in ['X','O']:
        a=input("Player 1: Do you want to be X or O: ").upper()
            
        if a not in ['X','O']:
            print("Enter valid output X or O")

    if a=='X':
        c='O'
    else:
        c='X'

    def first():
        if player=='Player 1':
            print()
            print('Player 1 will go first')
            
        else:
            print()
            print('Player 2 will go first')
            
    first()

    def position_check():
        return board[b-1] not in ['X','O']

    def board_full():
        for i in board:
            if i not in ['X','O']:
                return True
        return False


    def win_check(m):
        return ((board[0]==m and board[1]==m and board[2]==m) or
                (board[3]==m and board[4]==m and board[5]==m) or
                (board[6]==m and board[7]==m and board[8]==m) or
                (board[0]==m and board[3]==m and board[6]==m) or
                (board[1]==m and board[4]==m and board[7]==m) or
                (board[2]==m and board[5]==m and board[8]==m) or
                (board[0]==m and board[4]==m and board[8]==m) or
                (board[2]==m and board[4]==m and board[6]==m))

    def minimax(board,depth,ismax):
        
        if win_check(c):
            return 1

        elif win_check(a):
            return -1

        elif not board_full:
            return 0

        if ismax:
            bestscore = -1000

            for i in range(len(board)):
                
                if board[i]==' ':
                    board[i]=c
                    score= minimax(board,depth+1,False)
                    
                    board[i]=' '

                    if score > bestscore:
                        bestscore = score

            return bestscore

        else:
            bestscore = 1000

            for i in range(len(board)):
                if board[i]==' ':
                    
                    board[i]=a

                    score= minimax(board,depth+1,True)
                    
                    board[i]=' '

                    if score < bestscore:
                        bestscore = score

            return bestscore
            
        
    while board_full():
        
        if player=='Player 1':
            b='a'
            within_range=False
            while b.isdigit()==False or within_range==False:
                b=input("Enter your next move (1-9) :")

                if b.isdigit()==False:
                    print('\n'*100)
                    print('Enter a choice between 1-9')

                if b.isdigit()==True:
                    if int(b) in range(1,10):
                        within_range=True
                    else:
                        print('Enter a choice between 1-9')

            b=int(b)

            if position_check():
                board[b-1]=a
                print_board()
                if win_check(a):
                    print('Congratulations Player 1 wins!!')
                    break
                else:
                    player='Player 2'

            else:
                print('Position already occupied')

        if player=='Player 2':

            bestscore = -1000

            for i in range(len(board)):
                if board[i]==' ':
                    board[i]=c

                    score= minimax(board,0,False)
                    
                    board[i]=' '

                    if score > bestscore:
                        bestscore = score
                        bestmove=i
                        b=bestmove

            if position_check:
                
                board[b]=c
                
                print_board()
                
                if win_check(c):
                    print('Congratulations Player 2 wins!!')
                    break
                else:
                    player='Player 1'
                    
                


    else:
        print('Its a DRAW!!')


    if not play_again():
        break

When I play position 1 comp should play position 5 but it doesn't but it always plays position 2 and eventually looses Where is the mistake in my code I just learned about minimax and I don't want to use depth concept :

    |   |
  1 | 2 | 3
____|___|____
    |   |
  4 | 5 | 6
____|___|____
    |   |
  7 | 8 | 9
    |   |
Player 1: Do you want to be X or O: x

Player 1 will go first
Enter your next move (1-9) :1
    |   |
  X |   |  
____|___|____
    |   |
    |   |  
____|___|____
    |   |
    |   |  
    |   |
    |   |
  X | O |  
____|___|____
    |   |
    |   |  
____|___|____
    |   |
    |   |  
    |   |

Solution

  • There are a few issues:

    Not a problem, but:

    There is certainly much more to improve, but the above changes (and a few more), led to this version of your code:

    from random import randint
    
    def play_again():
        print()
        while True:
            p=input("Do you want to play again? Y or N  ").upper()
            if p=='Y' or p=='YES':
                return True
            elif p=='N' or p=='NO':
                print("Thank You!!")
                return False
            else:
                print('Enter a valid input!')
    
    def print_board(board):  # parameter list
        print('    |   |')
        print(' ',board[0],'|',board[1],'|',board[2])
        print('____|___|____')
        print('    |   |')
        print(' ',board[3],'|',board[4],'|',board[5])
        print('____|___|____')
        print('    |   |')
        print(' ',board[6],'|',board[7],'|',board[8])
        print('    |   |')
    
    def first(player):  # argument list
        print()
        if player=='Player 1':
            print('Player 1 will go first')
        else:
            print('Player 2 will go first')
            
    def position_check(board, move):
        return board[move] not in ['X','O']
    
    def board_has_moves(board):
        for i in board:
            if i not in ['X','O']:
                return True
        return False
    
    def win_check(board, m):
        return ((board[0]==m and board[1]==m and board[2]==m) or
                (board[3]==m and board[4]==m and board[5]==m) or
                (board[6]==m and board[7]==m and board[8]==m) or
                (board[0]==m and board[3]==m and board[6]==m) or
                (board[1]==m and board[4]==m and board[7]==m) or
                (board[2]==m and board[5]==m and board[8]==m) or
                (board[0]==m and board[4]==m and board[8]==m) or
                (board[2]==m and board[4]==m and board[6]==m))
    
    # A function to deal with one game
    def playgame(board, player, player_1_symbol, player_2_symbol):
        def minimax(depth, ismax):  # removed board parameter, as already in scope
            if win_check(board, player_2_symbol):  # pass board also
                return 1
            elif win_check(board, player_1_symbol):
                return -1
            elif not board_has_moves(board):  # call it, rename it
                return 0
            if ismax:
                bestscore = -1000
                for i in range(len(board)):
                    if board[i]==' ':
                        board[i]=player_2_symbol
                        score= minimax(depth+1,False)
                        board[i]=' '
                        if score > bestscore:
                            bestscore = score
                return bestscore
            else:
                bestscore = 1000
                for i in range(len(board)):
                    if board[i]==' ':
                        board[i]=player_1_symbol
                        score= minimax(depth+1,True)
                        board[i]=' '
                        if score < bestscore:
                            bestscore = score
                return bestscore
        
        while board_has_moves(board):  # better name; pass argument
            if player=='Player 1':
                move='a'  # better name
                within_range=False
                while not move.isdigit() or not within_range:
                    move=input("Enter your next move (1-9) :")
                    if not move.isdigit():
                        print('\n'*100)
                        print('Enter a choice between 1-9')
                    if move.isdigit():
                        if int(move) in range(1,10):
                            within_range=True
                        else:
                            print('Enter a choice between 1-9')
                move=int(move)-1  # reduce to make it 0-based
                if position_check(board, move):  # pass the arguments
                    board[move]=player_1_symbol   # b is zero based now
                    print_board(board)  # pass argument
                    if win_check(board, player_1_symbol):  # pass arguments
                        print('Congratulations Player 1 wins!!')
                        break
                    else:
                        player='Player 2'
                else:
                    print('Position already occupied')
            else:  # changed to avoid code falling thru from the previous block
                bestscore = -1000
                bestmove = 10  # better initialise before loop
                for i in range(len(board)):
                    if board[i]==' ':
                        board[i]=player_2_symbol
                        score= minimax(0,False)
                        board[i]=' '
                        if score > bestscore:
                            bestscore = score
                            bestmove=i
                if position_check(board, bestmove):  # add the parentheses to call it
                    board[bestmove]=player_2_symbol
                    print_board(board)  # pass argument
                    if win_check(board, player_2_symbol):
                        print('Congratulations Player 2 wins!!')
                        break
                    else:
                        player='Player 1'
        else:
            print('Its a DRAW!!')
    
    
    # Main program
    def main():  # avoid global variables, and put main logic in a function
        while True:
            board1=['1','2','3','4','5','6','7','8','9']
            print('    |   |')
            print(' ',board1[0],'|',board1[1],'|',board1[2])
            print('____|___|____')
            print('    |   |')
            print(' ',board1[3],'|',board1[4],'|',board1[5])
            print('____|___|____')
            print('    |   |')
            print(' ',board1[6],'|',board1[7],'|',board1[8])
            print('    |   |')
            board=[' ',' ',' ',' ',' ',' ',' ',' ',' ']
        
            # simplified:
            player = ('Player 1', 'Player 2')[randint(0,1)]
            player_1_symbol ='a'  # better name
            while player_1_symbol not in ['X','O']:
                player_1_symbol=input("Player 1: Do you want to be X or O: ").upper()
                if player_1_symbol not in ['X','O']:
                    print("Enter valid output X or O")
            # use ternary operator, and use better name
            player_2_symbol = 'O' if player_1_symbol=='X' else 'X'
            first(player)  # pass argument
            # move the move-loop logic into another function:
            playgame(board, player, player_1_symbol, player_2_symbol)
            if not play_again():
                break
        
    main()