컴퓨터 브리지

Computer bridge

컴퓨터 브릿지는 컴퓨터 소프트웨어를 사용하여 게임 계약 브릿지를 하는 것입니다.20세기 말경부터 컴퓨터 브리지 분야는 몇 년 동안 제한적인 발전을 거듭해 왔습니다.1996년, American Contract Bridge League(ACBL)는 매년 주요 브리지 이벤트와 함께 개최되는 공식 월드 컴퓨터 브리지 챔피언십을 설립했습니다.첫 번째 챔피언십은 1997년 앨버커키에서 열린 북미 브리지 챔피언십에서 열렸다.1999년부터 이 행사는 미국 계약 브리지 리그와 세계 브리지 연맹의 공동 활동으로 진행되어 왔다.ACBL 이사회 멤버인 Alvin Levy는 이 챔피언십을 시작하였고 창립 이후 매년 행사를 조정해왔다.이벤트 이력, 기사 및 출판물, 분석, 플레이 기록은 공식 홈페이지에서 확인할 수 있습니다.

세계 컴퓨터 브리지 챔피언십

월드 컴퓨터 브리지 챔피언십은 보통 라운드로빈으로 진행되며 상위 4명의 참가자들 [1][2]간의 녹아웃이 뒤따른다.연간 이벤트 수상자는 다음과 같습니다.

  • 1997년 브리지 바론
  • 1998년 GIB
  • 1999년 GIB
  • 2000년 메도우락 다리
  • 2001년 잭
  • 2002년 잭
  • 2003년 잭
  • 2004년 잭
  • 2005 Wbridge 5
  • 2006년 잭
  • 2007 Wbridge 5
  • 2008년 Wbridge5
  • 2009년 잭
  • 2010년 잭
  • 2011년 상어 브릿지
  • 2012년 잭
  • 2013년 잭
  • 2014년 상어 브릿지
  • 2015년 잭
  • 2016년 Wbridge5[3]
  • 2017 Wbridge[4] 5
  • 2018 Wbridge[5] 5
  • 2019[6] 마이크로브릿지
  • 2020년 우승이 취소되었습니다.
  • 2021년 챔피언십이 취소되었습니다.

컴퓨터 대 인간

지아 마흐무드의 책 "브릿지, 마이웨이"(1992)에서 지아는 자신이 선택한 4인조 팀이 컴퓨터에 지지 않을 것이라는 1백만 파운드의 내기를 제안했다.몇 년 후 미국의 컴퓨터 과학자 매튜 긴스버그가 [8]고안한 브릿지 프로그램 GIB(Ginsberg's Intelligent Bridge Player 또는 Goren In a Box)[7]는 플레이 테스트에서 윙클 스퀴즈처럼 전문적인 클리어 플레이를 할 수 있음을 증명했다.1996년 지아는 내기를 철회했다.2년 후, GIB는 컴퓨터 브리지 세계 챔피언이 되었고, 1998년 파 콘테스트에서 34명의 최고 인간(지아 마흐무드 [9]포함)과 비교해서도 랭킹 12위(11210점)를 기록했습니다.그러나 이러한 파 콘테스트는 기술 브릿지 분석 능력만을[clarification needed] 측정하는 것으로 1999년 지아는 개인 라운드 로빈 경기에서 [10]GIB를 포함한 다양한 컴퓨터 프로그램을 이겼다.

컴퓨터 브리지 분야에서 한층 더 진보함에 따라 Jack과 Wbridge5를 [12]포함한 보다 강력한 브리지 재생 프로그램이 탄생했습니다.이 프로그램들은 국가 교량 순위에서 높은 순위를 차지하고 있다.2005년과 2006년에 발표된 네덜란드 브리지 잡지 IMP에 실린 일련의 기사는 컴퓨터 브리지 세계 챔피언인 잭과 버뮤다 볼 우승자와 두 명의 유럽 챔피언을 포함한 7개의 네덜란드 최고의 페어 간의 경기를 묘사하고 있다.총 196개의 보드가 연주되었다.잭은 7쌍 중 3쌍(유럽 챔피언 포함)을 이겼다.전체적으로 이 프로그램은 385 IMP에 [volume & issue needed]비해 근소한 차이로 패배했습니다.

2009년, 숙련된 선수인 필립 마틴은 챔피언 브리지 프로그램인 잭과 경기하는 4년간의 프로젝트를 시작했다.그는 한 테이블에서 한 손을, 잭은 다른 세 손을, 잭은 다른 테이블에서 네 자리 모두에서 같은 카드를 꺼내 비교 결과를 도출했다.그는 가고일 [13]연대기라는 제목의 블로그에 결과와 분석을 게재했다.그 프로그램은 모든 대회에서 큰 차이로 우승한 마틴에게는 상대가 되지 않았다.

카드 플레이 알고리즘

브릿지는 체스나 바둑 같은 보드게임과는 다른 도전장을 던진다.특히 브릿지는 불완전한 정보의 확률적 게임이다.거래 개시시에, 각 참가자가 이용할 수 있는 정보는, 자신의 카드만으로 한정됩니다.입찰 및 후속 플레이 중에 테이블에서 다른 3명의 플레이어의 입찰을 통해 더 많은 정보를 얻을 수 있으며, 테이블 위에 디클리어(더미)의 파트너(더미)의 카드가 오픈되어 각 트릭으로 플레이된다.그러나 완전한 정보를 얻을 수 있는 것은 플레이가 끝날 때뿐입니다.

오늘날의 최상위 교량 프로그램은 미지의 손을 나타내는 많은 샘플을 생성함으로써 이러한 확률론적 특성을 다룬다.각 샘플은 무작위로 생성되지만 입찰 및 플레이에서 지금까지 사용 가능한 모든 정보와 호환되도록 제한됩니다.다음으로, 각 샘플에 대한 최적의 방어에 대해 서로 다른 플레이 라인의 결과를 테스트합니다.이 테스트는 광범위한 검색 알고리즘을 사용하여 쌍방의 최적의 플레이 라인을 결정하는 이른바 "더블 더미 솔버"를 사용하여 수행됩니다.모든 샘플에 대해 평균이 가장 높은 점수를 생성하는 플레이 라인이 최적의 플레이로 선택됩니다.

효율적인 더블 덤미 솔버는 브리지 플레이 프로그램을 성공시키기 위한 열쇠입니다.또한 표본 크기에 따라 계산량이 증가함에 따라 중요도 샘플링과 같은 기법을 사용하여 최소 크기이지만 여전히 대표적인 표본 세트를 생성합니다.

다른 전략 게임과의 비교

브릿지는 불완전한 정보 게임이지만, 더블덤 해결사는 완벽한 정보가 있는 게임의 단순화된 버전을 분석한다.입찰은 무시되고 계약서(트럼프 슈트와 디클리어)가 주어지며, 모든 플레이어는 처음부터 모든 카드를 알고 있다고 가정한다.따라서 해결사는 체스, 바둑, 역전과 같은 2인용 완벽한 정보의 승/패/추첨 게임을 해결하는 데 일반적으로 사용되는 많은 게임 트리 검색 기술을 사용할 수 있습니다.그러나 몇 가지 중요한 차이가 있습니다.

  • 더블 더미 브릿지는 실제로는 두 명의 일반 플레이어 간의 경기이지만, 각 "선수"는 두 손을 제어하고 네 명의 선수를 반영하는 올바른 순서로 카드를 플레이해야 한다. (네 명의 선수 중 누가 트릭을 이기고 다음 트릭을 이끌어야 하는지 차이가 있다.)
  • 더블더미 브릿지는 단순히 승/패/추첨이 아니라 정확히 제로섬이 아니라 두 팀이 13개의 트릭을 놓고 경쟁하기 때문에 연속 합산이다.연속섬 게임을 제로섬 게임으로 바꾸는 것은 사소한 일이다.또한 일반 계약 브리지의 목표(및 리스크 관리 전략)는 계약뿐만 아니라 토너먼트 형태에 따라 달라집니다.그러나 더블 덤 버전은 결정론적이기 때문에 목표는 간단하다. 즉, 일반성을 잃지 않고 취한 트릭의 수를 최대화하는 것을 목표로 할 수 있다.
  • 브릿지는 점증적으로 점수가 매겨집니다.각 플레이되는 트릭은 승패의 관점에서 최종적인 "점수"에 불가역적으로 기여합니다.경기가 끝날 때까지 최종 승부가 다소 열린 게임과는 대조적이다.브리지에서는 이미 결정된 트릭이 알파 베타 프루닝의 자연스러운 하한과 상한을 제공하며 검색이 깊어질수록 간격이 자연스럽게 줄어듭니다.다른 게임은 일반적으로 알파 베타 가지치기를 제한된 깊이에서 활성화하기 위해 인위적인 평가 기능이 필요하거나 가지치기가 가능하기 전에 리프 노드를 검색해야 합니다.
  • 더블더미 솔버에서 다양한 포지션의 "확실한 승자"를 계산하는 것은 비교적 저렴합니다.이 정보를 통해 플루닝이 개선됩니다.이것은 일종의 평가 함수라고 볼 수 있지만, 다른 게임에서 후자는 포지션 값의 근사치이지만, 전자는 포지션 값의 최종 하한치이다.
  • 더블더미 게임 트리 탐색 과정에서는 특정 위치에서 외관상 동일한 가치를 가진 카드로 이루어진 동등 클래스를 확립할 수 있다.서브트리 검색에서는 각 동등성 클래스의 카드를 1장만 고려할 필요가 있습니다.또한 치환 테이블을 사용할 경우 동등성 클래스를 이용하여 히트율을 향상시킬 수 있습니다.이것은 Matthew Ginsberg에 의해 파티션 검색으로 설명되었습니다.
컴퓨터 과학에서 해결되지 않은 문제:

더블 더미 브리지에서 승자를 결정하는 문제는 복잡도 클래스에서 어려운가요?

(컴퓨터 사이언스의 미해결 문제 증가)
  • 복잡도 클래스에서 많은 전략 게임이 입증되었습니다. 즉, 복잡도 클래스의 모든 문제는 다항식 시간에 해당 문제로 축소될 수 있습니다.예를 들어, 일반화 x × x 체스는 EXPTIME-complete(EXPTIME과 EXPTIME-hard에서 모두)로 입증되었으며, 이는 사실상 EXPTIME의 가장 어려운 문제 중 하나임을 의미한다. 그러나 보드 게임과 달리 이중 덤미 브리지에서 사용할 수 있는 자연 구조가 없기 때문에 경도의 문제는 남아 있다.를 클릭합니다.[14]

미래

컴퓨터 체스에 비해 컴퓨터 브릿지는 세계 최고 수준까지는 이르지 못했지만 최고의 로봇들은 꾸준히 높은 수준의 플레이를 보여주고 있다.(최근 몇 년간 www.computerbridge.com에서 실시한 분석 결과를 참조하십시오.)그러나 Philippe Pionchon의 기사(1984년) 아래를 참조하십시오.그러나 컴퓨터 체스는 프로그래머들에게 인간과 같은 지능을 제공하는 기계를 만드는 것에 대해 거의 가르치지 않았지만 브리지와 같은 보다 직관적이고 확률적인 게임이 더 나은 시험장을 제공할 수 있다.

브릿지 플레이 프로그램이 가까운 미래에 세계적인 수준에 도달할 수 있을지에 대한 질문은 대답하기 쉽지 않다.컴퓨터 브릿지는 컴퓨터 체스에 비해서도 관심을 끌지 못했다.반면에, 이 분야에서 일하는 연구자들에 의해 지난 10년 동안 많은 진전이 있었다.

브리지 로봇의 게임 수준과 상관없이, 컴퓨터 브릿지는 이미 게임의 분석을 바꾸어 놓았다.시판되고 있는 더블 덤미 프로그램은, 통상, 4개의 손이 모두 알려진 브리지의 문제를 몇 분의 1초만에 해결할 수 있습니다.오늘날 책과 잡지의 편집자들은 출판 전에 다리 문제를 분석하기 위해 인간에만 의존하지 않을 것이다.또한 점점 더 많은 브리지 플레이어 및 코치들이 경기 후 컴퓨터 분석을 사용하고 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ ACBL/WBF 월드 컴퓨터 브리지 챔피언십 공식 사이트
  2. ^ 세계 컴퓨터 브리지 챔피언십 - 참가자 목록 및 링크
  3. ^ "20th Ourgame World Computer-Bridge Championship". World Computer-Bridge Championship. Retrieved 3 November 2019.
  4. ^ "21st World Computer-Bridge Championship". World Computer-Bridge Championship. Retrieved 3 November 2019.
  5. ^ "22nd World Computer-Bridge Championship". World Computer-Bridge Championship. Retrieved 3 November 2019.
  6. ^ "23rd World Computer-Bridge Championship December 2-7, 2019 San Francisco, CA, USA at the ACBL's NABC". World Computer-Bridge Championship. Retrieved 14 December 2019.
  7. ^ 브리지 베이스 온라인 도움말
  8. ^ 긴스버그 프로파일
  9. ^ "Rosenberg Wins Par Contest" (PDF).
  10. ^ 인간 대 기계 서문 - 웨이백 머신에서 아카이브된 밀레니엄의 브리지 매치 2006-05-14
  11. ^ 잭 홈페이지
  12. ^ WBridge5 홈페이지(프랑스어)
  13. ^ "The Gargoyle Chronicles: Board 1". 15 September 2009.
  14. ^ Hearn, Robert Aubrey (2006). Games, puzzles, and computation (Doctoral).

외부 링크