Подсчет стабильных дисков в Отелло

Question

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

Я могу легко сосчитать куски 'edge stable', но я не уверен, как учесть другие из них. Я использую 1-D массив для представления доски.

Ценю любые советы по этому поводу!

Answer 1

Хм, это относится к вашей структуре данных, я думаю.Чтобы проверить, является ли кусок стабильным, вы должны проверить, все ли поля рядом с ним (горизонтальное, вертикальное, диагональное) соответствуют одному из следующих правил:

• Это граница
• Этостабильный фрагмент того же цвета
• Он находится в заполненном ряду

Как вы это проверите, зависит от вашей структуры данных.Возможно, вы можете выбрать двумерный массив, чтобы у вас была «картинка» ближе к реальной игровой доске, матрица 8x8.

Answer 2

из http://en.wikipedia.org/wiki/Reversi

"как правило, кусок стабилен, когда по всем четырем осям (горизонтальная, вертикальная и каждая диагональ) находится на границе в заполненном ряду,или рядом со стабильным кусочком того же цвета. "

Вы уже упомянули границы - заполненные строки можно проверить, просто посчитав кусочки, хотя здесь, вероятно, есть много оптимизаций, например, найтисначала заполняются строки, а затем отмечают каждую позицию в полной строке как потенциально стабильную, вместо того, чтобы выполнять итерацию по каждой позиции, а затем проверять все соответствующие направления, что приведет к напрасным усилиям.

Эта страница содержит более подробную информацию о расчете стабильности.

Если вы заинтересованы в компьютере Отелло, обязательно посмотрите публикации на Logistello , который был (вхотя бы несколько лет назад) чемпион мира.Автор, Майкл Буро, написал свою кандидатскую диссертацию на эту тему.Исходный код теперь доступен, так что вы можете проверить используемые структуры данных.По памяти, я думаю, он использовал троичные числа (то есть значения черный, белый, пустой), чтобы обеспечить быстрый поиск, а также поддерживал состояние различных шаблонов (строк, столбцов, диагоналей, углов и т. Д.), Чтобы ускорить функцию оценки.