stringtranslate.com

Компьютер Отелло

Компьютер Отелло относится к компьютерной архитектуре, охватывающей компьютерное оборудование и компьютерное программное обеспечение, способное играть в игру Отелло . Он был в частности включен в Microsoft Windows с 1.0 до XP , где он просто известен как Реверси. [ необходима цитата ]

Доступность

Существует множество программ Othello, таких как NTest , Saio, Edax , Cassio, Pointy Stone, Herakles, WZebra и Logistello , которые можно бесплатно загрузить из Интернета . Эти программы, запущенные на любом современном компьютере , могут играть в игры, в которых лучшие игроки-люди легко побеждаются. Это потому, что, хотя последствия ходов предсказуемы как для компьютеров, так и для людей, компьютеры лучше их изучают. [1]

Методы поиска

Программы компьютерного Othello ищут любые возможные законные ходы, используя игровое дерево . Теоретически они проверяют все позиции/узлы, где каждый ход одного игрока называется «ply» . Этот поиск продолжается до тех пор, пока не будет достигнута определенная максимальная глубина поиска или программа не определит, что была достигнута конечная позиция «листа».

Наивная реализация этого подхода, известная как Minimax или Negamax , может искать только на небольшой глубине за практическое количество времени, поэтому были разработаны различные методы, чтобы значительно увеличить скорость поиска хороших ходов. Они основаны на Alpha-beta pruning , Negascout , MTD(f) и NegaC*. [2] Алгоритм alphabeta — это метод ускорения процедуры поиска Minimax путем отсечения случаев, которые в любом случае не будут использоваться. Этот метод использует тот факт, что каждый второй уровень в дереве будет максимизировать, а каждый второй уровень — минимизировать. [3]

Для уменьшения размера искомого дерева также используются несколько эвристик: хороший порядок ходов, таблица транспозиций и выборочный поиск. [4]

Для ускорения поиска на машинах с несколькими процессорами или ядрами может быть реализован «параллельный поиск» . Было проведено несколько экспериментов с игрой Othello, например, ABDADA [5] или APHID [6]. В последних программах YBWC [7] кажется предпочтительным подходом.

Многопробный разрез

Multi-ProbCut — это эвристика, используемая при альфа-бета-обрезке дерева поиска. [8] Эвристика ProbCut оценивает оценки оценок на более глубоких уровнях дерева поиска, используя линейную регрессию между более глубокими и более мелкими оценками. Multi-ProbCut расширяет этот подход на несколько уровней дерева поиска. Сама линейная регрессия изучается на основе предыдущих поисков по дереву, что делает эвристику своего рода динамическим контролем поиска. [9] Она особенно полезна в таких играх, как Othello , где существует сильная корреляция между оценками оценок на более глубоких и более мелких уровнях. [10] [11]

Методы оценки

Существует три различных парадигмы создания функций оценки.

Таблицы диско-квадратные

Разные квадраты имеют разные значения — углы хорошие, а квадраты рядом с углами плохие. Не принимая во внимание симметрию, на доске есть 10 различных позиций, и каждой из них дано значение для каждой из трех возможностей: черный диск, белый диск и пусто. Более сложный подход заключается в том, чтобы иметь разные значения для каждой позиции на разных этапах игры; например, углы более важны в дебюте и начале средней игры, чем в эндшпиле. [12]

На основе мобильности

Большинство игроков-людей стремятся максимизировать мобильность (количество доступных ходов) и минимизировать граничные диски (диски, соседствующие с пустыми квадратами). Мобильность игрока и мобильность противника рассчитываются, а также потенциальная мобильность игрока и потенциальная мобильность противника. [13] Эти меры можно найти очень быстро, и они значительно увеличивают игровую силу. Большинство программ знают о конфигурациях краев и углов и пытаются минимизировать количество дисков в начале игры, еще одна стратегия, используемая игроками-людьми. [12]

Коэффициенты на основе паттернов/паттернов

Максимизацию мобильности и минимизацию границы можно разбить на локальные конфигурации, которые можно складывать вместе; обычная реализация заключается в оценке каждой строки, столбца, диагонали и угловой конфигурации по отдельности и сложении значений, необходимо оценить множество различных шаблонов. [12] Процесс определения значений для всех конфигураций выполняется путем взятия большой базы данных игр, сыгранных между сильными игроками, и расчета статистики для каждой конфигурации на каждом этапе игры из всех игр. [12]

Наиболее распространенный выбор для прогнозирования окончательной разницы дисков — это взвешенная мера разницы дисков, где победившая сторона получает бонус, соответствующий количеству дисков. [12]

Открытие книги

Дебютные книги помогают компьютерным программам, предоставляя общие дебюты, которые считаются хорошими способами противостоять плохим дебютам. Все сильные программы используют дебютные книги и автоматически обновляют свои книги после каждой игры. Чтобы просмотреть все позиции из всех игр в базе данных игр и определить лучший ход, не сыгранный ни в одной игре базы данных, используются таблицы транспозиций для записи позиций, которые были ранее просмотрены. Это означает, что эти позиции не нужно искать снова. [12] Это занимает много времени, так как глубокий поиск должен быть выполнен для каждой позиции, но как только это сделано, обновление книги становится простым. После каждой сыгранной игры все новые позиции ищутся на предмет наилучшего отклонения.

Другие оптимизации

Более быстрое оборудование и дополнительные процессоры могут улучшить возможности программы, играющей «Отелло», такие как более глубокий поиск слоев.

Решение Отелло

В ходе игры игроки ходят по очереди. Игрок-человек использует черные фишки, а компьютер — белые. Игрок-человек начинает игру. [1] Othello сильно решается на досках 4×4 и 6×6, причем второй игрок (белый) выигрывает при идеальной игре . [14] [15]

Отелло 4 × 4

Othello 4x4 имеет очень маленькое игровое дерево и была решена менее чем за одну секунду многими простыми программами Othello, которые используют метод Minimax, который генерирует все возможные позиции (почти 10 миллионов). Результатом является то, что белые выигрывают с перевесом +8 (3-11). [14]

Отелло 6 × 6

Othello 6x6 была решена менее чем за 100 часов многими простыми программами Othello, которые используют метод Minimax, который генерирует все возможные позиции (почти 3,6 триллиона). Результатом является то, что wХайт побеждает с перевесом +4 (16-20). [16]

Отелло 8 × 8

Размер игрового дерева Othello 8x8 оценивается в 10 54 узлов, а количество допустимых позиций оценивается менее чем в 10 28 . По состоянию на октябрь 2023 года в препринте утверждается, что игра была решена, причем оптимальным результатом является ничья. [17] [18] Результаты вычислений также публикуются, что делает ее одной из крупнейших общедоступных книг. [19]

Некоторые ведущие программы расширяли свои книги уже много лет. В результате многие линии на практике ничьей или выигрышем для любой из сторон. Что касается трех основных дебютов диагонали, перпендикуляра и параллели, то, по-видимому, и диагональные, и перпендикулярные открытия ведут к розыгрышу линий, в то время как параллельное открытие является выигрышем для черных. Дерево розыгрыша также кажется больше после диагонального открытия, чем после перпендикулярного открытия. [20] [ неудачная проверка ] Параллельное открытие имеет сильные преимущества для черного игрока, позволяя черным всегда выигрывать в идеальной игре. [21] [ неудачная проверка ]

Вехи в компьютерном Othello

Логистелло против Такеши Мураками (4-я игра)

Список лучших программ Othello/Reversi

  1. NTest (Ntest) Криса Уэлти
  2. Edax (Архив Edax 2013-04-06 на Wayback Machine ) Ричард Делорм
  3. Logistello (Логистелло) Майкла Буро

Смотрите также

Примечания

  1. ^ ab "Dcs.gla.ac.uk" (PDF) . Архивировано из оригинала (PDF) 3 января 2011 г.
  2. ^ Жан-Кристоф Вайль (1992). Поиск NegaC*. Журнал ICCA, т. 15, № 1, стр. 3-7.
  3. ^ Арманто, Хендраван; Сантосо, Джоан; Джованни, Даниэль; Курниаван, Фарис; Юдианто, Рики; Гунаван, Стивен (октябрь 2012 г.). «Эволюционная нейронная сеть для игры Отелло». Procedia — Социальные и поведенческие науки . 57 : 419–425. дои : 10.1016/j.sbspro.2012.09.1206 .
  4. ^ Буро, М., «Эксперименты с Multi-ProbCut и новая функция высококачественной оценки для Othello», Игры в исследованиях ИИ , HJ van den Herik, H. Iida (ред.), ISBN 90-621-6416-1 , 2000 
  5. ^ Жан-Кристоф Вайль (1996). Распределенный алгоритм поиска минимакса ABDADA. Труды конференции ACM Computer Science Conference 1996 года, стр. 131-138. ACM, Нью-Йорк, штат Нью-Йорк, перепечатано в журнале ICCA, том 19, № 1
  6. ^ Марк Брокингтон (1997). KEYANO Unplugged — Построение программы Othello. Технический отчет TR-97-05, Кафедра вычислительной техники, Университет Альберты.
  7. ^ Райнер Фельдманн, Питер Мысливиц, Буркхард Моньен (1991). Полностью распределенная шахматная программа. Достижения в компьютерных шахматах 6
  8. ^ Буро, Майкл (1997). «Эксперименты с Multi-ProbCut и новая функция высококачественной оценки для Othello». Игры в исследованиях ИИ . 34 (4): 77–96.
  9. ^ Булитко, Вадим; Люстрек, Митя; Шеффер, Джонатан; Бьернссон, Ингви; Сигмундарсон, Сверрир (1 июня 2008 г.). «Динамическое управление при эвристическом поиске в реальном времени». Журнал исследований искусственного интеллекта . 32 : 419–452. дои : 10.1613/jair.2497 .
  10. ^ Фюрнкранц, Йоханнес (2001). Машины, которые учатся играть в игры | Путеводители. Nova Science Publishers, Inc. 6080 Jericho Tpke. Suite 207 Commack, NY Соединенные Штаты: Nova Science Publishers, Inc. стр. 11–59. ISBN 978-1-59033-021-0.{{cite book}}: CS1 maint: местоположение ( ссылка )
  11. ^ Хайнц, Эрнст А. (2013). Масштабируемый поиск в компьютерных шахматах: алгоритмические усовершенствования и эксперименты на большой глубине поиска. Springer Science & Business Media. стр. 32. ISBN 978-3-322-90178-1.
  12. ^ abcdef Гуннар Андерссон (2007). «Написание программы «Отелло»». radagast.se . Получено 2023-02-12 .
  13. ^ Как работает Ntest ​​Архивировано 2011-11-09 на Wayback Machine 02 марта 2005 г.
  14. ^ ab Решение Отелло 4 × 4 Архивировано 2011-07-07 на Wayback Machine 02 сентября 2008 г.
  15. ↑ Идеальная игра в 6x6 Othello из двух альтернативных стартовых позиций Архивировано 1 ноября 2009 г., на Wayback Machine 17 ноября 2004 г.
  16. ^ Ф. Питтнер (июль 2006 г.). "Домашняя страница Tothello". www.tothello.com . Получено 12.02.2023 .
  17. ^ "Отелло решен" (PDF) . Получено 2023-11-04 .
  18. ^ Такидзава, Хироки. «реверси-скрипты». Гитхаб . Проверено 4 ноября 2023 г.
  19. ^ "Анализ игры позиций Отелло" . Получено 2023-11-04 .
  20. ^ "Сильнейшая программа Отелло с точки зрения искусственного интеллекта". Архивировано из оригинала 2007-01-09 . Получено 2010-04-05 .
  21. ^ "Проект SaioApp – Самый сильный движок Othello" . Получено 2023-02-12 .
  22. ↑ Гарднер, Мартин. Математические развлечения. Scientific American, апрель 1977 г.
  23. ^ Дуда, Ричард О (октябрь 1977 г.). «Отелло, новая древняя игра». BYTE . стр. 60–62.
  24. ^ Райт, Эд (ноябрь–декабрь 1977 г.). «Отелло». Creative Computing . стр. 140–142 . Получено 18 октября 2013 г.
  25. ^ ab Frey, Peter W (июль 1980 г.). «Имитация принятия решений человеком на персональном компьютере». BYTE . стр. 56 . Получено 18 октября 2013 г. .
  26. ^ «Компьютерный Отелло — Видеоигра от Nintendo».
  27. ^ abcdef "История компьютерных игр" (PDF) . Архивировано из оригинала (PDF) 24 января 2011 года.
  28. ^ ab Frey, Peter W (июль 1981 г.). «The Santa Cruz Open / Othello Tournament for Computers». BYTE . стр. 16 . Получено 18 октября 2013 г. .
  29. ↑ Майкл Буро (20 августа 1997 г.). «Матч года «Отелло»». skatgame.net . Получено 12 февраля 2023 г.
  30. ^ Ямана, Такуто. «Стенограммы самостоятельной игры Эгаруцида». Отелло А. И. Эгаруцид . Проверено 5 ноября 2023 г.

Внешние ссылки

Найдите словосочетание «компьютер отелло» в Викисловаре, бесплатном словаре.