[자료구조] minimax 알고리즘

Tic Tac Toe

import random

board = {1:' ', 2:' ', 3:' ', 
         4:' ', 5:' ', 6:' ',
         7:' ', 8:' ', 9:' '}

player = 'O'
computer = 'X'

def printBoard(board):
    print()
    print(board[1] + "|" + board[2] + "|" + board[3])
    print("-+-+-")
    print(board[4] + "|" + board[5] + "|" + board[6])
    print("-+-+-")
    print(board[7] + "|" + board[8] + "|" + board[9])
    print()
    
def insertLetter(letter, position):
    if board[position] == ' ':
        board[position] = letter
        printBoard(board)
        
        if checkDraw():
            print("Draw!")
            exit()
        
        if checkWin():
            if letter == 'X':
                print("Bot wins!")
                exit()
            else :
                print("Player wins!")
                exit()
        return
    else :
        print("Invalid position")
        position = int(input("Please enter a new position: "))
        insertLetter(letter, position)
        return

def checkWin() :
    if (board[1] == board[2] and board[1] == board[3] and board[1] != ' '):
        return True
    elif (board[4] == board[5] and board[4] == board[6] and board[4] != ' '):
        return True
    elif (board[7] == board[8] and board[7] == board[9] and board[7] != ' '):
        return True
    elif (board[1] == board[4] and board[1] == board[7] and board[1] != ' '):
        return True
    elif (board[2] == board[5] and board[2] == board[8] and board[2] != ' '):
        return True
    elif (board[3] == board[6] and board[3] == board[9] and board[3] != ' '):
        return True
    elif (board[1] == board[5] and board[1] == board[9] and board[1] != ' '):
        return True
    elif (board[7] == board[5] and board[7] == board[3] and board[7] != ' '):
        return True
    else:
        return False

def checkDraw() :
    for key in board.keys():
        if board[key] == ' ':
            return False
    return True
    
def playerMove():
    position = int(input("Enter a position for 'O': "))
    insertLetter(player, position)
    return

def compMove():
    #position = int(input("Enter a position for 'X': "))
    #insertLetter(computer, position)
    #return
    
    bestScore = -800
    bestMove = 0
    
    for key in board.keys():
        if board[key] == ' ':
            board[key] = computer
            score = minimax(board, False) #
            board[key] = ' '
            if score > bestScore :
                bestScore = score
                bestMove = key
    insertLetter(computer, bestMove)
    return

def minimax(board, isMaximizing) :
    if checkWhichMarkWon(computer):
        return 1
    elif checkWhichMarkWon(player):
        return -1
    elif checkDraw():
        return 0
    
    if isMaximizing :
        bestScore = -800
        for key in board.keys() :
            if board[key] == ' ':
                board[key] = computer
                score = minimax(board, False)
                board[key] = ' '
                if score > bestScore:
                    bestScore = score
        return bestScore
    else:
        bestScore = 800
        for key in board.keys():
            if board[key] == ' ':
                board[key] = player
                score = minimax(board, True)
                board[key] = ' '
                if score < bestScore:
                    bestScore = score
        return bestScore
                    
           
def checkWhichMarkWon(mark) :
    if (board[1] == board[2] and board[1] == board[3] and board[1] == mark):
        return True
    elif (board[4] == board[5] and board[4] == board[6] and board[4] == mark):
        return True
    elif (board[7] == board[8] and board[7] == board[9] and board[7] == mark):
        return True
    elif (board[1] == board[4] and board[1] == board[7] and board[1] == mark):
        return True
    elif (board[2] == board[5] and board[2] == board[8] and board[2] == mark):
        return True
    elif (board[3] == board[6] and board[3] == board[9] and board[3] == mark):
        return True
    elif (board[1] == board[5] and board[1] == board[9] and board[1] == mark):
        return True 
    elif (board[7] == board[5] and board[7] == board[3] and board[7] == mark):
        return True
    else:
        return False    

while not checkWin():
    if (board[1] == board[2] and board[1] == board[3] and board[1] == board[4] and
        board[1] == board[5] and board[1] == board[6] and board[1] == board[6] and 
        board[1] == board[7] and board[1] == board[8] and board[1] == board[9] and board[1] == ' ' ) :
        insertLetter(computer, random.randint(1, 9))
    
    playerMove()
    compMove()
    

생각해보기

• 깊이를 생각하여 이길 수 있는 짧은 경로를 선택
• 설명 추가
• 참고 : https://www.youtube.com/watch?v=JC1QsLOXp-I