優化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代碼片段

回答

相關問題