Help please! I can’t make my minimax algorithm work.

Question

I’ve tried everything I can, but the minimax algorithm just isn’t providing the right results. It doesn’t even make a move that leads to an instant win when it has the opportunity. I don’t know why.

https://code.sololearn.com/WsF813udH47Y/?ref=app

Answer 1

Well we know that a win consists of matching 3 linear numbers
1 2 3
4 5 6
7 8 9
Winning combos: [1,2,3],[1,4,7],[1,5,9],[7,8,9],[7,5,3],[9,6,3],[2,5,8],[4,5,6]

you can iterate through the current placements of both player and machine to determine if they’re one away from a win by checking if they have two out of three numbers for a winning combo and if the third number is unclaimed, then claim that third position to either win or counter-win. Example:

Player has positions [8,1,3]
the algorithm checks each array of possible winning combos and compares them to the players placements, one by one, starting from the first winning combo which is [1,2,3]:

player positions = [8,1,3]
match = []
is [8] included in [1,2,3]? no.
continue
is [1] included in [1,2,3]? yes.
match.push(1)
is [2] included in [1,2,3]? yes.
match.push(2)

halt, length of match == 2 which indicates the player is one away from a win, it needs to get the difference between (match[1,2]) and (combo[1,2,3]) which is 3.

Next the machine checks if position 3 is already claimed, if not, then claim position 3 effectivey blocking the player from a win, if it is taken, then continue comparing players placements to winning combos until all have been checked.

This can also work for having the machine choose a winning move by following the same algorithm, but by checking its own placements against the possible matches instead.

As far as minimax goes, that’s a little more complicated than I would be able to put into words, but I use a minimax method in my tic tac toe code that I shared with you in your other post, located in the machineMove() function by utilizing the frequency() function.

The algorithm I explained above for checking for a win is roughly based off the one I wrote, also in my code, under the oneAway() function, if you are interested in that approach!

Answer 2

Jake Ok. I used a minimax that returned “1” if the computer is in winning state, “-1” if the player is in a winning state, and “0” if its a tie as the base cases for the recursion, and if its not a base case it tries each move and calls minimax on the board with that move and returns either the minimum or the maximum value returned from the minimax calls based on if its making moves for the player or the computer. I didn’t bother with one away from win, as it could be handled easily with a “who’s in a winning state, if anybody”. I did just now add aome comments and found a couple mistakes in the process, but no success yet, although it does make a winning move when it can, but doesn’t prevent me from winning.