Компьютерный мост

Компьютерный бридж — это игра в контрактный бридж с использованием компьютерного программного обеспечения. После нескольких лет ограниченного прогресса, примерно с конца 20-го века, в области компьютерных мостов были достигнуты значительные успехи. В 1996 году Американская лига контрактного бриджа (ACBL) учредила официальный чемпионат мира по компьютерному бриджу, который будет проводиться ежегодно вместе с крупным мероприятием по бриджу. Первый чемпионат состоялся в 1997 году на чемпионате Северной Америки по бриджу в Альбукерке. С 1999 года мероприятие проводится как совместное мероприятие Американской лиги контрактного бриджа и Всемирной федерации бриджа . Элвин Леви, член правления ACBL, инициировал этот чемпионат и ежегодно координирует его с момента его создания. Историю мероприятия, статьи и публикации, анализ и игровые записи можно найти на официальном сайте.

Чемпионат мира по компьютерному бриджу

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

• 1997 Бридж Барон
• 1998 ГИБ
• 1999 ГИБ
• 2000 Мост Медоуларк
• 2001 Джек
• 2002 Джек
• 2003 Джек
• 2004 Джек
• 2005 Wbridge5
• 2006 Джек
• 2007 Wbridge5
• 2008 Wbridge5
• 2009 Джек
• 2010 Джек
• 2011 Акулий мост
• 2012 Джек
• 2013 Джек
• 2014 Акулий мост
• 2015 Джек
• 2016 Wbridge5
• 2017 Wbridge5
• 2018 Wbridge5
• 2019 Микромост
• 2020- чемпионаты отменены

С 2022 года проводятся «Неофициальные чемпионаты по компьютерному бриджу». Формат представляет собой турнир по круговой системе, за которым следует полуфинал, а затем финал, с подсчетом очков в IMP (и победные очки могут быть использованы для разрешения ничьих). В 2022 году из-за «технических трудностей» круговой турнир был заменен четвертьфиналом.

Победителями ежегодного мероприятия стали:

• 2022 Wbridge 5.12
• 2023 Qplus 15.3
• 2024 год в стадии подготовки

Компьютеры против людей

В Зии Махмуда книге « Мост, мой путь » (1992) Зия предложил ставку в 1 миллион фунтов стерлингов на то, что ни одна выбранная им команда из четырех человек не будет побеждена компьютером. Несколько лет спустя программа бриджа GIB (что может означать либо «Интеллектуальный игрок в бридж Гинзберга», либо « Горен в коробке»), детище американского ученого-компьютерщика Мэтью Гинзберга, доказал свою способность к умелой игре разыгрывающего, например, к подмигиваниям в игровых тестах. В 1996 году Зия отозвал свою ставку. Два года спустя GIB стал чемпионом мира по компьютерному бриджу, а также занял 12-е место (11210) в игре с оператором по сравнению с 34 лучшими людьми в Par Contest 1998 года (включая Зию Махмуда). Однако такое паритетное соревнование оценивает только навыки технического анализа моста. , а в 1999 году Зия обыграла различные компьютерные программы, включая GIB , в индивидуальном круговом матче.

Дальнейший прогресс в области компьютерного бриджа привел к появлению более сильных программ игры в бридж, в том числе Jack и Wbridge5 . Эти программы заняли высокие места в национальных рейтингах бриджей. В серии статей, опубликованных в 2005 и 2006 годах в голландском журнале IMP по бриджу, описываются матчи между пятикратным чемпионом мира по компьютерному бриджу Джеком и семью ведущими голландскими парами, включая победителя Bermuda Bowl и двух действующих чемпионов Европы. Всего было сыграно 196 досок. Джек победил три пары из семи (включая чемпионов Европы). В целом программа проиграла с небольшим отрывом (359 против 385 IMP ).

В 2009 году Филлип Мартин, опытный игрок, начал четырехлетний проект, в котором он играл против чемпиона по программе бриджа Джека. Он играл одну руку за одним столом, а Джек играл за тремя остальными; за другим столом Джек разыграл одни и те же карты на всех четырех местах, получив сравнительный результат. Он опубликовал свои результаты и анализ в блоге, который назвал «Хроники горгульи» . Программа не могла сравниться с Мартином, который выигрывал все соревнования с большим отрывом.

Алгоритмы карточной игры

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

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

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

Сравнение с другими стратегическими играми

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

• Хотя бридж с двойным манекеном на практике представляет собой соревнование между двумя обобщенными игроками, каждый «игрок» контролирует две руки, и карты должны разыгрываться в правильном порядке, отражающем четырех игроков. (Имеет значение, какая из четырех рук выиграет взятку и должна вести следующую взятку.)
• Бридж с двойным манекеном – это не просто выигрыш/проигрыш/ничья и не совсем игра с нулевой суммой , а с постоянной суммой, поскольку две играющие стороны соревнуются за 13 взяток. Превратить игру с постоянной суммой в игру с нулевой суммой тривиально. Более того, цель (и стратегия управления рисками) в генеральном контрактном бридже зависит не только от контракта, но и от формы турнира (из-за различий в системах подсчета очков, влияющих на оптимальную общую стратегию). Однако, как только игра сводится к детерминистическому анализу с двумя манекенами, цель становится простой: можно без потери общности стремиться максимизировать количество взятых уловок.
• Мост оценивается постепенно; каждая сыгранная взятка необратимо влияет на окончательный «счет» с точки зрения выигранных или проигранных взяток. В этом отличие от игр, в которых окончательный результат более или менее открыт до тех пор, пока игра не закончится. В бридже уже определенные приемы обеспечивают естественные нижнюю и верхнюю границы для альфа-бета-отсечения , и интервал естественным образом сокращается по мере углубления поиска. Другим играм обычно требуется искусственная функция оценки , чтобы включить альфа-бета-обрезку на ограниченной глубине, или необходимо выполнить поиск конечного узла, прежде чем обрезка станет возможной.
• Вычислить «верных победителей» в различных позициях в решателе с двойной фикцией относительно недорого. Эта информация улучшает обрезку. Ее можно рассматривать как своего рода функцию оценки , однако, хотя последняя в других играх является приближением значения позиции, первая является окончательной нижней границей значения позиции.
• В ходе поиска по дереву игры с двойной фикцией можно установить классы эквивалентности, состоящие из карт с очевидно равным значением в определенной позиции. При поиске в поддереве необходимо учитывать только одну карту из каждого класса эквивалентности, и, кроме того, при использовании таблицы транспонирования классы эквивалентности можно использовать для повышения вероятности попадания. описал это как поиск разделов . Мэтью Гинзберг

Нерешенная задача в информатике :

ли проблема определения победителя в бридже с двойным манекеном Трудна в любом классе сложности ?

(еще нерешенные проблемы по информатике)

• Многочисленные стратегические игры доказали свою сложность в определенном классе сложности , а это означает, что любая проблема этого класса сложности может быть сведена к этой задаче за полиномиальное время . Например, x × x обобщенные шахматы было доказано, что EXPTIME -полны (как в EXPTIME , так и в EXPTIME -hard), что фактически означает, что это одна из самых сложных задач в EXPTIME . Однако, поскольку в отличие от настольной игры в мосте с двумя манекенами нет естественной структуры, которую можно было бы использовать для доказательства или опровержения твердости, остается вопрос твердости.

Будущее

По сравнению с компьютерными шахматами , компьютерный бридж не достиг мирового уровня, но топовые роботы продемонстрировали стабильно высокий уровень игры. (См. анализ последних нескольких лет игры на сайте www.computerbridge.com .) Однако см. ниже статью Филиппа Пионшона (1984). Тем не менее, хотя компьютерные шахматы мало чему научили программистов в создании машин, обладающих интеллектом, подобным человеческому, более интуитивные и вероятностные игры, такие как бридж, могут стать лучшей испытательной площадкой.

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

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

См. также

• Список наград в области информатики
• Компьютерная олимпиада
• Метод Монте-Карло
• Поиск по дереву Монте-Карло
• Выборка по важности
• Ханаби (карточная игра)

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

• Чемпионат мира по компьютерному бриджу - чемпионат мира по бридж-ботам ACBL / WBF (официальный сайт)
• BridgeGuys (23 октября 2013 г.). «Программное обеспечение, участвующее в чемпионате мира по компьютерному мосту, и история этих программ» (PDF) . Архивировано из оригинала (PDF) 8 ноября 2016 г.
• Гинзберг, Мэтью Л. (1999). «GIB: Шаги к программе игры в бридж на экспертном уровне» . стр. 584–589. CiteSeer ^х :  10.1.1.52.2188 .
• Бете, Пол М. (14 января 2010 г.). «Состояние автоматизированной игры в бридж» (PDF) .
• Филипп Пионшон (1984). «Искусственный интеллект и игра в бридж» . Обзор Ле Бриджёра . Классический анализ ИИ применительно к бриджу.