Я уже искал в сети psuedocode, рабочие примеры, проблемы переполнения стека / решения одной и той же области, и я пока не нашел ничего полезного, поэтому я обращаюсь к этому здесь.
Я пытаюсь реализовать алгоритм Minimax в моей игре Tic Tac Toe очень простым способом (без обрезки альфа / бета).Позвольте мне объяснить каждый вспомогательный метод, который у меня есть, и затем я могу поделиться частями моего реального кода, если вам это нужно. Примечание (я НЕ использую глубину при проверке состояния терминала, только проверяю на выигрыш или проверяю на ничью.)
Во-первых, у меня есть утилита MakeBestMove, котораябудет вызван при перемещении компьютера, затем в MakeBestMove вызовет MiniMax, который затем будет вызывать себя до тех пор, пока boardState не достигнет состояния терминала или когда не останется никаких перемещений.
Я хочу, чтобы MakeBestMove возвращал лучший ход, а моя функция MiniMax возвращала счет boardState.
Если вы знакомы с MiniMax, когда состояние является терминальным, состояние оценивается.Я использовал -100 для победы игрока O, 100 для победы игрока X и 0 для ничьей, чтобы выиграть мою игру.Это сделано в моей вспомогательной функции EvaluateScore. У меня также есть функция, которая будет определять доступные ходы на основе текущего состояния игрового поля, чтобы помочь мне перебирать открытые ходы.Также может быть важно отметить, что игрок «X» - это всегда человек, а игрок «O» - это всегда компьютер.
Я пытаюсь использовать тот же подход, который использовал в Python для реализации MiniMax сF #, и теоретически он должен работать, даже если он не лоялен к функциональной парадигме F #.
По той или иной причине он не ведет себя так, как я ожидал.Я провел часы, просматривая каждую строку кода, чтобы убедиться, что у меня не было никаких странных побочных эффектов, но я не добился успеха.Я был бы признателен, если бы кто-то указал мне правильное направление.Я знаю, что написал это очень настоятельно, но я думаю, что это может сработать таким образом, но не могу понять, почему это не так и чего я, возможно, упускаю.Любая помощь с благодарностью!
ВОПРОСЫ ПОВЕДЕНИЯ КОДА: 1. Правильно не возвращается bestMove в MakeBestMove 2. Хотя функция Minimax выглядит так, как будто она работает правильно, рекурсивно повторяя различные терминальные состояния, MakeBestMove не будет блокировать перемещения для "O"но возьму выигрышный ход, когда он будет на расстоянии одного шага.
КАК Я ХОЧУ, ЧТОБЫ СВОЙ КОД ВЕДУТ: 1. Способность правильно набрать BoardState (что, я полагаю, я уже делаю.) 2. Возможность вернуть этооценка, если boardState является терминальным, или если больше не осталось ходов (что я делаю) 3. Возможность использовать этот счет, чтобы затем сделать лучший выбор хода (это проблема)
РЕДАКТИРОВАТЬ Я хотел добавить «обход» вызовов, выполняемых в моей программе, на случай, если вы захотите запустить мой код через Visual Studio и протестировать его.
В Program.fs начинается мой код, и когда он вызывает ComputerPlayerTurn(), он использует Game.fs, где вызывается ComputerPlayerTurn(), затем инициализирует переменную let mutable computerMove to = MakeBestMove(board),После того, как MakeBestMove(board) вызван, внутри функции находится то место, где вызывается MiniMax(board) marker.
В следующем коде я обнаружил проблемы с поведением:
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
Мой код находится на Github в моей MASTER-ветке моего репозитория: https://github.com/sinnmk/fsharp-tictactoe