优化Scala代码片段

我仍然在学习Scala，并决定实施一个黑白棋游戏。我使用Alpha Beta修剪，基于这个algorithm来实现AI组件。优化Scala代码片段

但是我意识到我的执行效率不高。如果我将算法的最大深度增加到5以上，我会开始注意性能问题。我意识到搜索空间是指数级的，所以我希望能够帮助我指出优化此代码的方法。

下面是如何实现的算法：

trait MaxMin 
case class Max() extends MaxMin 
case class Min() extends MaxMin 

object AlphaBeta { 

    type Move = List[State] 
    type FitnessMove = Tuple2[Int, List[Move]] 

    def not(p: Player) = p match { 
    case _: Player2 => Player1() 
    case _: Player1 => Player2() 
    } 

    def max(x: FitnessMove, y: FitnessMove) = if (x._1 >= y._1) x else y 
    def min(x: FitnessMove, y: FitnessMove) = if (x._1 <= y._1) x else y 
    def terminal(turn: Int) = if (turn >= 64) true else false 

    def search(board: Board, player: Player, turn: Int, MAX_DEPTH: Int = 5): Move = { 
    def alphaBeta(node: Board, depth: Int, alpha: Int, beta: Int, 
     moveChoice: List[Move], player: Player, p: MaxMin, turn: Int): FitnessMove = 
     if (depth == 0 || terminal(turn)) 
     (player.evalHeuristic(node, turn), moveChoice) 
     else 
     p match { 
      case _: Max => 
      player.getPossibleMoves(node). 
      takeWhile(_ => beta > alpha). // Pruning 
      foldLeft((alpha, moveChoice)) { case ((alpha, moveChoice), move) => 
       val simulate = player.simulateMove(node, move) 
       max((alpha, moveChoice), 
       alphaBeta(simulate, depth-1, alpha, beta, 
        move :: moveChoice, not(player), Min(), turn+1)) 
      } 
      case _: Min => 
      player.getPossibleMoves(node). 
      takeWhile(_ => beta > alpha). // Pruning 
      foldLeft((beta, moveChoice)) { case ((beta, moveChoice), move) => 
       val simulate = player.simulateMove(node, move) 
       (
       min((beta, moveChoice), 
        alphaBeta(simulate, depth-1, alpha, beta, 
        moveChoice, not(player), Max(), turn+1))._1, 
        moveChoice 
      ) 
      } 
     } 
    val (_, moveChoice) = alphaBeta(board, MAX_DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE, List.empty[Move], player, Max(), turn) 
    if (!moveChoice.isEmpty) moveChoice.head 
    else player.getPossibleMoves(board).head 
    } 

}

，如果我使用while循环和一个更加“势在必行”的做法，但我更愿意保持不变的代码，我大概可以得到更好的性能。我可以在代码上做出什么改进，或者你会以不同方式处理整个算法的实现？

这是game如果你想检查出来。谢谢！

来源

2013-03-17 Samuel Heaney

只是如果你是感兴趣：前段时间我写了一个基于小控制台的Othello实现，没有AI：https：//gist.github.com/sschaef/2472666 – sschaef 2013-03-17 01:04:33

你能否确保你附加一个测试，以便我可以自由地重构你的代码而不会中断其功能？ – Edmondo1984 2013-03-17 02:45:24

嗨@ Edmondo1984是的，我会尝试尽快添加一些测试。 – 2013-03-17 19:49:54

我没有分析所有的代码，但是有一点上面显得很“可疑”

player.getPossibleMoves(node). 
     takeWhile

所以我想：好 - 如果他真的在这里得到所有的移动列表然后过滤，这可能是非常低效的。这是你实现这确实与产量

def findPossibleMoves(playerDisk: Int): List[Move] = 
    groupStatesByMove { 
     (for { 
     i <- upperLimit to lowerLimit 
     j <- leftLimit to rightLimit 
     if repr(i)(j) == 0 
     dir <- 1 to 8 
     disk = getPlayerDisk(i, j, dir) 
     if disk == playerDisk && findMove(i, j, dir)(playerDisk) 
     } yield new State(i, j, dir, playerDisk)).toList 
    }

实际工作现在 - 如果你只是做回键入Iterable（应为takeWhile和除通过索引直接访问其他大多数列表的操作就足够了 - 看IterableLike），如果在最后（也在Player的调用函数中）省略了toList，则输出会自动设置为输入类型 - 在这种情况下将列出输入类型，因为x to y会生成一个列表。这里的诀窍是使用Stream来代替1 to 8，而不是使用(1 to 8).toStream。所有其他to表达式也是如此。然后，每个State只应在需要时生成 - 所以：直到takeWhile返回false。

下面是一个例子：

object TakeTest extends App { 
    def generate : Iterable[Int] = { 
    for (j <- (1 to 10).toStream; if (println("generate: " + j) ==())) 
     yield j 
    } 
    println("takeWhile with list:") 
    generate.toList.takeWhile(_ < 3) 
    println("takeWhile with Stream/Iterable:") 
    generate.takeWhile(_ < 3).toList 
}

这是唯一的线索，我可以从代码给，否则我会用 - 你或许应该先熟悉它：jvisualvm

来源

2013-03-17 05:50:18

感谢您的指点，我绝对忽略了每次获得可能的动作时都会生成整个集合的部分。 – 2013-03-17 20:57:44

优化Scala代码片段

回答

相关问题