El puente de computadora es el juego del puente de contrato de juego usando software de computadora. Después de años de progreso limitado, desde finales del siglo XX, el campo del puente informático ha logrado importantes avances. En 1996, la American Contract Bridge League (ACBL) estableció un Campeonato Mundial de Bridge de Computadoras oficial, que se celebrará anualmente junto con un importante evento de bridge. El primer campeonato tuvo lugar en 1997 en el North American Bridge Championships en Albuquerque. Desde 1999, el evento se ha realizado como una actividad conjunta de la American Contract Bridge League y la World Bridge Federation.. Alvin Levy, miembro de la Junta de ACBL, inició este campeonato y ha coordinado el evento anualmente desde su inicio. El historial de eventos, artículos y publicaciones, análisis y registros de reproducción se pueden encontrar en el sitio web oficial.
Campeonato Mundial de Computadora-Bridge
El Campeonato Mundial de Bridge de Computadoras se juega típicamente como un round robin seguido de un nocaut entre los cuatro mejores concursantes. [1] [2] Los ganadores del evento anual son:
- 1997 Bridge Baron
- 1998 GIB
- 1999 GIB
- 2000 Puente Meadowlark
- 2001 Jack
- 2002 Jack
- 2003 Jack
- 2004 Jack
- 2005 Wbridge5
- 2006 Jack
- 2007 Wbridge5
- 2008 Wbridge5
- 2009 Jack
- 2010 Jack
- Puente de tiburones 2011
- 2012 Jack
- 2013 Jack
- Puente de tiburones 2014
- 2015 Jack
- 2016 Wbridge5 [3]
- 2017 Wbridge5 [4]
- 2018 Wbridge5 [5]
- Micro Puente 2019 [6]
- El campeonato 2020 ha sido cancelado
Computadoras versus humanos
En el libro de Zia Mahmood , Bridge, My Way (1992), Zia ofreció una apuesta de £ 1 millón a que ningún equipo de cuatro personas de su elección sería derrotado por una computadora. Unos años más tarde, el programa puente GIB (que puede significar "Ginsberg's Intelligent Bridgeplayer" o " Goren In a Box"), [7] creación del científico informático estadounidense Matthew Ginsberg, [8] demostró ser capaz de realizar jugadas de declaradores expertos como winkle aprieta en pruebas de juego. En 1996, Zia retiró su apuesta. Dos años más tarde, GIB se convirtió en el campeón mundial en bridge de computadora, y también tuvo un puntaje en el puesto 12 (11210) en el juego de declaradores en comparación con 34 de los mejores humanos en el Concurso Par de 1998 (incluida Zia Mahmood). [9] Sin embargo, este concurso de pares mide las habilidades técnicas de análisis de puentes sólo [ aclaración necesaria ] , y en 1999 Zia venció a varios programas de computadora, incluido GIB , en un partido de todos contra todos. [10]
Un mayor progreso en el campo del bridge de computadora ha dado como resultado programas de juego de bridge más fuertes, incluidos Jack [11] y Wbridge5 . [12] Estos programas han obtenido una alta calificación en las clasificaciones nacionales de puentes. Una serie de artículos publicados en 2005 y 2006 en la revista holandesa de bridge IMP describe los enfrentamientos entre el cinco veces campeón mundial de bridge por computadora Jack y siete parejas holandesas importantes, incluido un ganador del Bermuda Bowl y dos campeones europeos reinantes. Se jugaron un total de 196 tableros. Jack derrotó a tres de las siete parejas (incluidos los campeones de Europa). En general, el programa perdió por un pequeño margen (359 frente a 385 IMP ). [ volumen y problema necesarios ]
En 2009, Phillip Martin, un jugador experto, comenzó un proyecto de cuatro años en el que jugó contra el programa campeón de bridge, Jack. Jugó una mano en una mesa, con Jack jugando las otras tres; en otra mesa, Jack jugó las mismas cartas en los cuatro asientos, produciendo un resultado comparativo. Publicó sus resultados y análisis en un blog que tituló The Gargoyle Chronicles . [13] El programa no fue rival para Martin, quien ganó todos los concursos por amplios márgenes.
Algoritmos de juego de cartas
Bridge plantea desafíos a sus jugadores que son diferentes de los juegos de mesa como el ajedrez y el go . En particular, el bridge es un juego estocástico de información incompleta. Al comienzo de un trato, la información disponible para cada jugador se limita a sus propias cartas. Durante la subasta y el juego posterior, se dispone de más información a través de la subasta de los otros tres jugadores en la mesa, las cartas del compañero del declarante (el muerto) se ponen abiertas sobre la mesa y las cartas jugadas en cada baza. . Sin embargo, solo al final de la obra se obtiene la información completa.
Los programas de bridge de alto nivel actuales tratan con esta naturaleza probabilística generando muchas muestras que representan las manos desconocidas. Cada muestra se genera al azar, pero se limita a ser compatible con toda la información disponible hasta el momento de la licitación y el juego. A continuación, el resultado de las diferentes líneas de juego se compara con la defensa óptima para cada muestra. Esta prueba se realiza utilizando un "solucionador de doble simulación" que utiliza amplios algoritmos de búsqueda para determinar la línea de juego óptima para ambas partes. La línea de juego que genera la mejor puntuación promediada sobre todas las muestras se selecciona como la jugada óptima.
Los solucionadores eficientes de doble simulación son clave para el éxito de los programas de juego de bridge. Además, a medida que aumenta la cantidad de cálculo con el tamaño de la muestra, se utilizan técnicas como el muestreo por importancia para generar conjuntos de muestras que son de tamaño mínimo pero aún representativas.
Comparación con otros juegos de estrategia
Mientras que el bridge es un juego de información incompleta, un solucionador de doble simulación analiza una versión simplificada del juego donde hay información perfecta ; se ignora la subasta, se da el contrato (palo de triunfo y declarante) y se asume que todos los jugadores conocen todas las cartas desde el principio. Por lo tanto, el solucionador puede usar muchas de las técnicas de búsqueda de árbol de juegos que se usan típicamente para resolver juegos de ganar / perder / empatar con información perfecta de dos jugadores, como ajedrez , ir y revertir . Sin embargo, existen algunas diferencias significativas.
- Aunque el bridge de doble simulación es en la práctica una competencia entre dos jugadores generalizados, cada "jugador" controla dos manos y las cartas deben jugarse en un orden correcto que refleje a cuatro jugadores. (Hace una diferencia cuál de las cuatro manos gana una baza y debe liderar la siguiente baza).
- El puente de doble simulación no es simplemente ganar / perder / empatar y no es exactamente una suma cero , sino una suma constante, ya que dos bandos compiten por 13 bazas. Es trivial transformar un juego de suma constante en un juego de suma cero. Además, el objetivo (y la estrategia de gestión de riesgos) en el puente de contrato general depende no solo del contrato sino también de la forma del torneo. Sin embargo, dado que la versión de doble simulación es determinista, el objetivo es simple: uno puede sin perder la generalidad apuntar a maximizar el número de trucos realizados.
- El puente se puntúa de forma incremental; cada baza jugada contribuye irreversiblemente a la "puntuación" final en términos de bazas ganadas o perdidas. Esto contrasta con los juegos en los que el resultado final es más o menos abierto hasta que termina el juego. En el puente, los trucos ya determinados proporcionan límites inferiores y superiores naturales para la poda alfa-beta , y el intervalo se reduce de forma natural a medida que la búsqueda se profundiza. Otros juegos suelen necesitar una función de evaluación artificial para permitir la poda alfa-beta a una profundidad limitada, o deben buscar un nodo de hoja antes de que sea posible la poda.
- Es relativamente económico calcular "ganadores seguros" en varias posiciones en un solucionador de doble simulación. Esta información mejora la poda. Puede considerarse como una especie de función de evaluación , sin embargo, mientras que la última en otros juegos es una aproximación del valor de la posición, la primera es un límite inferior definitivo en el valor de la posición.
- Durante el transcurso de la búsqueda del árbol de juego de doble simulación, se pueden establecer clases de equivalencia que consisten en cartas con un valor aparentemente igual en una posición particular. Solo se debe considerar una tarjeta de cada clase de equivalencia en la búsqueda del subárbol y, además, cuando se usa una tabla de transposición , las clases de equivalencia se pueden explotar para mejorar la tasa de aciertos. Esto ha sido descrito como búsqueda de particiones por Matthew Ginsberg.
¿Es difícil el problema de decidir el ganador en el puente de doble simulación en alguna clase de complejidad ?
- Numerosos juegos de estrategia han demostrado ser difíciles en una clase de complejidad , lo que significa que cualquier problema en esa clase de complejidad se puede reducir en tiempo polinómico a ese problema. Por ejemplo, el ajedrez x × x generalizado se ha probado EXPTIME -completo (tanto en EXPTIME como en EXPTIME -hard), lo que significa que se encuentra entre los problemas más difíciles de EXPTIME . Sin embargo, dado que no existe una estructura natural para explotar en el puente de doble simulación hacia una prueba o refutación de dureza, a diferencia de un juego de mesa, la cuestión de la dureza permanece. [14]
El futuro
En comparación con el ajedrez por computadora , el bridge de computadora no ha alcanzado el nivel de clase mundial, pero los mejores robots han demostrado un nivel de juego consistentemente alto. (Ver análisis de los últimos años de juego en www.computerbridge.com .) Sin embargo, ver más abajo el artículo de Philippe Pionchon (1984). Sin embargo, mientras que el ajedrez por computadora ha enseñado poco a los programadores sobre la construcción de máquinas que ofrecen inteligencia similar a la humana, los juegos más intuitivos y probabilísticos como el bridge podrían proporcionar un mejor campo de pruebas.
La pregunta de si los programas de juego de bridge alcanzarán un nivel de clase mundial en el futuro previsible no es fácil de responder. El puente de la computadora no ha atraído una cantidad de interés cercana al del ajedrez por computadora. Por otro lado, los investigadores que trabajan en este campo han avanzado mucho en la última década.
Independientemente del nivel de juego de los robots de bridge, computer bridge ya ha cambiado el análisis del juego. Los programas de doble simulación disponibles comercialmente pueden resolver problemas de puente en los que se conocen las cuatro manos, normalmente en una fracción de segundo. En estos días, pocos editores de libros y revistas dependerán únicamente de los humanos para analizar los problemas de los puentes antes de las publicaciones. Además, cada vez más jugadores de bridge y entrenadores utilizan el análisis por computadora en la autopsia de un partido.
Ver también
- Lista de premios de informática
- Olimpiada informática
- Método de Montecarlo
- Búsqueda de árboles de Montecarlo
- Muestreo de importancia
- Hanabi (juego de cartas)
Referencias
- ^ Sitio oficial del Campeonato Mundial de Bridge de Computadoras ACBL / WBF
- ^ Campeonato Mundial de Bridge de Computadoras - Lista de concursantes y sus enlaces
- ^ "20º Campeonato Mundial de Bridge de Computadoras de Ourgame" . Campeonato Mundial de Computadora-Bridge . Consultado el 3 de noviembre de 2019 .
- ^ "21º Campeonato Mundial de Computadoras-Bridge" . Campeonato Mundial de Computadora-Bridge . Consultado el 3 de noviembre de 2019 .
- ^ "22º Campeonato Mundial de Computadoras-Bridge" . Campeonato Mundial de Computadora-Bridge . Consultado el 3 de noviembre de 2019 .
- ^ "23º Campeonato Mundial de Computadoras-Bridge 2-7 de diciembre de 2019 San Francisco, CA, EE. UU. En el NABC de la ACBL" . Campeonato Mundial de Computadora-Bridge . Consultado el 14 de diciembre de 2019 .
- ^ Ayuda en línea de Bridge Base
- ^ Perfil de Ginsberg
- ^ "Rosenberg gana el concurso Par" (PDF) .
- ^ Prólogo de Hombre contra máquina: el combate puente del milenio Archivado el 14 de mayo de 2006 en la Wayback Machine.
- ^ Página de inicio de Jack
- ^ Página de inicio de WBridge5 (en francés)
- ^ [1]
- ^ Hearn, Robert Aubrey (2006). Juegos, puzzles y computación (Doctoral).
enlaces externos
- Campeonato Mundial de Bridge por Computadora - campeonato mundial de bridge-bot de ACBL / WBF (sitio web oficial)
- BridgeGuys. "Software Computer Bridge que participa en el World Computer Bridge Championship y la historia de estos programas de software" (PDF) . Archivado desde el original (PDF) el 8 de noviembre de 2016.
- Ginsberg, Matthew L. "GIB: Pasos hacia un programa de Bridge-Playing de nivel experto". CiteSeerX 10.1.1.52.2188 . Cite journal requiere
|journal=
( ayuda ) - Bethe, Paul M (14 de enero de 2010). "El estado del Bridge Play automatizado" (PDF) .
- Philippe Pionchon (1984). "Juego de inteligencia artificial y Bridge" . Revisión de Le Bridgeur . Análisis clásico de IA aplicado al bridge.