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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

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:

1 2 3

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

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.