(примечание: это не домашнее задание по CS)
Я попытался реализовать алгоритм поиска минимаксного игрового дерева в Coffeescript и продолжаю получать ошибки с моим алгоритмом. По-видимому, есть 2 основные проблемы: 1) сам алгоритм, кажется, не возвращает правильное значение во время альфа-бета-обрезки (очевидно, более серьезная проблема), и 2) мой объект игрового поля, представленный массивом из 9 целых чисел, кажется быть прикрепленным к DOM, что делает проблематичным дублирование платы и передачу ее в качестве параметра рекурсивным вызовам функции минимаксного поиска.
Есть 3 класса: доска, бот (где живет алгоритм минимакс) и игра. Имейте в виду, что новая игра запускается при загрузке (соответственно появляются всплывающие уведомления об отладке) и что доска имитируется с предварительно настроенными играми для облегчения отладки.
Вы заметите, что я предпринял три отдельных попытки минимаксного решения (неделями в свободное время ломал голову над этим), последние две теперь закомментированы. В своем окончательном решении я следовал этому псевдокоду.
index.html
<!DOCTYPE html>
<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]-->
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<title>Tic Tac Toe | JMS</title>
<meta name="description" content="Tic-tac-toe using the minimax algorithm">
<meta name="viewport" content="width=device-width">
<link rel="stylesheet" href="css/normalize.min.css">
<link rel="stylesheet" href="css/main.css">
<script src="js/vendor/modernizr-2.6.2-respond-1.1.0.min.js"></script>
</head>
<body>
<h1 id="output">empty</h1>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js"></script>
<script>window.jQuery || document.write('<script src="js/vendor/jquery-1.9.0.min.js"><\/script>')</script>
<!-- <script src="js/main.js"></script> -->
<script src="js/rules.js"></script>
<script src="js/board.js"></script>
<script src="js/game.js"></script>
<script src="js/bot.js"></script>
<!-- <script>
var _gaq=[['_setAccount','UA-XXXXX-X'],['_trackPageview']];
(function(d,t){var g=d.createElement(t),s=d.getElementsByTagName(t)[0];
g.src=('https:'==location.protocol?'//ssl':'//www')+'.google-analytics.com/ga.js';
s.parentNode.insertBefore(g,s)}(document,'script'));
</script> -->
</body>
</html>
доска.кофе
class Board
constructor: ->
@spaces = [0,1,2,3,4,5,6,7,8]
reset: ->
@spaces = [0,1,2,3,4,5,6,7,8]
setSpace: (index, side) ->
console.log "board.setSpace: played at index #{index} with side #{side}"
@spaces[index] = side
$('#output').text(@spaces)
setSpaces: (array) ->
@spaces = array
getSpace: (index) ->
@spaces[index]
getSpaces: ->
@spaces
бот.кофе
class Bot
constructor: (side) ->
console.log "created a new bot!"
@name = "Gandalf"
@infinity = 99
@side = side
calculateMove: (board) ->
console.log "Bot.calculateMove with #{board.getSpaces()}"
debugger
isBoardEmpty = (board) -> # works
console.log "Bot.calculateMove: board is #{board.getSpaces()}"
boardSpaces = board.getSpaces()
for space in boardSpaces
console.log "Bot.calculateMove: checking if space #{space} is empty"
if typeof space is "string"
console.log "Bot.calculateMove: board isn't empty"
return false
return true
return 4 if isBoardEmpty(board)
boardCopy = jQuery.extend({}, board) # this copies the board
# but still refers to the same spaces
# in the copy. Necessary?
console.log "about to call Bot.move"
move = @search(boardCopy, @side, 0, -@infinity, +@infinity)
return move
search: (board, side, depth, alpha, beta)->
# needs to return the index of the move
debugger
##### TRY 1 #####
#################
value = @nodeValue(board, side)
if value isnt 0
if value > 0 then return value - depth else return value + depth
otherside = if side is 'X' then 'O' else 'X'
moves = @generateMoves board
boardSpaces = board.getSpaces()
boardCopy = new Board()
boardCopy.setSpaces(boardSpaces)
if side is 'O'
for move in moves
boardCopy.setSpace(move, side)
score = @search(boardCopy, otherside, depth + 1, beta, alpha)
alpha = score if score > alpha
@undoMove(boardCopy, move)
return alpha if alpha >= beta
if side is 'X'
for move in moves
boardCopy.setSpace(move, side)
score = @search(boardCopy, otherside, depth + 1, beta, alpha)
beta = score if score < beta
@undoMove(boardCopy, move)
return beta if alpha >= beta
##### TRY 2 #####
#################
# value = @nodeValue(board, side)
# console.log "Bot.search: depth is #{depth}"
# console.log "Bot.search: value is #{value}"
# if value isnt 0
# if value > 0 then return value - depth else return value + depth
# moves = @generateMoves board
# return value if moves.length is 0
# otherside = if side is 'X' then 'O' else 'X'
# for move in moves
# console.log "Bot.search: #{move} in moves"
# boardSpaces = board.getSpaces()
# boardCopy = new Board()
# boardCopy.setSpaces(boardSpaces) # This could be rolled into a optional argument
# # on the board constructor
# @makeMove(boardCopy, move, side)
# potentialAlpha = -@search(board, otherside, depth + 1, -beta, -alpha)
# @undoMove(boardCopy, move) # THINK ITS SOMETHING WITH THE BOARD BEING USED
# break if beta <= alpha
# if potentialAlpha > alpha
# alpha = potentialAlpha
# if depth is 0
# bestMove = move
# if depth isnt 0 then return alpha else return bestMove
##### TRY 3 #####
#################
# value = @nodeValue(board, side)
# console.log "Bot.search: depth is #{depth}"
# console.log "Bot.search: value is #{value}"
# if value isnt 0
# if value > 0 then return value - depth else return value + depth
# moves = @generateMoves board
# return value if moves.length is 0 # ?
# otherside = if side is 'X' then 'O' else 'X'
# boardSpaces = board.getSpaces()
# boardCopy = new Board()
# boardCopy.setSpaces(boardSpaces) # This could be rolled into a optional argument
# # on the board constructor
# if side is 'O'
# for move in moves
# boardCopy.setSpace(move, side)
# score = @search(boardCopy, otherside, depth + 1, beta, alpha)
# alpha = score if score > alpha
# return alpha if alpha >= beta
# break if beta > alpha
# else
# for move in moves
# boardCopy.setSpace(move, side)
# score = @search(boardCopy, otherside, depth + 1, beta, alpha)
# beta = score if score < beta
# return beta if alpha >= beta
# break if alph > beta
nodeValue: (board, side) ->
console.log "Bot.nodeValue: board is #{board.getSpaces()} and side is #{side}"
gameResult = checkGameOver board
console.log "Bot.nodeValue: gameResult is #{gameResult}"
if gameResult is false or gameResult is 'tie'
console.log "returning 0 for nodeValue"
return 0
else if gameResult is side
console.log "returning #{@infinity} for nodeValue"
return @infinity
else
console.log "returning #{-@infinity} for nodeValue"
return -@infinity
generateMoves: (board) ->
console.log "Bot.generateMoves: board is #{board.getSpaces()}"
moves = []
boardSpaces = board.getSpaces()
for space in boardSpaces
if typeof space is "number"
moves.push(space)
console.log "Bot.generateMoves: moves are #{moves}"
return moves
makeMove: (board, move, side) ->
console.log "makeMove: board before makeMove with move #{move} is #{board.getSpaces()}"
board.setSpace(move, side)
# board[move] = side
console.log "makeMove: board after makeMove is #{board.getSpaces()}"
return board #####
undoMove: (board, move) ->
console.log board.getSpaces()
boardSpaces = board.getSpaces()
board.setSpace(move, move)
console.log board.getSpaces()
return board
# minimax = (player, board) ->
# minimax (player, board) ->
# winner if gameOver(currentPosition)
правила.кофе
checkGameOver = (board) ->
opportunities = 8
result = false
check = (space) ->
board.getSpace(space)
winningCombinations = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],
[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
for combo in winningCombinations
firstPlay = combo[0]
secondPlay = combo[1]
thirdPlay = combo[2]
if typeof check(firstPlay) is "string" and
typeof check(secondPlay) is "string" and
typeof check(thirdPlay) is "string"
opportunities -= 1
console.log "checkGameOver: opportunities decreased to #{opportunities}"
if check(firstPlay) is check(secondPlay) is check(thirdPlay)
alert "Winner is #{board.getSpace(firstPlay)}"
return result = board.getSpace(firstPlay)
if opportunities is 0
alert "tie"
return result = "tie"
return result
игра.кофе
class Game
constructor: ->
@board = new Board()
$('#output').text(@board.getSpaces())
new: ->
@board.reset()
@result = false
@side = "X"
@bot = new Bot "O"
@moves = 0
firstTurn: ->
# Production
# space = prompt "What space are you playing?"
# @makeMove space
# Testing
@board.setSpaces ['X',1,2,3,'O',5,6,7,8] # Testing – Bot should output 1 for calMove
@makeMove 2
makeMove: (space) =>
@board.setSpace(space, @side)
@moves += 1
@concludeTurn()
listenForMove: ->
space = prompt "What space are you playing?"
@makeMove space
concludeTurn: ->
@result = checkGameOver @board
console.log "Result is #{@result}"
if @result is 'X' or @result is 'O' or @result is 'tie'
alert "Game.concludeTurn: game is over, heading into gameOver"
return @gameOver @result
@changeTurn()
changeTurn: ->
@side = if @side is 'X' then 'O' else 'X'
console.log "in change turn, side is now #{@side}"
@listenForMove() if @side is 'X'
console.log "Game.changeTurn: bot (#{@bot}) is about to calc move"
@makeMove(@bot.calculateMove @board) if @side is 'O'
# placement = @bot.calculateMove @board if @side is 'O'
# console.log placement
# @board.setSpace(placement, 'O') # give a secondary argument to makeMove and remove
# @concludeTurn()
gameOver: (winner) ->
console.log "Game.concludeTurn: winner is #{@result}"
return
# answer = prompt "Winner is #{winner}! Would you like to play again?"
# @playAgain answer
# playAgain: (answer) ->
# alert "Suite yourself" if answer is false
# @new() if answer is true
# check if game is over
# check moves
# if even then human
# else
# bot
#
# increment moves?
# reset grid
# turn = "X"
# move = 0
g = new Game()
g.new()
g.firstTurn()
Очень благодарен за любую помощь.
