Bridge met bytes

Computers zijn inmiddels beter dan mensen in bordspellen als schaak en go. Maar bridge met bytes is geen succesverhaal. De computer mist intuïtie.

Het was wereldnieuws: de computer verslaat een van de beste go-spelers ter wereld. Negentien jaar daarvoor, in 1997, moest wereldkampioen Gary Kasparov het afleggen tegen schaakcomputer Deep Blue. In de wereld van strategische bordspellen geldt het Chinese go als complexer dan het van oorsprong Indiase schaak en dat verklaart waarom het zo lang heeft geduurd eer er een fatsoenlijk go-algoritme is geschreven.

Negentien jaar is een geologisch tijdperk in de wereld van computertechnologie. In 1997 had de massa nog maar net kennis gemaakt met internet, pasten mobiele telefoon nauwelijks in je broekzak want zo groot als een baksteen en waren de digitale video disc en de dvd-speler het nieuwste snufje op het gebied van consumentenelektronica. Opa, vertel nog eens…

In de jaren tussen 1997 en 2016 gold go als de steen der wijzen van het onderzoek naar kunstmatige intelligentie. Een jaar nadat schaakkampioen Kasparov zijn meerdere moest erkennen in een schaakalgoritme versloegen geoefende spelers, geen kampioenen, het beste go-computerprogramma van dat moment. Zelfs een onrealistisch zware handicap voor de menselijke spelers kon het algoritme niet aan winst helpen. De weg naar een winnend go-algoritme was lang en zwaar.

Vlieguren

Go wordt gespeeld op een raster van 19 bij 19 lijnen en telt dus 361 snijpunten, aanzienlijk meer dan de 64 velden van het schaakbord. Het aantal mogelijke spelsituaties, en bijgevolg optimale voortzettingen, is astronomisch veel groter dan schaak heeft te bieden. De tactieken waarmee schaakalgoritmes werken lopen stuk op go. Het snoeien van het aantal mogelijkheden (alpha-beta pruning in jargon) is ondoenlijk, er zijn domweg teveel opties.

Het evalueren van de posities die de schaakstukken innemen op het bord werkt ook niet voor go. Bij schaak heeft elk stuk zijn intrinsieke waarde, een toren is waardevoller dan een loper. Bij go wordt de waarde van de stenen, of eigenlijk: de waarde van de positie van de stenen, bepaald door de context, de positie van de stenen die er omheen liggen en de open plekken. De eenvoud van de spelregels voor go maakt het onmogelijk om de positie-evaluatie te formaliseren. Goede go-spelers ontwikkelen daarvoor een intuïtie.

De computer speelt go

Ondanks die serieuze obstakels – in de alinea’s hierboven slechts in zeer algemene zin  aangestipt – is het toch gelukt om een go-programma te maken dat op meester-niveau presteert en wel via zelflerende neurale netwerken. Als het probleem te complex is om via een geformaliseerde aanpak (een algoritme) te tackelen, dan moet het ‘algoritme’ meer flexibel zijn en leren van zijn ervaringen. Een beetje zoals de go-meesters door de jaren hun intuïtie hebben aangescherpt. Vlieguren maken de expert.

Kaarten tellen

Is het AI-onderzoekers gelukt om het probleem van computer go te kraken, voor een andere denksport, bridge, is de robotspeler nog ongewisse toekomst. Het kaartspel bridge werpt problemen op die van een andere categorie zijn dan de optimale strategie voor de bordspelen schaak en go. Wie achter het spelbord zit, mens of computer, overziet het complete veld. Dat is niet het geval bij bridge. Het is een spel waarbij de spelers moeten werken met incomplete informatie.

Bridge wordt gespeeld met twee teams van twee spelers elk en bestaat uit twee fasen. Eerst het bieden, waarmee de teamspelers elkaar (en de tegenstanders) informatie geven over hun hand met kaarten. Uit het bieden rolt een eindbod, het contract, dat vervolgens moet worden gehaald door de kaarten te spelen, de tweede fase. De speler die het contract biedt, speelt de kaarten. Zijn partner legt diens hand open op tafel en is verder inactief, hij is de dummy.

Bridge voor beginners

Bij aanvang van het spel beschikt elke speler alleen over de informatie die zijn hand hem biedt. Tijdens het bieden wordt daar informatie aan toegevoegd. Als de dummy zijn kaarten open legt is er een kwart van de kaartdistributie duidelijk en tijdens het spelen van het contract verschijnt er nog meer informatie. Kaarten tellen (welke zijn er uit het spel?) is een vereiste. Pas als het spel is voltooid is de informatie compleet.

Monte Carlo methode

Al sinds 1997 organiseert de American Contract Bridge League een jaarlijks toernooi voor computerbridge, dus met de automatisering van het spel zal het wel snor zitten, ben je geneigd te denken. Het tegendeel is waar.

Bij bridge draait het om de verdeling van de kaarten; voor automatiseerders is het een distributieprobleem en derhalve een waarschijnlijkheidsprobleem. Hoe groot is de kans dat deze combinatie van kaarten voorkomt? Het aantal mogelijke handen (distributies) is astronomisch, maar niet elke verdeling is even waarschijnlijk. Een hand waarin een ‘kleur’ ontbreekt komt minder vaak voor dan een hand met alle ‘kleuren’.

Het bridge algoritme, bridge met bytes, genereert een groot aantal mogelijke verdelingen op basis van de gegeven, maar incomplete informatie ( in jargon: de Monte Carlo methode). Het zoekt vervolgens de beste voortzetting door te doen alsof de informatie compleet is, de double dummy oplossing. Dat is een versimpelde versie van het werkelijke spel. Op die manier kan de computer alle mogelijkheden aflopen, vergelijkbaar met schaak en go.

Jack in the box

Het bridge algoritme Jack, veelvoudig winnaar van het computerbridge toernooi, doet het heel behoorlijk tegen spelers op topniveau, maar verliest vaker van ervaren kaarters dan het wint. AI-onderzoekers geven toe: vergeleken met  computerschaak staat computerbridge in de kinderschoenen. Het is de vraag of het daar ooit uitkomt.

Het beslissende verschil: bridge is een spel met incomplete informatie. Net als het leven zelf. De alwetende blik en de totale regie zijn de gedroomde perfectie, maar de praktijk is verre van perfect, de informatie nooit compleet. Het verhaal van bridge met bytes illustreert een uniek menselijk trekje.

Mensen moeten dagelijks talloze keuzes maken op basis van incomplete informatie en slagen er opmerkelijk vaak in om de goede (of in ieder niet een verkeerde) keuze te maken. Dat doen ze op basis van hun ervaring en leervermogen. En via hun intuïtie, een onmisbaar hulpmiddel in een imperfecte wereld. En onmogelijk te vangen in een algoritme.

Computerschaak: hoe het werkt

Geef als eerste reactie