Puente de computadora

El bridge por computadora es el juego de bridge por contrato que se juega con software de computadora. Después de años de progreso limitado, desde finales del siglo XX aproximadamente, el campo del bridge por computadora ha logrado avances importantes. En 1996, la American Contract Bridge League (ACBL) estableció un Campeonato Mundial de Bridge por Computadora oficial, que se celebraría anualmente junto con un evento importante de bridge. El primer campeonato tuvo lugar en 1997 en el Campeonato Norteamericano de Bridge en Albuquerque. Desde 1999, el evento se ha llevado a cabo como una actividad conjunta de la American Contract Bridge League y la World Bridge Federation . Alvin Levy, miembro de la Junta de la ACBL, inició este campeonato y ha coordinado el evento anualmente desde su inicio. El historial del evento, los artículos y publicaciones, los análisis y los registros de juego se pueden encontrar en el sitio web oficial.

El Campeonato Mundial de Bridge por Computadora se juega generalmente con un sistema de todos contra todos seguido de una eliminatoria entre los cuatro mejores concursantes. ^{[1] [2]} Los ganadores del evento anual son:

Desde 2022 se celebran los "Campeonatos no oficiales de bridge por ordenador". ^[7] El formato es un torneo de todos contra todos, seguido de una semifinal y luego una final, con puntuación en IMP (y los puntos de victoria se pueden utilizar para resolver los empates). En 2022, debido a "dificultades técnicas", el torneo de todos contra todos se sustituyó por un torneo de cuartos de final.

Los ganadores del evento anual son:

• Puente W 5.12 2022
• Qplus 2023 15.3
• 2024 en preparación

En el libro de Zia Mahmood , Bridge, My Way (1992), Zia ofreció una apuesta de 1 millón de libras 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 de bridge GIB (que puede significar tanto "Ginsberg's Intelligent Bridgeplayer" como " Goren In a Box"), ^[8] creación del científico informático estadounidense Matthew Ginsberg, ^[9] demostró ser capaz de realizar jugadas de declarante expertas como winkle squeezes en pruebas de juego. En 1996, Zia retiró su apuesta. Dos años más tarde, GIB se convirtió en el campeón mundial de bridge por computadora, y también tuvo una puntuación de 12º lugar (11210) en juego de declarante en comparación con 34 de los mejores humanos en el Concurso Par de 1998 (incluido Zia Mahmood). ^[10] Sin embargo, un concurso de este tipo mide únicamente las habilidades técnicas de análisis del bridge ^{[ aclaración necesaria ]} , y en 1999 Zia venció a varios programas informáticos, incluido GIB , en un partido de todos contra todos individual. ^[11]

Los avances en el campo del bridge por ordenador han dado como resultado programas más potentes para jugar al bridge, como Jack ^[12] y Wbridge5 ^[13] . Estos programas han obtenido altas puntuaciones en los rankings nacionales de bridge. Una serie de artículos publicados en 2005 y 2006 en la revista de bridge holandesa IMP describe partidas entre el cinco veces campeón mundial de bridge por ordenador Jack y siete de las mejores parejas holandesas, entre ellas 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 europeos). En general, el programa perdió por un pequeño margen (359 contra 385 IMP ). ^{[ volumen y número 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, mientras que Jack jugaba las otras tres; en otra mesa, Jack jugó las mismas cartas en los cuatro asientos, lo que produjo un resultado de comparación. Publicó sus resultados y análisis en un blog que tituló The Gargoyle Chronicles . ^[14] El programa no fue rival para Martin, que ganó todas las competiciones por amplios márgenes.

El bridge plantea desafíos a sus jugadores que son diferentes a los de 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 una mano, la información disponible para cada jugador se limita a sus propias cartas. Durante la subasta y el juego posterior, se obtiene 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) que se colocan abiertas sobre la mesa y las cartas jugadas en cada baza. Sin embargo, normalmente solo al final del juego se obtiene la información completa.

Los programas de bridge de alto nivel actuales se ocupan de esta naturaleza probabilística generando muchas muestras que representan las manos desconocidas. Cada muestra se genera de forma aleatoria, pero se limita a ser compatible con toda la información disponible hasta el momento sobre la subasta y el juego. A continuación, se prueba el resultado de diferentes líneas de juego frente a la defensa óptima para cada muestra. Esta prueba se realiza utilizando un denominado "solucionador de doble simulación" que utiliza algoritmos de búsqueda extensivos 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 de doble simulación eficientes son clave para el éxito de los programas 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 sean de tamaño mínimo pero aún así representativos.

Si bien 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 supone que todos los jugadores conocen todas las cartas desde el principio. Por lo tanto, el solucionador puede utilizar muchas de las técnicas de búsqueda de árboles de juego que se utilizan normalmente para resolver juegos de dos jugadores con información perfecta en los que se gana/pierde/empata, como ajedrez , go y reversi . Sin embargo, existen algunas diferencias significativas.

• Aunque el bridge double-dummy es en la práctica una competición entre dos jugadores generalizados, cada "jugador" controla dos manos y las cartas deben jugarse en un orden correcto que refleje a los cuatro jugadores (es importante saber cuál de las cuatro manos gana una baza y debe liderar la siguiente).
• El bridge de doble ficticio no es simplemente ganar/perder/empatar y no es exactamente de suma cero , sino de 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 bridge de contrato general depende no solo del contrato sino también de la forma del torneo (debido a las diferencias en los sistemas de puntuación que afectan a la estrategia general óptima). Sin embargo, una vez que el juego se ha reducido al análisis determinista de doble ficticio, el objetivo es simple: uno puede, sin pérdida de generalidad, intentar maximizar la cantidad de bazas realizadas.
• El bridge se puntúa de forma incremental; cada baza jugada contribuye de forma irreversible a la "puntuación" final en términos de bazas ganadas o perdidas. Esto contrasta con los juegos en los que el resultado final está más o menos abierto hasta que termina el juego. En el bridge, las bazas ya determinadas 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 hace más profunda. Otros juegos suelen necesitar una función de evaluación artificial para permitir la poda alfa-beta a una profundidad limitada, o deben buscar en 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 esta última en otros juegos es una aproximación del valor de la posición, la primera es un límite inferior definitivo del valor de la posición.
• Durante el transcurso de la búsqueda en un á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 carta de cada clase de equivalencia en la búsqueda de subárboles y, además, cuando se utiliza una tabla de transposición , se pueden aprovechar las clases de equivalencia para mejorar la tasa de aciertos. Matthew Ginsberg describió esto como búsqueda de partición .

• 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 polinomial a ese problema. Por ejemplo, el ajedrez x × x generalizado ha demostrado ser EXPTIME -completo (tanto en EXPTIME como EXPTIME -difícil), lo que significa efectivamente que está entre los problemas más difíciles en EXPTIME . Sin embargo, dado que no hay una estructura natural para explotar en el bridge de doble simulación hacia una prueba o refutación de dificultad, a diferencia de un juego de mesa, la cuestión de la dificultad permanece. ^[15]

En comparación con el ajedrez por ordenador , el bridge por ordenador no ha alcanzado un nivel de clase mundial, pero los robots de más alto nivel han demostrado un nivel de juego consistentemente alto. (Véase el análisis de los últimos años de juego en www.computerbridge.com.) Sin embargo, véase más abajo el artículo de Philippe Pionchon (1984). Sin embargo, mientras que el ajedrez por ordenador ha enseñado poco a los programadores sobre la construcción de máquinas que ofrecen una inteligencia similar a la humana, los juegos más intuitivos y probabilísticos como el bridge podrían proporcionar un mejor campo de pruebas.

No es fácil responder a la pregunta de si los programas para jugar al bridge alcanzarán un nivel de clase mundial en un futuro próximo. El bridge por ordenador no ha despertado un interés tan grande como el del ajedrez por ordenador. Por otra parte, los investigadores que trabajan en este campo han logrado grandes avances en la última década.

Independientemente del nivel de juego de los robots de bridge, el bridge por ordenador ya ha cambiado el análisis del juego. Los programas de doble simulación disponibles comercialmente pueden resolver problemas de bridge en los que se conocen las cuatro manos, normalmente en una fracción de segundo. Hoy en día, pocos editores de libros y revistas confían únicamente en humanos para analizar los problemas de bridge antes de su publicación. Además, cada vez más jugadores y entrenadores de bridge utilizan el análisis por ordenador en el análisis posterior de una partida.

• Lista de premios de informática
• Olimpiada de informática
• Método de Monte Carlo
• Búsqueda de árboles en Montecarlo
• Muestreo de importancia
• Hanabi (juego de cartas)

• Campeonato Mundial de Bridge-Computadora – Campeonato Mundial de Bridge-Bot ACBL/WBF (sitio web oficial)
• BridgeGuys (23 de octubre de 2013). "Software de bridge informático participante en el Campeonato Mundial de Bridge Informático y la historia de estos programas de software" (PDF) . Archivado desde el original (PDF) el 8 de noviembre de 2016.
• Ginsberg, Matthew L. (1999). "GIB: Pasos hacia un programa de juego de bridge de nivel experto". pp. 584–589. CiteSeer ^x : 10.1.1.52.2188.
• Bethe, Paul M (14 de enero de 2010). "El estado del juego de bridge automatizado" (PDF) .
• Philippe Pionchon (1984). “Inteligencia artificial y juego de bridge”. Revista Le Bridgeur .Análisis clásico de la IA aplicada al puente.