Компьютер Отелло
 | |
| NTest — сильная программа othello |
Компьютер Отелло относится к компьютерной архитектуре, включающей компьютерное оборудование и компьютерное программное обеспечение, способное играть в игру Отелло . В частности, он был включен в Microsoft Windows от 1.0 до XP , где он известен просто как Reversi.
Доступность
[ редактировать ]Существует множество программ Othello, таких как NTest , Saio, Edax , Cassio, Pointy Stone, Herakles, WZebra и Logistello загрузить из Интернета , которые можно бесплатно . Эти программы, запущенные на любом современном компьютере , могут играть в игры, в которых легко победить лучших игроков-людей. Это связано с тем, что, хотя последствия ходов предсказуемы как для компьютеров, так и для людей, компьютеры лучше их исследуют. [ 1 ]
Методы поиска
[ редактировать ]Компьютерные программы «Отелло» ищут любые возможные легальные ходы, используя дерево игры . Теоретически они исследуют все позиции/узлы, где каждый ход одного игрока называется «слоем» . Этот поиск продолжается до тех пор, пока не будет достигнута определенная максимальная глубина поиска или пока программа не определит, что достигнута конечная «листовая» позиция.
Наивная реализация этого подхода, известная как Minimax или Negamax , позволяет осуществлять поиск только на небольшую глубину за практический промежуток времени, поэтому были разработаны различные методы, позволяющие значительно увеличить скорость поиска хороших ходов. Они основаны на обрезке Alpha-beta , Negascout , MTD(f) и NegaC*. [ 2 ] Алгоритм алфавита — это метод ускорения процедуры поиска в Минимаксе за счет исключения случаев, которые в любом случае не будут использоваться. Этот метод использует тот факт, что каждый второй уровень в дереве будет максимизироваться, а каждый второй уровень — минимизироваться. [ 3 ]
Для уменьшения размера дерева поиска также используются несколько эвристик: хороший порядок ходов, таблица транспонирования и выборочный поиск. [ 4 ]
Чтобы ускорить поиск на машинах с несколькими процессорами или ядрами, «параллельный поиск» можно реализовать . С игрой Отелло было проведено несколько экспериментов, например ABDADA. [ 5 ] или ТЛЯ [ 6 ] В последних программах YBWC [ 7 ] кажется предпочтительным подходом.
Многозондовая резка
[ редактировать ]Multi-ProbCut — это эвристика, используемая при альфа-бета-обрезке дерева поиска. [ 8 ] Эвристика ProbCut оценивает оценки на более глубоких уровнях дерева поиска, используя линейную регрессию между более глубокими и более мелкими оценками. Multi-ProbCut расширяет этот подход на несколько уровней дерева поиска. Сама линейная регрессия изучается посредством предыдущих поисков по дереву, что делает эвристику своего рода динамическим управлением поиском. [ 9 ] Это особенно полезно в таких играх, как «Отелло» , где существует сильная корреляция между оценками на более глубоком и более поверхностном уровнях. [ 10 ] [ 11 ]
Методы оценки
[ редактировать ]Существует три разные парадигмы создания функций оценки.
Дисково-квадратные столы
[ редактировать ]Разные квадраты имеют разные значения: углы хорошие, а квадраты рядом с углами плохие. Если не учитывать симметрию, на доске имеется 10 различных позиций, и каждой из них присвоено значение для каждой из трех возможностей: черный диск, белый диск и пустой. Более сложный подход заключается в том, чтобы иметь разные значения для каждой позиции на разных этапах игры; например, угловые более важны в дебюте и начале середины игры, чем в эндшпиле. [ 12 ]
На основе мобильности
[ редактировать ]Большинство игроков-людей стремятся максимизировать мобильность (количество доступных ходов) и минимизировать пограничные диски (диски, прилегающие к пустым клеткам). Рассчитываются мобильность игрока и мобильность противника, а также рассчитывается потенциальная мобильность игрока и потенциальная мобильность противника. [ 13 ] Эти меры можно найти очень быстро, и они значительно увеличивают игровую силу. Большинство программ знают конфигурации краев и углов и стараются минимизировать количество дисков в начале середины игры - еще одна стратегия, используемая игроками-людьми. [ 12 ]
Коэффициенты на основе шаблонов/шаблонов
[ редактировать ]Максимизацию мобильности и минимизацию границ можно разбить на локальные конфигурации, которые можно суммировать; обычная реализация состоит в том, чтобы оценить каждую конфигурацию строки, столбца, диагонали и угла отдельно и сложить значения, необходимо оценить множество различных шаблонов. [ 12 ] Процесс определения значений для всех конфигураций осуществляется путем использования большой базы данных игр, сыгранных между сильными игроками, и расчета статистики для каждой конфигурации на каждом этапе игры по всем играм. [ 12 ]
Наиболее распространенный способ прогнозирования окончательной разницы дисков использует взвешенную меру разницы дисков, при которой победившая сторона получает бонус, соответствующий количеству дисков. [ 12 ]
Открытие книги
[ редактировать ]Книги по дебютам помогают компьютерным программам, предоставляя общие дебюты, которые считаются хорошими способами противодействия плохим дебютам. Все сильные программы используют дебютные книги и автоматически обновляют свои книги после каждой игры. Чтобы просмотреть все позиции из всех игр в базе данных игры и определить лучший ход, не сыгранный ни в одной игре из базы данных, таблицы транспозиции используются для записи позиций, которые были найдены ранее. Это означает, что эти позиции не нужно искать снова. [ 12 ] Это отнимает много времени, поскольку для каждой позиции необходимо выполнить глубокий поиск, но как только это будет сделано, обновить книгу будет легко. После каждой сыгранной партии все новые позиции ищутся на предмет наилучшего отклонения.
Другие оптимизации
[ редактировать ]Более быстрое оборудование и дополнительные процессоры могут улучшить возможности программы, играющей в Отелло, например, более глубокий поиск слоев.
Разгадка Отелло
[ редактировать ]Во время игры игроки чередуют ходы. Игрок-человек использует черные фишки, а компьютер — белые. Игрок-человек начинает игру. [ 1 ] Отелло решается на досках 4×4 и 6×6, причем второй игрок (белый) выигрывает в идеальной игре . [ 14 ] [ 15 ]
Отелло 4 × 4
[ редактировать ]Отелло 4х4 имеет очень маленькое дерево игры и решается менее чем за одну секунду многими простыми программами Отелло, использующими метод Минимакс, генерирующий все возможные позиции (около 10 миллионов). В результате белые побеждают с перевесом +8 (3-11). [ 14 ]
Отелло 6 × 6
[ редактировать ]Отелло 6х6 была решена менее чем за 100 часов с помощью множества простых программ Отелло, использующих метод Минимакс, генерирующий все возможные позиции (около 3,6 триллионов). В результате белые побеждают с перевесом +4 (16-20). [ 16 ]
Отелло 8 × 8
[ редактировать ]Размер дерева игры Отелло 8x8 оценивается в 10 54 узлов, а количество легальных позиций оценивается менее чем в 10 28 . По состоянию на октябрь 2023 года в препринте утверждается, что игра решена и оптимальным результатом является ничья. [ 17 ] [ 18 ] Также публикуются результаты вычислений, что делает эту книгу одной из крупнейших общедоступных книг. [ 19 ]
Некоторые ведущие программы уже много лет расширяют свои списки. В результате многие линии на практике представляют собой ничьи или победы для обеих сторон. Что касается трех основных дебютов: диагонального, перпендикулярного и параллельного, то оказывается, что как диагональный, так и перпендикулярный дебюты приводят к рисованию линий, в то время как параллельный дебют является победой для черных. Дерево рисунка также кажется больше после диагонального открытия, чем после перпендикулярного. [ 20 ] [ не удалось пройти проверку ] Параллельное начало имеет серьезные преимущества для черного игрока, позволяя черным всегда выигрывать в идеальной игре. [ 21 ] [ не удалось пройти проверку ]
Вехи в компьютерном Отелло
[ редактировать ]| а | б | с | д | и | ж | г | час | ||
| 1 | 
|
|
|
|
|
|
|
|
1 |
| 2 |
|
|
|
|
|
|
|
|
2 |
| 3 |
|
|
|
|
|
|
|
|
3 |
| 4 |
|
|
|
|
|
|
|
|
4 |
| 5 |
|
|
|
|
|
|
|
|
5 |
| 6 |
|
|
|
|
|
|
|
|
6 |
| 7 |
|
|
|
|
|
|
|
|
7 |
| 8 |
|
|
|
|
|
|
|
|
8 |
| а | б | с | д | и | ж | г | час |
- 1977 : Scientific American сделал самую раннюю известную опубликованную ссылку на программу Отелло/Реверси, написанную NJD Jacobs в BCPL . [ 22 ] В октябре BYTE опубликовала «Отелло, новую древнюю игру» как программу ввода текста на BASIC . [ 23 ]
- 1977 : Creative Computing опубликовала версию «Отелло», написанную Эдом Райтом на FORTRAN . [ 24 ] [ 25 ]
- 1978 : Nintendo выпускает видеоигру Computer Othello для игровых автоматов . [ 26 ]
- 1980 : Программа «Отелло» «Мавр» (написанная Майком Ривом и Дэвидом Леви ) выиграла одну игру в матче из шести игр против чемпиона мира Хироши Иноуэ. [ 27 ] Питер Фрей из Северо-Западного университета обсудил компьютерные и человеческие стратегии Отелло в BYTE , а также обсудил свою игру TRS-80 Othello, которая, как утверждал Фрей, легко победила версию Райта, работающую на CDC 6600 . [ 25 ] Пол Розенблум из Университета Карнеги-Меллон разработал IAGO , который занял третье место на компьютерном турнире Северо-Западного университета. [ 28 ] Когда IAGO играл в The Moor, IAGO лучше справлялся с постоянным захватом фигур и ограничением подвижности противника. [ 27 ]
- 1981 : IAGO, бегущий на DEC KA10, финишировал впереди 19 других участников Открытого турнира Отелло в Санта-Крус в Калифорнийском университете в Санта-Крус , установив единственный непобежденный рекорд. Игра Чарльза Хита на основе TRS 80 заняла второе место. Микрокомпьютерные процессоры заняли места со второго по седьмое, опередив несколько мэйнфреймов и миникомпьютеров; Фрей предположил, что это произошло потому, что компьютер Отелло не пользуется некоторыми преимуществами более крупных компьютеров, такими как более быстрая арифметика с плавающей запятой . [ 28 ]
- Конец 1980-х : Кай-Фу Ли и Санджой Махаджан создали программу «Отелло» BILL , которая была похожа на IAGO, но включала байесовское обучение. БИЛЛ уверенно победил ЯГО. [ 27 ]
- 1992 : Майкл Буро начал работу над программой «Отелло» Logistello . Методы поиска, функция оценки и база знаний шаблонов Logistello были лучше, чем в более ранних программах. Logistello усовершенствовала свою игру, сыграв против себя более 100 000 игр. [ 27 ]
- 1997 : Логистелло выиграл все игры в матче из шести игр против чемпиона мира Такеши Мураками. Хотя не было особых сомнений в том, что программы «Отелло» сильнее людей, прошло 17 лет с момента последнего матча между компьютером и действующим чемпионом мира. После матча 1997 года сомнений уже не было: Логистелло был значительно лучше любого игрока-человека. [ 29 ] [ 27 ]
- 1998 : Майкл Буро ушел из Logistello. Исследовательский интерес к «Отелло» несколько угас, но некоторые программы, в том числе Ntest, Saio, Edax, Cassio, Zebra и Herakles, продолжали развиваться. [ 27 ]
- 2004 : Ntest стала сильнейшей программой, значительно сильнее Logistello.
- 2005 : Ntest, Saio, Edax, Cyrano и Zebra стали значительно сильнее Logistello. Ntest и Zebra ушли на пенсию.
- 2011 : Saio , Edax и Cyrano стали намного быстрее Logistello и других программ.
- 2022 : Эгаруцид выглядит как мощный двигатель, вдохновленный Edax.
- 2023 : Отелло решен с использованием слегка модифицированного Edax. Egaroucid публикует данные о самостоятельной игре. [ 30 ]
Список лучших программ Отелло / Реверси
[ редактировать ]- NTest ( Ntest ) Криса Велти
- Edax ( Edax Архивировано 6 апреля 2013 г. в Wayback Machine ), Ричард Делорм
- Logistello ( Логистелло ) Майкла Буро
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Jump up to: а б «Dcs.gla.ac.uk» (PDF) . Архивировано из оригинала (PDF) 3 января 2011 года.
- ^ Жан-Кристоф Вайль (1992). Поиск NegaC*. Журнал ICCA, Vol. 15, № 1, стр. 3-7.
- ^ Арманто, Хендраван; Сантосо, Джоан; Джованни, Даниэль; Курниаван, Фарис; Юдианто, Рики; Гунаван, Стивен (октябрь 2012 г.). «Эволюционная нейронная сеть для игры Отелло» . Procedia — Социальные и поведенческие науки . 57 : 419–425. дои : 10.1016/j.sbspro.2012.09.1206 .
- ^ Буро, М., «Эксперименты с Multi-ProbCut и новой высококачественной оценочной функцией для Отелло» , «Игры в исследованиях искусственного интеллекта» , Х.Дж. ван ден Херик, Х. Иида (ред.), ISBN 90-621-6416-1 , 2000 г.
- ^ Жан-Кристоф Вайль (1996). Алгоритм распределенного минимаксного поиска ABDADA. Материалы конференции ACM по информатике 1996 г., стр. 131–138. ACM, Нью-Йорк, штат Нью-Йорк, переиздано ICCA Journal Vol. 19, № 1
- ^ Марк Брокингтон (1997). KEYANO Unplugged - Построение программы Отелло. Технический отчет TR-97-05, факультет вычислительной техники, Университет Альберты.
- ^ Райнер Фельдманн, Питер Мысливиц, Буркхард Моньен (1991). Полностью распределенная шахматная программа. Достижения в компьютерных шахматах 6
- ^ Буро, Майкл (1997). «Эксперименты с Multi-ProbCut и новой функцией высококачественной оценки для Отелло» . Игры в исследованиях искусственного интеллекта . 34 (4): 77–96.
- ^ Булитко, Вадим; Люстрек, Митя; Шеффер, Джонатан; Бьернссон, Ингви; Сигмундарсон, Сверрир (1 июня 2008 г.). «Динамическое управление при эвристическом поиске в реальном времени» . Журнал исследований искусственного интеллекта . 32 : 419–452. дои : 10.1613/jair.2497 .
- ^ Фюрнкранц, Йоханнес (2001). Машины, которые учатся играть в игры | Путеводители . Nova Science Publishers, Inc.6080 Иерихон Тпке. Suite 207 Commack, Нью-Йорк, США: Nova Science Publishers, Inc., стр. 11–59. ISBN 978-1-59033-021-0 .
{{cite book}}: CS1 maint: местоположение ( ссылка ) - ^ Хайнц, Эрнст А. (2013). Масштабируемый поиск в компьютерных шахматах: алгоритмические усовершенствования и эксперименты с большой глубиной поиска . Springer Science & Business Media. п. 32. ISBN 978-3-322-90178-1 .
- ^ Jump up to: а б с д и ж Гуннар Андерссон (2007). «Написание программы Отелло» . radagast.se . Проверено 12 февраля 2023 г.
- ↑ Как работает Ntest. Архивировано 9 ноября 2011 г. в Wayback Machine , 2 марта 2005 г.
- ^ Jump up to: а б Решение Отелло 4 × 4. Архивировано 7 июля 2011 г. в Wayback Machine , 2 сентября 2008 г.
- ↑ Идеальная игра в Отелло 6х6 с двух альтернативных стартовых позиций. Архивировано 1 ноября 2009 г., в Wayback Machine, 17 ноября 2004 г.
- ^ Ф. Питтнер (июль 2006 г.). «Домашняя страница Тотелло» . www.tothello.com . Проверено 12 февраля 2023 г.
- ^ «Отелло раскрыт» (PDF) . Проверено 4 ноября 2023 г.
- ^ Такидзава, Хироки. "обратные скрипты " Гитхаб . Получено 4 ноября.
- ^ «Анализ игры позиций Отелло» . Проверено 4 ноября 2023 г.
- ^ «Сильнейшая программа Отелло с точки зрения искусственного интеллекта» . Архивировано из оригинала 9 января 2007 г. Проверено 5 апреля 2010 г.
- ^ «Проект SaioApp — самый сильный движок Отелло» . Проверено 12 февраля 2023 г.
- ^ Гарднер, Мартин. Математический отдых. Scientific American, апрель 1977 г.
- ^ Дуда, Ричард О (октябрь 1977 г.). «Отелло, новая старинная игра» . БАЙТ . стр. 60–62.
- ^ Райт, Эд (ноябрь – декабрь 1977 г.). «Отелло» . Творческие вычисления . стр. 140–142 . Проверено 18 октября 2013 г.
- ^ Jump up to: а б Фрей, Питер В. (июль 1980 г.). «Моделирование принятия решений человеком на персональном компьютере» . БАЙТ . п. 56 . Проверено 18 октября 2013 г.
- ^ «Компьютер Отелло — видеоигра от Nintendo» .
- ^ Jump up to: а б с д и ж «История компьютерных игр» (PDF) . Архивировано из оригинала (PDF) 24 января 2011 года.
- ^ Jump up to: а б Фрей, Питер В. (июль 1981 г.). «Открытый турнир Санта-Крус / Отелло для компьютеров» . БАЙТ . п. 16 . Проверено 18 октября 2013 г.
- ^ Майкл Буро (20 августа 1997 г.). «Отелло-матч года» . skatgame.net . Проверено 12 февраля 2023 г.
- ^ Ямана, Такуто. «Стенограммы самостоятельной игры Эгаруцида» . Отелло А. И. Эгаруцид . Получено 5 ноября.
Внешние ссылки
[ редактировать ]