Подсчет стабильных дисков в Отелло
Я кодирую движок Отелло (реверси), как тренировку для реализации шахматного движка позже. Я хочу посчитать количество стабильных фигур, но не знаю, как это лучше всего сделать.
Я легко могу сосчитать части 'edge stable', но я не уверен, как учесть другие. Я использую 1-D массив для представления платы.
Ценю любые советы по этому поводу!
3 ответа
С http://en.wikipedia.org/wiki/Reversi
"Как правило, фигура является стабильной, когда вдоль всех четырех осей (горизонтальной, вертикальной и каждой диагонали) она находится на границе, в заполненном ряду или рядом со стабильной фигурой того же цвета".
Вы уже упомянули границы - заполненные строки можно проверить, просто посчитав куски, хотя здесь, вероятно, есть много оптимизаций, например, сначала найдите заполненные строки, а затем пометьте каждую позицию в полной строке как потенциально стабильную, а не итерируя по каждая позиция, а затем проверка всех соответствующих направлений, что приведет к напрасным усилиям.
На этой странице есть более подробная информация о расчете стабильности.
Если вы интересуетесь компьютером Отелло, обязательно посмотрите публикации о Логистелло, который был (по крайней мере, несколько лет назад) чемпионом мира. Автор, Майкл Буро, написал свою кандидатскую диссертацию на эту тему. Исходный код теперь доступен, так что вы можете проверить используемые структуры данных. По памяти, я думаю, он использовал троичные числа (то есть значения черный, белый, пустой), чтобы обеспечить быстрый поиск, а также поддерживал состояние различных шаблонов (строк, столбцов, диагоналей, углов и т. Д.), Чтобы ускорить функцию оценки.
Хм, это относится к вашей структуре данных, я думаю. Чтобы проверить, является ли кусок стабильным, вы должны проверить, все ли поля рядом с ним (горизонтальное, вертикальное, диагональное) соответствуют одному из следующих правил:
- Это граница
- Это стабильный кусок того же цвета
- Это в заполненном ряду
Как вы это проверите, зависит от вашей структуры данных. Может быть, вы можете выбрать двумерный массив, чтобы у вас была "картинка" ближе к реальной игровой доске, матрица 8x8.
Прямой ответ
Просто пройдитесь по доске по спирали, отмечая, какие диски оказались стабильными. Если жетон непосредственно примыкает к устойчивому диску того же цвета или непосредственно примыкает к границе во всех четырех направлениях (по горизонтали, вертикали, левой диагонали, правой диагонали), то он будет устойчивым — таково определение стабильный диск.
Пример схемы для спирали:
Если вы столкнулись с «петлей», в которой отсутствуют какие-либо устойчивые диски, вы можете прекратить поиск внутренней спирали, так как устойчивых дисков больше не будет. Более того, для его оптимизации можно сначала проверить, взят ли угол, если нет, то стабильных дисков вообще не будет .
Подробнее об этом можно прочитать в этой исследовательской статье .
Дополнительные мысли
Если вы используете количество стабильных дисков как часть эвристики, не будет ли разумнее также проверить количество нестабильных и полустабильных дисков? В этом случае спираль неприменима и следует проверять устойчивость каждого диска.