Минимакс в Scala

Я пытаюсь адаптировать алгоритм минимакс из Википедии для своей реализации TicTacToe в Scala. Я хочу, чтобы игрок X, -1, попытался максимизировать свой счет. Я нашел классную статическую функцию оценки здесь который я хотел бы использовать. Он возвращает положительные числа, если доска хороша для игрока, и отрицательные числа, если доска плоха для игрока. Я попробовал несколько вариантов, и X продолжает делать первый ход доступным. Метод приведен ниже, метод и функцию оценки можно найти здесь.

Есть ли в этом что-то явно очевидное, что я упускаю?

// player X = -1, player O = 1
def minmax(board:Array[Int], height:Int, player:Int):Double={
  if(height == 0)
    evaluatePosition(board, player)

  var alpha = -player * Double.PositiveInfinity;

  val allBoards = makeAllPossibleMoves(board, player) // array of child boards
  for(b <- allBoards){
    val score = minmax(b, height-1, -player)
    alpha = if (player == -1) Math.max(alpha, score) else Math.min(alpha, score)
  }

  alpha
}

artificial-intelligence scala minimax
person Odhran Roche    schedule 30.11.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Кажется, что alpha инициализирован неправильным значением:

var alpha = -player * Double.PositiveInfinity

означает, что в случае X игрока (-1) alpha инициализируется как

var alpha = - (-1) * Double.PositiveInfinity

который можно упростить до

var alpha = Double.PositiveInfinity

Таким образом, альфа больше не может увеличиваться, т.е.

alpha = if (player == -1) Math.max(alpha, score) else //...

не будет иметь никакого эффекта. Обратное должно быть верным для другого игрока (1), где alpha инициализируется отрицательной бесконечностью и, следовательно, больше не может быть мимизировано. Таким образом, вы сможете исправить это, просто удалив фактор -1 из инициализации alpha:

var alpha = player * Double.PositiveInfinity
person Roland Ewald    schedule 30.11.2013
comment
Конечно. Спасибо за ясное объяснение. Мне также пришлось явно возвращать evaluatePosition(board, player), чтобы получить результат. Теперь это работает, но, как ни странно, работает лучше, когда height установлено на 0, чем когда height > 0. Я думаю, что это может быть просто причудой функции оценки. - person Odhran Roche; 30.11.2013