Problem with a minimax algorith in Tic,Tac,Toe

[Daniel_Gargallo]

Greetings to everyone,
I am a student from Spain, so I am sorry if there's some words wrong. I am doing a project for school and now I have to do a bot who plays tic Tac toe. First, I programmed the game and after I watched a video to see how to do the bot ("https://www.youtube.com/watch?v=2Tr8LkyU78c"). Then I changed some parts of my code and some of the video code. Now, the bot "plays" but it shouldn't lose never and he does. The bot plays first. For example, in the sequence: (a1, b2, a2, a3, b1, c1) you can win. Another problem it is that at the beginning, it takes a lot of time to play the first move (more than expected), I don't have a lot of experience and I don¡t know why it happens. However, it's not a big problem, but, If you know why, I will also solve that problem.
I will be grateful for any help.
Daniel G

possible_choices = ["a1", "a2","a3","b1", "b2","b3","c1","c2","c3"]
init = {"a1" : 0, "a2" : 0, "a3":0, 
        "b1": 0, "b2": 0, "b3":0,
        "c1" : 0, "c2": 0, "c3": 0}

def jugadahumano():
    jugada = str(input("inserte aqui su jugada del tipo : a1"))
    if (jugada in init.keys()) and (jugada in possible_choices):
        init[jugada]=1
        possible_choices.remove(jugada)
    else:
        print("su jugada es incorrecta o bien ya hay una ficha sobre esa casilla")
        jugadahumano()


def jugadarobi():
    bestScore = -1000
    bestMove = 0
    for key in init.keys():
        if (init[key]==0):
            init[key]=2
            score = minimax(init,False)
            init[key]=0
            if (score > bestScore):
                bestScore = score
                bestMove = key

    init[bestMove]= 2



def minimax(board, isMaximizing):
    if (whichmarkwon(2)):
        return 1
    elif (whichmarkwon(1)):
        return -1
    elif (checkDraw()):
        return 0
    elif (isMaximizing==True):
        bestScore = -800
        for key in init.keys():
            if (init[key]== 0):
                board[key]=2
                score = minimax(init,False)
                board[key]=0
                if (score>bestScore):
                    bestScore = score
        return bestScore
    elif (isMaximizing==False):
        bestScore = 800
        for key in init.keys():
            if (init[key]== 0):
                init[key]==1
                score = minimax(init,True)
                init[key]==0
                if(score<bestScore):
                    bestScore = score
        return bestScore



def checkDraw():
    for key in init:
        if init[key]==0:
            return False
            
    return True


def whowin():
    
    if (init["a1"] == init["a2"] ==init["a3"]== 1) or (init["b1"] == init["b2"] == init["b3"]== 1) or (init["c1"] ==init["c2"] ==init["c3"]== 1) or (init["a1"] == init["b2"] == init["c3"]== 1) or (init["c1"] == init["b2"] == init["a3"]== 1) or (init["a1"] == init["b1"] == init["c1"]== 1) or (init["a2"] == init["b2"] == init["c2"]== 1) or (init["a3"] == init["b3"] == init["c3"]== 1):
        print("el ganador de la partida es el humano")
        return True 
    elif (init["a1"] == init["a2"] ==init["a3"]== 2) or (init["b1"] == init["b2"] == init["b3"]== 2) or (init["c1"] ==init["c2"] ==init["c3"]== 2) or (init["a1"] == init["b2"] == init["c3"]== 2) or (init["c1"] == init["b2"] == init["a3"]== 2) or (init["a1"] == init["b1"] == init["c1"]== 2) or (init["a2"] == init["b2"] == init["c2"]== 2) or (init["a3"] == init["b3"] == init["c3"]== 2):
        print("el ganador es el robot")
        return True
    elif checkDraw() == True:
        print("Ha habido empate.")
        return True
    else:
        return False

def whichmarkwon(mark):
    if (init["a1"] == init["a2"] ==init["a3"]== mark) or (init["b1"] == init["b2"] == init["b3"]== mark) or (init["c1"] ==init["c2"] ==init["c3"]== mark) or (init["a1"] == init["b2"] == init["c3"]== mark) or (init["c1"] == init["b2"] == init["a3"]== mark) or (init["a1"] == init["b1"] == init["c1"]== mark) or (init["a2"] == init["b2"] == init["c2"]== mark) or (init["a3"] == init["b3"] == init["c3"]== mark):
        return True
    else:
        return False







print("esto es el juego del tres en ralla, primero juegan los unos unos despues los doses")

while (whowin()== False)or (checkDraw==False):     
    whowin()
    jugadarobi()

    print(init.get("a1"), init.get("a2"), init.get("a3"))
    print(init.get("b1"), init.get("b2"), init.get("b3"))
    print(init.get("c1"), init.get("c2"), init.get("c3"))
    whowin()
    jugadahumano()

    
        

[deanhystad]

About why the first move takes a long time.

There are 255,168 possible combinations in a tic-tac-toe board, 3198 combinations after two selections are made, 108 combinations after 4 selections are made, 6 combinations after 6 selections are made, and only 1 combination after 8 selections are made. Calls to minimax are more than twice that: 549,945 times for the first robot choice, 6811 times for the second robot choice, 257 times for the third robot choice, 15 times for the fourth robot choice, and 1 time for the last open spot on the board.

It takes a while to do something 549,945 times, so speeding up minimax will do a lot to reduce how long it takes the robot to make the first move. Maybe you could keep a count of how many choices have been made and use that instead of using the checkDraw() function. Maybe you could use the fact that the most recent marker will always be a part of the winning row/column/diagonal to speed up the whichmarkwon() function. If the robot just placed a marker there is no reason to check if the player won.

[Daniel_Gargallo]

Thanks for your help,
First I will try to improve the speed and then the rest.
I will inform when the game is finished.

[deanhystad]

Now that I found the problem I can't believe I didn't see it before. It was so obvious it took me almost a day to see it.

This is the code in minimax() for when isMaximizing is False:

                init[key]==1   # <- Does this look odd?
                score = minimax(init,True)
                init[key]==0   # <- How about this:

Fix this problem and I think it will work. I switched over to using minimax and have not beat the computer in 50 tries.

After the code is fixed the first move will be really quick compared to how it was. But the very first move still takes much longer than the second which takes far longer than the third and so on. To speed things up you could have the player go first so the robot only has to test 8 positions which takes much less time than 9 positions. If you still want the robot to go first you could just randomly pick a square for the first move, and by the time the robot plays again there are only 7 moves to test which takes no time at all.

This is my minimax implementation I added to a tkinter tic tac toe game I wrote a while back. I added a randomizer to randomly pick from equally good results. It doesn't come into play very often as there is usually one best answer, but it does prevent the robot always making the same first move.

    def robotMove(self):
        """Get robot move.  Robot choses square that gives it the best chance to win"""
        moves = []
        for move, mark in enumerate(self.board):
            if mark is None:
                self.board[move] = self.ROBOT
                moves.append((move, self.minimax(False)))
                self.board[move] = None
        # To make things less "robotic" randomly choose from equally good results
        random.shuffle(moves)
        moves.sort(key=lambda x:x[1], reverse=True)
        self.placeMarker(moves[0][0], self.ROBOT)
 
    def minimax(self, maximize):
        """Return a "score" for the current board using minimax algorithm.
        Score is computed by recursively calling the function and alternating
        between picking the best move for the robot and the player.  If
        the robot wins the board gets a positive score.  If the player wins the
        board gets a negative score.
        """
        if (win := self.winner()) is not None:
           # Sombody won.  Score +1 if it was the robot and -1 if it was the player.
            score = 1 if self.board[win[0]] == self.ROBOT else -1
        elif not None in self.board:
            score = 0  # Draw
        elif maximize:  # Pick best move for robot (maximum score)
            score = -10000
            for move, marker in enumerate(self.board):
                if marker is None:
                    self.board[move] = self.ROBOT
                    score = max(score, self.minimax(False))
                    self.board[move] = None
        else: # Pick best move for player (minimum score)
            score = 10000
            for move, marker in enumerate(self.board):
                if marker is None:
                    self.board[move] = self.PLAYER
                    score = min(score, self.minimax(True))
                    self.board[move] = None
        return score

[Daniel_Gargallo]

Thank you for spotting the mistake,
As soon as I have more time, I will also study your code to completely understand it.
Again, thanks.

[deanhystad]

Just for fun I have the robot playing the robot. It never wins. I also did some timing for how long it takes the robot to make a move.

Output:
Open slots, Time in seconds
9, 2.3034896850585938
8, 0.2453746795654297
7, 0.03091716766357422
6, 0.003970146179199219
5, 0.0009915828704833984
4, 0.0
3, 0.0
2, 0.0
1, 0.0

A solution for fewer than 6 slots takes so little time it cannot be measured accurately using time.time(). Making a move with 8 open slots has a barely noticeable delay. The only slow move is the first. Since the minimax() function returns the same score for every slot on a new board you may as well have the robot randomly pick a slot.