I have already scoured the web for psuedocode, working examples, stack overflow problems/solutions of the same realm, and I have not found anything to be of help so far so I'm reaching out on here.
I'm trying to implement the Minimax algorithm in my Tic Tac Toe game in a very basic way (no alpha/beta pruning). Let me explain each helper method I have, and then I can share parts of my actual code if you need it. Note (I am NOT using depth when checking for terminal state, only checking for win or checking for a draw.)
First, I have the utility MakeBestMove that will be called upon a computer move, then within MakeBestMove will call MiniMax, which then will call itself until the boardState reaches a terminal state or when there are no moves left.
I want MakeBestMove to return the best move, and my MiniMax function to return a score of the boardState.
If you are familiar with MiniMax, when state is terminal the state is scored. I've used -100 for player O win, 100 for player X win, and 0 for draw to score my game. This is done in my EvaluateScore helper function.I also have a function that will determine the available moves based upon current state of the game board to help me iterate through the open moves. Also, it might be important to note that player "X" is always a human and player "O" is always the computer.
I'm trying to use the same approach I used in Python to implement MiniMax with F#, and it should theoretically work, even though it's not being loyal to F# functional paradigm.
For some reason or another, it does not behave how I would expect it to. I have spent hours going over each line of code to make sure I wasn't having any weird side-effects, but have not had any success. I would appreciate it if someone could point me in the right direction. I know I wrote it very imperatively, but I do think it can work this way, but can't seem to figure out why it doesn't and what I might possibly be missing. Any help is greatly appreciated!
CODE BEHAVIOR ISSUES: 1. Does not return bestMove in MakeBestMove correctly 2. While the Minimax function appears to look like it is behaving correctly by recursively iterating through different terminal boardStates, the MakeBestMove will not block moves for "O" but will take the winning move when it's one move away.
HOW I WANT MY CODE TO BEHAVE: 1. Ability to correctly score boardState (which I believe I already am doing.) 2. Ability to return that score if boardState is terminal, or if there are no more moves left to take (which I'm doing) 3. Ability to use that score to then make the best move choice (this is the issue)
EDIT I wanted to add a 'walk through' of the calls being made within my program, in case you wanted to run my code through Visual Studio and test it out.
In Program.fs is where my code starts, and when it calls ComputerPlayerTurn() then it will use Game.fs, where ComputerPlayerTurn() is called then will initialize the variable let mutable computerMove to = MakeBestMove(board). After MakeBestMove(board) is called, within the function is where MiniMax(board) marker is called.
The following code is where the behavior issues I'm having are found:
let rec MiniMax(board) marker =
let mutable bestValue = 0
let mutable board = board
let mutable moves = GetListOfMoves(board)
if GameWon(board) marker = true || GetListOfMoves(board).Count = 0 then
bestValue <- EvaluateScore(board)
else
if marker = "X" then
bestValue <- -100
for move in moves do
board <- ModifyBoard(board) move marker
bestValue <- max(MiniMax(board) "O")(bestValue)
board <- ModifyBoard(board) move " "
bestValue <- bestValue
else
bestValue <- 100
for move in moves do
board <- ModifyBoard(board) move marker
bestValue <- min(MiniMax(board) "X")(bestValue)
board <- ModifyBoard(board) move " "
bestValue <- bestValue
bestValue
let MakeBestMove (board) marker =
let mutable board = board
let mutable bestMove = 0
let mutable bestValue = 0
let mutable bestMoves = ResizeArray<int>()
let moves = GetListOfMoves(board)
for move in moves do
board <- ModifyBoard(board) move marker
bestValue <- MiniMax(board) "X"
board <- ModifyBoard(board) move " "
if marker = "X" then
if bestValue = 100 then
bestMove <- move
if bestValue > 0 then
bestMoves.Add(move)
else if bestValue = 0 then
bestMoves.Add(move)
elif marker = "O" then
if bestValue = -100 then
bestMove <- move
if bestValue < 0 then
bestMoves.Add(move)
else if bestValue = 0 then
bestMoves.Add(move)
if bestMove = 0 && bestMoves.Count > 0 then
bestMove <- bestMoves.[0]
elif bestMove <> 0 then
bestMove <- bestMove
else
bestMove <- GetListOfMoves(board).[0]
bestMove
My code is on Github on my MASTER branch of my repository: https://github.com/sinnmk/fsharp-tictactoe
The problem is here:
if ((GameWon(board) marker) = true || (moves.Count = 0)) then
It is only considering ties and games where marker wins.
It should also consider games where marker loses:
if GameWon board "O" || GameWon board "X" || moves.Count = 0 then
I removed unnecessary parenthesis and conditions like = true.