Простая структура данных для настольной игры Отелло?

Question

Я делал свою программу давным-давно здесь как универ-проект, по крайней мере, он работает в некоторой степени (вы можете попробовать уровень Обезьяны и Новичка :)).

IЯ хотел бы переработать и повторно внедрить его, чтобы попрактиковаться в структуре данных и алгоритме.

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

Поскольку игровая доска симметрична как по горизонтали, так и по вертикали, мне нужна лучшая структура данных, чем мой предыдущий подход:

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 11 12 13 14 15 16 17 18 -1
-1 21 22 23 24 25 26 27 28 -1
-1 31 32 33 34 35 36 37 38 -1
    . . . . . .

Таким образом, можно легко вычислитьсоседние позиции с любым значением ячейки, подобным этому:

x-11 x-10 x-9
x-1   x   x+1
x+9  x+10 x+11

Эти -1 действуют как «стены» для предотвращения неправильных вычислений.

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

Любое хорошее предложение?Я также собираюсь попробовать ruby, чтобы иметь более быструю скорость вычислений, чем PHP (только для минимального и максимального альфа-бета-сокращения, если я запрограммирую его на n шагов вперед).

Большое спасибо запредложения заранее.

Answer 1

С проблемой легко разобраться, если вы отделите презентацию доски от внутреннего представительства.Как только движение открытия сделано, вы получаете параллельное, диагональное или перпендикулярное отверстие.Каждый из них может быть в любой из 4 ориентаций.Поворачивайте внутреннее представление доски, пока оно не будет совмещено с вашей начальной книгой.Затем просто примите во внимание вращение при рисовании доски.

---

Что касается игры, вам нужно изучить теорию мобильности.Взгляните на книгу Hugo Calendars на эту тему.Также Ник Буро немного написал о своей программе Logistello. Часто задаваемые вопросы

Answer 2

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

Это уменьшает размер вашей базы данных на 8, но увеличивает стоимость хэширования на 8. Является ли это хорошим компромиссом? Это зависит от того, насколько велика ваша база данных и как часто вы выполняете поиск в базе данных.

Answer 3

После того, как вы перейдете на C / C ++ :-), подумайте о представлении игрового поля в качестве «битовых плат», например два 64-битных вектора, например для белого и черного, например struct Board {unsigned long white, black};

С осторожностью вы можете избежать индексации массива для позиций тестируемого элемента и фактически можете параллельно выполнять поиск всех захватов вверх, захватов вправо и т. Д. Из позиции, используя серию битовых логических операторов, сдвигов, и маски, и никаких петель (!). Гораздо быстрее.

Эта идея представления ортогональна вашему квестино о раскрытии симметрии книги.

Счастливого взлома.

Answer 4

Поскольку это параллельное открытие применимо только к самому первому ходу, я бы просто зафиксировал первый ход.

Если вам действительно нужна скорость, я бы порекомендовал C ++.

Я бы также подумал, что проверка места на доске быстрее, чем проверка того, содержит ли пространство -1.