AI Bridge Kampioen

Dit artikel is gepubliceerd in samenwerking met Binaire, een blog voor het begrijpen van digitale problemen.


We weten dat algoritmen het mogelijk maken om mechanismen te bieden die mensen verslaan bij schaken of in complexere spellen zoals go… maar hoe zit het met bridge? Dit spel, dat verder gaat dan harmonisch, laat een belangrijke plaats over voor menselijke interacties. De door NukkAI ontwikkelde brugrobot Nook wordt op het hoogste niveau gebracht dankzij een combinatie van symbolische AI ​​en digitale AI.

Bridge is een kaartspel waarin een team van twee spelers probeert een gemeenschappelijk doel te bereiken, een ‘contract’ genaamd, dat wordt bepaald tijdens de biedingsfase. Het voltooien van een contract bestaat uit het uitvoeren van ten minste een bepaald aantal trucs tegen het andere team dat zal samenwerken volgens de gecodificeerde regels om te proberen het contract te beëindigen.

In tegenstelling tot bordspellen zoals Schaken of Go, is Bridge een spel met onvolledige informatie. In het begin kent elke speler slechts 13 kaarten in zijn hand. Tijdens het spel kan elke speler, door na te denken over de informatie die tijdens de biedfase en over de kaarten die in elke ronde worden gespeeld, zijn veronderstellingen beperken tot de resterende kaarten in het spel, maar moet hij zijn beslissingen nemen (kies de kaart om in elke ronde te spelen) zonder zich volledig bewust te zijn van de resterende kaarten in de handen van zijn partner of tegenstanders.

Goed bridgen houdt in dat je verschillende soorten vaardigheden onder de knie moet krijgen:

  • Doe aftrekkingen (als deze speler deze reeks zetten speelt, heeft hij of zij deze kaart)

  • Hypothesen maken en herzien (zo’n tegenstander heeft minstens 5 schoppenkaarten of geen hartenkaarten meer)

  • Voorspel een bepaald aantal mogelijke zetten van het andere team

  • Evalueer de kansen van de verschillende potentiële tegenstanders om het risico te sturen en bereken de verwachte winst voor de te spelen zetten.

Versla de menselijke helden

Nook’s AI, gebruikmakend van de gecombineerde kracht van symbolische AI-methoden en digitale AI-technologieën, is erin geslaagd om bridgekampioenen van niveau 8 van wereldklasse te overtreffen in honderden games van hetzelfde decennium om te presteren (3 No Trump). Voor een eerlijke vergelijking tussen Nook en de menselijke spelers speelden Nook en elke kampioen dezelfde games, op de locatie van dezelfde adverteerder, tegen twee van de Wbridge5-bots die het andere team vormen. Wbridge5 (ontwikkeld door Yves Costel) is een kampioen in brugrobotica in meerdere werelden, alleen in competities tussen bots. Elke menselijke held (net als Nook) speelt zijn eigen (verborgen) spel en het spel van zijn partner (spelend “dood”) dat voor iedereen zichtbaar is, tegen twee tegenstanders hier die worden gesimuleerd door een Wbridge5 geconfigureerd in Defender-modus.

In tegenstelling tot spellen met volledige informatie (zoals schaken of zappen), zijn in de spelboom van de brug de mogelijke bewegingen van de tegenstander als reactie op de bewegingskeuze van de robot afhankelijk van de kaarten in de hand van de tegenstander, die de robot niet kent . Voor elke minuutknoop van de boom (d.w.z. een knoop die de tangles van de tegenstander voorstelt), is het nodig om potentiële werelden te creëren (mogelijke handen van de tegenstander), die elk de meest waarschijnlijke tegenstanders op de kaart die door de bot wordt gespeeld, verkent.

De kracht van Nook ligt in het intelligent verkennen van een game tree met potentiële werelden op basis van vier complementaire technologieën:

  • Automatische grammaticale inferentie

  • Machine learning van een voorbeeld van eerder gespeelde games om de strategie van tegenstanders te leren

  • Willekeurige generatie van potentiële Monte Carlo-achtige werelden gebonden aan domeinregels en vijandige modellen

  • Het vinden van een MinMax-achtige boom met Alpha-Beta-garnituren in elke wereld is mogelijk door gebruik te maken van verschillende spelersmodellen.

Nook’s Tree of Possible Game of Worlds-verkenningsalgoritme is met name een uitbreiding en verbetering van het AlphaMu-algoritme dat is ontwikkeld door Tristan Cazenave en Véronique Ventos. In elke fase van het spel genereert het algoritme willekeurig verschillende potentiële werelden, terwijl wordt gecontroleerd of ze voldoen aan de beperkingen die worden afgeleid door de regels en de modellen van de tegenstander die worden waargenomen of geleerd. In elk van de mogelijke werelden worden de verschillende mogelijke zetten geëvalueerd door het MinMax-algoritme dat zeer selectief wordt gemaakt door gebruik te maken van tegenstandersmodellen.

Sommige spelersmodellen zijn neurale netwerken die automatisch worden getraind om hun specifieke taak uit te voeren. Trainingsgegevens worden verkregen uit honderdduizenden games die WBridge5 tegen zichzelf speelt. Het gebruikte neurale netwerk, van het type ResNet, is niet erg groot en de omvang van de trainingsdataset is redelijk. Als gevolg hiervan vereist de trainingsstap, uitgevoerd op de Jean Zay-computer van CNRS, 200.000 keer minder rekenkracht dan de neurale netwerktraining die wordt gebruikt in het AlphaGo-programma van DeepMind, dat in 2016 de hoofdgame van Go Lee Sedol versloeg.

kunstmatige intelligentie concept

Automatische regelinferentie is de sleutel tot het beperken van harmonischen en het verklaren van beslissingen. De regels voorzagen in de kennis van het Nook-model voor bridgespelers, om uit de biedvolgorde positieve of negatieve beperkingen op de handen van verschillende spelers af te leiden. Bijvoorbeeld, het bod van een partner van “2 geen troef” na het openen van “1 geen troef”, gevolgd door de pass van de tegenstander, geeft aan dat de partner een deal heeft van gelijk aan of minder dan 5 harten of schoppen. Andere regels beschrijven hoe de tegenstander de eerste kaart kiest (leidende eenheid).

Deze regels zijn door mensen te interpreteren (omdat ze worden uitgedrukt in speler-logische concepten zoals “uniforme verdeling”) en kunnen worden geëxploiteerd door de machine, die de verbinding heeft gemaakt tussen deze abstracte concepten en de concrete verdelingen van handen. Vanuit de abstracte en afgeleide kennis dat een hand regelmatig is, kan men automatisch alle corresponderende tactiele handen (en hun kansen) genereren op basis van de kaarten die men in één hand heeft en, als maatstaf voor het spel, de kaarten die door verschillende spelers worden gespeeld. spelers.

We begrijpen daarom het belang van regels bij het beperken van potentiële werelden in de tijd en dus het sturen van willekeurige generatie in het hart van Monte Carlo-boomonderzoek.

Een ander voordeel van deze regels is dat ze op elk moment tijdens het spel kunnen worden gebruikt om de hoge zichtbaarheid en waarschijnlijkheid van de verborgen handen van de tegenstander uit te leggen. Inderdaad, in de brug, het beantwoorden van vragen als “Waarom heb je deze kaart gespeeld?” Het maakt deel uit van de Gedragscode om met name te controleren of er geen sprake is van bedrog van de kant van de speler of dat de zet geen toeval is.

Ook al speelt Nook momenteel slechts een deel van de huidige “contracten” van de brug (de “drie troeven”), de ontwerpers hebben al het nut aangetoond van “hybride” AI die hen de mogelijkheid geeft om hun opties uit te leggen. Deze nieuwe aanpak, die NukkAI van plan is uit te rollen op andere gebieden, zoals cyberbeveiliging, onderwijs of transport, opent de weg voor “iets dat meer lijkt op intelligentie dan we deze jaren hebben gezien”, stelt Cedric Villani, auteur van een parlementair rapport dat in 2018 inspireerde de strategie De Franse regering over kunstmatige intelligentie, die de uitdaging live kwam observeren.

Leave a Comment