Playing Connect 4?

Question

Материал из Википедии:

Connect Four с тех пор была решена с грубыми силовыми методами, начиная с работы Джона Тромп в составлении базы данных 8-слойный [4] [8] (4 февраля 1995). Алгоритмы искусственного интеллекта, способные сильно разрешить Connect Four, являются минимаксными или негамаксными, с оптимизациями, которые включают альфа-бета-обрезку, динамическое упорядочение истории движений игрового игрока и таблицы транспонирования. Код для решения Connect Four с этими методами также является основой для целочисленного теста производительности Fhourstones.

Я пытался ускорить мой алгоритм Connect 4, который в настоящее время использует Minimax вместе с обрезкой Alpha-Beta и таблицей транспонирования. Я хочу сделать это быстрее, поэтому решил добавить «динамический порядок истории игровых движений».

Что такое «динамический порядок истории игрового игрока»? Я искал ее, но не нашел ресурсов, которые объясняли это. Может кто-нибудь объяснить эту концепцию, и, если возможно, расскажите, как сильно ускорить скорость, которую я должен ожидать?

Answer 1

Посмотреть этот ответ: Dynamic move ordering. Таблицы транспозиций используются для выполнения динамического упорядочения перемещения:

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

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

(PS -. Если ваш код в Java, вы можете попробовать его на моем Java game page, хотя в настоящее время он имеет очень простой алгоритм)