Search code examples
javascriptminimax

Should miniMax algorithm be able to handle any input

I'm working to build a basic tictactoe game using the miniMax algorythm and I have an implementation in JavaScript that works, sort of. However I'm feeding it some test board states and it doesn't seem to be working the way I expect. For example if I feed it

['o', '1', 'x',
'x',   4,   5,
'x',  'o', 'o']

it tells me that the next correct move for X is index 4 (winning state.) However if I feed it 

['o', 'x',  2,
 'o',  4,   5,
 'x',  7,  'x']

it tells me that the next correct move for O is index 2 (which is an instant fail as X will win by taking position 7.

So basically what I'm wondering is if this matters. From working through the game progression I don't believe that the board layout in the second example is one that could ever actually occur using the algorithm, no matter what X does the computer running O won't let the board get into this state so perhaps my implementation is correct. Should miniMax be able to handle this (or any board state) or is this test board state just one that it can't handle because it's an "impossible" state. I don't trust code that I don't fully understand so any advice is welcomed.

Full code of my implementation is on Github here: https://github.com/cugamer/tictactoe/tree/master/lib

Solution

  • Yes it should cover any input, and yes it does matter, because you might have bug somewhere in your code that you need to kick out.

    Mainly because Minimax is simply given a state of the board, not the history i.e series of moves that led to this position. It simply have no way to figure out if a state is "possible" state. All it does is look ahead i.e finds out all future possible states that could arise, and if any of them leads to a sure defeat, it should be able to avoid that path.

    Your specific example however is an interesting case. No matter how 'O' proceeds, it'll be a defeat in the end. So, all possible moves will return same i.e lowest possible score for player 'O'. Since in your code bestMove don't get updated unless a better moves come along, which there isn't any in this case, it will simply return the first move.