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

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

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

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

1997 Мост Барон
1998 GIB
1999 GIB
2000 Мост Медоуларк
2001 Джек
2002 Джек
2003 Джек
2004 Джек
2005 Wbridge5
2006 Джек
2007 Wbridge5
2008 Wbridge5
2009 Джек
2010 Джек
2011 Акулий мост
2012 Джек
2013 Джек
2014 Акулий мост
2015 Джек
2016 Wbridge5^[3]
2017 Wbridge5^[4]
2018 Wbridge5^[5]
2019 Микромост^[6]
Чемпионат 2020 года отменен

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

В Зия Махмуд книга, Мост, мой путь (1992), Зия сделал ставку на 1 миллион фунтов стерлингов, что ни одна из четырех человек по его выбору не проиграет компьютеру. Несколько лет спустя программа моста GIB (что может означать "Интеллектуальный бриджипарт Гинзберга" или "Горен В коробке"),^[7] детище американского ученого-информатика Мэтью Гинзберга,^[8] оказался способным к искусному разыгрыванию игры подмигивать сжимает в игровых тестах. В 1996 году Зия отозвал свою ставку. Два года спустя, GIB стал чемпионом мира по компьютерному бриджу, а также занял 12-е место (11210) в игре разыгрывающих по сравнению с 34 людьми из лучших в конкурсе Par Contest 1998 года (включая Зию Махмуд).^[9] Однако такой номинальный конкурс измеряет только навыки анализа технических мостов.^{[требуется разъяснение ]}, а в 1999 году Зия обыграла различные компьютерные программы, в том числе GIB, в индивидуальном круговом матче.^[10]

Дальнейший прогресс в области компьютерного бриджа привел к появлению более сильных программ для игры в бридж, включая Джек ^[11] и Wbridge5.^[12] Эти программы получили высокие оценки в национальных рейтингах мостов. Серия статей, опубликованных в 2005 и 2006 годах в журнале Dutch Bridge. IMP описывает матчи пятикратного чемпиона мира по компьютерному бриджу Джек и семь лучших голландских пар, включая Бермудская чаша победитель и два действующих чемпиона Европы. Всего было сыграно 196 досок. Джек обыграл три пары из семи (включая чемпионов Европы). В целом программа проиграла с небольшим отрывом (359 против 385 IMP ).^{[объем и выпуск необходим ]}

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

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

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

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

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

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

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

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

Нерешенная проблема в информатике:

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

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

Многочисленные стратегические игры хорошо зарекомендовали себя класс сложности, что означает, что любую проблему в этом классе сложности можно уменьшить за полиномиальное время к этой проблеме. Например, обобщенные $х \times х$ шахматы было доказано $EXPSPACE$ -полный (как в $EXPSPACE$ и $EXPSPACE$ -hard), что фактически означает, что это одна из самых сложных проблем в $EXPSPACE$ . Однако, поскольку в мосту с двумя манекенами нет естественной структуры, которую можно было бы использовать для подтверждения или опровержения твердости, в отличие от настольной игры, остается вопрос твердости.^[14]

Будущее

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

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

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

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

внешняя ссылка

World Computer-Bridge Championship - чемпионат мира по бридж-ботам ACBL / WBF (Официальный веб-сайт)
BridgeGuys. «Участие в программе Computer Bridge Software для чемпионата мира по компьютерному мосту и история этих программ» (PDF). Архивировано из оригинал (PDF) 8 ноября 2016 г.
Гинзберг, Мэтью Л. "GIB: шаги к программе игры в мост на экспертном уровне". CiteSeerX 10.1.1.52.2188. Цитировать журнал требует | журнал = (помощь)
Бете, Пол М. (14 января 2010 г.). "Состояние автоматизированной игры в бридж" (PDF).
Филипп Пионшон (1984). «Искусственный интеллект и игра в мост». Le Bridgeur Обзор. Классический анализ ИИ применительно к мосту.

[1] Официальный сайт чемпионата мира по компьютерному бриджу ACBL / WBF

[2] World Computer Bridge Championship - Список участников и их ссылки

[3] "20-й чемпионат мира по компьютерному бриджу Ourgame". Чемпионат мира по компьютерному бриджу. Получено 3 ноября 2019.

[4] «21-й чемпионат мира по компьютерному бриджу». Чемпионат мира по компьютерному бриджу. Получено 3 ноября 2019.

[5] «22-й чемпионат мира по компьютерному бриджу». Чемпионат мира по компьютерному бриджу. Получено 3 ноября 2019.

[6] «23-й чемпионат мира по компьютерному бриджу, 2-7 декабря 2019 г., Сан-Франциско, Калифорния, США, на NABC ACBL». Чемпионат мира по компьютерному бриджу. Получено 14 декабря 2019.

[7] Онлайн-справка Bridge Base

[Ginsberg-8] Профиль Гинзберга

[9] «Розенберг побеждает в номинальном конкурсе» (PDF).

[10] Предисловие к Человек против машины - Матч тысячелетия В архиве 2006-05-14 на Wayback Machine

[11] Домашняя страница Джека

[12] Домашняя страница WBridge5 (на французском)

[13] [1]

[14] Хирн, Роберт Обри (2006). Игры, головоломки и вычисления (Докторантура).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]