为什么我的极小极大算法不会撤消每一步?
问题描述:
我正在为我制作的原创4人棋盘游戏创建AI。关于棋盘游戏为什么我的极小极大算法不会撤消每一步?
详情:
4名球员轮流同时移动他们的有色件在四个主要方向之一。碎片可以从板上移开。每个玩家在开始时都有5条生命。对于从棋盘上移走的棋子,玩家会失去1点生命。新作品将在整个游戏中确定性地产生。
我抬起头如何做一个minimax算法,发现this。我通读了这篇文章,并认为我理解了所有内容,所以我试图将第1.5节中的Java代码翻译成Swift。
这里是我的思维过程:
- 由于我的游戏有4名球员,我会像对待其他人尽量减少球员。
- 在Java代码中,有一行代表移动。由于我的游戏的游戏状态在每次移动中都会发生剧烈变化,因此我只会将所有游戏状态存储在数组中,并且在需要撤消某些操作时,我可以在数组上调用
dropLast
。 - 由于在我的游戏中的移动被表示为
Direction
枚举,我将返回一个(Int, Direction)
元组,而不是像Java代码那样的int数组。 -
game
是计算属性,它只是返回gameStates.last!
-
game.currentPlayer
我每次调用上game
的moveUp/Down/Left/Right
方法之一,时间会改变,所以我不需要编写额外的代码来决定谁是未来的球员。 - 在最后一行,我需要返回
(bestScore, bestDirection)
,但我意识到有时bestDirection
未分配。所以我做了bestDirection
一个可选。如果它没有在返回语句中分配,我只会返回任意方向。
这里是我的尝试:
private func minimax(depth: Int, color: Color) -> (score: Int, direction: Direction) {
var bestScore = color == myColor ? Int.min : Int.max
var currentScore: Int
var bestDirection: Direction?
if game.players.filter({$0.lives > 0}).count < 2 || depth == 0 {
// This is a call to my heuristic evaluation function
bestScore = evaluateHeuristics()
} else {
// if the player has no pieces on the board, just move up since moving in any direction won't change anything
for move in (game.board.indicesOf(color: color).count == 0 ? [Direction.up] : [Direction.up, .down, .left, .right]) {
let gameCopy = game.createCopy()
switch move {
case .up: gameCopy.moveUp()
case .down: gameCopy.moveDown()
case .left: gameCopy.moveLeft()
case .right: gameCopy.moveRight()
}
gameStates.append(gameCopy)
// myColor is like mySeed in the original Java code
if color == myColor {
currentScore = minimax(depth: depth - 1, color: game.currentPlayer.color).score
if currentScore > bestScore {
bestScore = currentScore
bestDirection = move
}
} else {
currentScore = minimax(depth: depth - 1, color: game.currentPlayer.color).score
if currentScore < bestScore {
bestScore = currentScore
bestDirection = move
}
}
_ = gameStates.dropLast()
}
}
return (bestScore, bestDirection ?? .left)
}
当我与4的depth
测试这个AI,似乎无论做愚蠢的举动,如移动他的棋子落板,或将他的件只在一个方向。
我也注意到当递归调用返回时,gameStates
的长度约为90。通常它应该是1对吗?因为在递归调用返回时,AI尝试的所有移动都应该被撤消,并且gameStates
将只包含初始状态。
我做错了什么?
答
dropLast()返回一个包含除数组最后一个元素以外所有元素的数组。它不会修改原始数组。使用removeLast()
编辑
你真正想要的是一个堆栈数据结构。这是一个。
public struct Stack<Element>
{
fileprivate var elements: [Element] = []
public init() {}
/// Push an element onto the top of the stack
///
/// - parameter newElement: The element to push
public mutating func push(_ newElement: Element)
{
elements.append(newElement)
}
/// Pops the top element off the stack
///
/// - returns: The top element or nil if the stack is empty.
public mutating func pop() -> Element?
{
let ret = elements.last
if ret != nil
{
elements.removeLast()
}
return ret
}
/// The top element of the stack. Will be nil if the stack is empty
public var top: Element?
{
return elements.last
}
/// Number of items in the stack
public var count: Int
{
return elements.count
}
/// True if the stack is empty
public var isEmpty: Bool
{
return elements.isEmpty
}
}
我不相信这个代码甚至会编译。 'minimax'被声明为返回一个元组'(得分:Int,方向:方向)',但是你把结果赋给一个'Int'。 – JeremyP
另外,除非我误解了游戏规则,否则移动应该包含一个方向列表,其中每个棋子都有一个,但是您只是返回一个方向。 – JeremyP
@JeremyP不,我访问了'.score'元素的最后一行。 – Sweeper