Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Door , , 56 reacties
Bron: IEEE Spectrum

Volgens een Canadese hoogleraar informatica eindigt checkers altijd in gelijkspel als beide partijen perfect spelen. Het bewijs voor deze stelling publiceerde hij gisteren op de website van het wetenschappelijke tijdschrift Science

Checkers is een variant van dammen die ook wel bekend staat als 'Engels dammen' en waarbij twee spelers, elk met 12 stenen, op de zwarte vlakken van een schaakbord spelen. In 1989 presenteerde hoogleraar informatica Jonathan Schaeffer van de Universiteit van Alberta in Canada Chinook: een computerprogramma dat het WK checkers in 1994 won van een mens. Dat programma maakte gebruik van een enorme database met zetten die menselijke grootmeesters hadden gedaan. Nadat de checkerscomputer de kampioenstitel had binnengesleept, besloot Schaeffer het spel te gaan 'oplossen'.

Checkersbord

Dit zou een indrukwekkende klus worden, aangezien er bij checkers maar liefst 500 triljoen (5∙1020) mogelijke spelsituaties bestaan. Daarom begon Schaeffer met een database met alle mogelijke eindspelen die op zouden kunnen treden bij winst, verlies en gelijkspel. Vanaf die eindsituaties zocht hij terug naar mogelijke voorgaande situaties, net zolang tot hij bij een spelsituatie met 10 speelstukken uitkwam. Op dat moment had hij al een database van 39 biljoen spelsituaties, die ondanks compressie 237GB aan ruimte innamen. Deze database vergde dermate veel rekenkracht dat Schaeffer het project in 1997 stilzette, om pas vier jaar later de draad weer op te pakken.

Schaeffer zette vervolgens een voorwaarts zoekalgoritme in om vanaf de beginsituatie te zoeken naar een rij zetten die tot een van de 39 biljoen spelsituaties zou leiden. Hierbij werd niet gezocht naar alle mogelijke zetten en de gevolgen ervan, zoals Chinook of schaakcomputer Deep Blue dat zouden aanpakken; enkel de beste zetten werden geanalyseerd, namelijk de zetten die zo snel mogelijk tot winst zouden leiden. Het doel van een checkersspeler is volgens Schaeffer namelijk het in zo min mogelijk zetten winnen van het spel of verlies zo lang mogelijk uitstellen. Zo bleven van de 500 triljoen mogelijke spelsituaties 'nog maar' 100 biljoen posities over.

WK checkers 1992: Jonathan Schaeffer achter een Silicon Graphics 4D/480

Checkersspelers hadden al langer het vermoeden dat een spel altijd in remise moest eindigen als beide spelers perfect speelden. Partijen tussen menselijke spelers eindigden zo vaak in gelijkspel dat het vanaf 1934 verplicht was iedere partij op een wereldkampioenschap te beginnen met drie zetten uit een lijst met geaccepteerde willekeurige zetten. Schaeffer heeft nu van 19 van de 300 mogelijke openingszetten bewezen dat ze in remise eindigen bij een perfecte speelwijze. De overige 281 beginzetten leiden volgens de professor tot spelsituaties die door de 19 bewezen openingszetten ook bereikt worden. Hij is daarom ook niet van plan moeite te doen om een volledig bewijs te leveren. Dat zou ook onmogelijk zijn omdat zelfs de grootste supercomputers van dit moment niet genoeg opslagruimte hebben voor de tientallen petabytes aan ruimte die de database inneemt.

Het zal nog heel lang duren voor een spel als schaken wordt 'opgelost'. Wetenschappers vermoeden dat ook dat spel altijd in remise eindigt als het perfect gespeeld wordt, maar het aantal mogelijke spelposities bij schaken is het kwadraat van dat bij checkers. Dit betekent dat er 1040 tot 1050 mogelijke situaties moeten worden geanalyseerd. Volgens Schaeffer is dat niet onmogelijk, maar zonder een doorbraak in kwantumcomputertechnologie zal niemand aan de lange zoektocht beginnen.

Moderatie-faq Wijzig weergave

Reacties (56)

"Het zal nog heel lang duren voor een spel als schaken wordt 'opgelost'. Wetenschappers vermoeden dat ook dat spel altijd in remise eindigt als het perfect gespeeld wordt, maar het aantal mogelijke spelposities bij schaken is het kwadraat van dat bij checkers."

Spellen zijn alleen maar leuk door onze onwetenheid en beperktheid.

Het zijn allemaal spellen op een bord van vaste afmetingen met een beperkt aantal vlakken en eventueel een beperkte hoeveelheid stukken. De mogenlijkheden zijn dus altijd beperkt.

Boter kaas en eieren is leuk voor een klein kind, maar een volwassen persoon ziet het nut er niet van in sinds je niet kan winnen indien de tegenpartij geen fout maakt. Zo ook is schaken interessant voor een volwassen persoon en die staat niet automatisch boven de ladder (al wel op onze planeet).

[Reactie gewijzigd door Teddy Rukspin op 20 juli 2007 14:24]

gaaf hoor, dat mensen zich hier mee bezighouden :) respect
vraag me wel af waarom iemand zou gaan dammen als je schaak kunt spelen.. (omdat het zo vaak remise wordt, en omdat dammen toch een soort light-weight schaak is.. sorry dammers onder ons :P)
Dit gaan dan wel om checkers, soort van mini-dammen dus.

"Gewoon" dammen gaat op 100 vakjes, en met 40 stenen in plaats van de hier gebruikte 24 stenen op 64 vakjes.

En dat zal ook wel altijd op remise eindigen bij perfect spel, maar is weer een factor moeilijker te bewijzen.
Daarom heb je ook sinds een X aantal jaar de "Delftsche telling", welke het remise probleem voor een groot deel oplost ;) (Google maar naar DUWO Kennisstadtoernooi ofzo, vind je er genoeg over).
Bovendien heeft Checkers, behalve het kleinere boord, ook veel afwijkende regels (dam mag maar één vakje, achteruitslaan met gewone schrijf niet toegestaan, etc)
Dammen... schaken... het blijven spelletjes waarbij het aantal zetten beperkt is. Alleen is het zo dat ons brein blijkbaar het aantal mogelijkheden bij dammen beter kan 'overzien' dan bij schaken omdat dat spel zo vaak in remise eindigt. Voor de rest kun je jouw stelling dus ook gewoon omdraaien: schaken is een zware vorm van dammen. ;) Ik zie verder weinig lol in beide spellen.
Beperkt is misschien niet het juiste woord... ik zou eerder "eindig" zeggen. Het is inderdaad beperkt, maar nog altijd is het aantal mogelijke schaakpartijen ver, ver, VER boven wat een mens kan bevatten, en ookboven wat een computer uit kan rekenen binnen een redelijke tijdspanne.

Ga maar na: een schaker kan in z'n eerste zet kiezen uit 20 zetten (8 pionnen kunnen 1 of 2 vakken vooruit, 2 paarden kunnen elk naar 2 velden). Zwart kan antwoorden met eveneens 20 zetten. Na 1 zet (wit+zwart) heb je dus al 400 combinaties.

Het verschil tussen mens en computer is dat een mens weet dat van die 400 mogelijkheden, er nog geen 10 zijn die strategisch handig zijn. Een computer weet dat niet en moet combinaties doorrekenen om erachter te komen.
met een beetje slim programmeerwerk kun je er ook wel achter komen welke zetten waarschijnlijk minder handig zijn en dus vantevoren ook alvast wat filteren.

@knettergek: aannamen zijn niet per se slechter dan berekeningen.. (maw: gewiekste aannames zijn vaak sneller en redelijk accuraat terwijl berekenen veel meer tijd kan kosten)
een mens doet een aanname. Een computer rekent het uit. Daarom zijn computers mits krachtig genoeg ook sterker in Schaak dan mensen.
Nou... Ik ken geen schaakprogramma dat niet gebruik maakt van een openingsboek. Vaak wordt er pas serieus gerekend zodra een partij buiten het openingsboek terecht komt.
Een mens rekent lang niet alle spelsituaties na, alleen wat relevant is.....Deep Blue berekende van iedere zet alle mogelijke zetten uit..da's niet efficient...
Dat is een verkeerd idee van wat een schaakcomputer doet. Die berekent echt niet alles door... dat zou veel te veel computer kracht vergen. Ook een schaakcomputer probeert zo snel mogelijk tot de conclusie te komen dat een bepaald zet niet goed is, en dus de berekening af te breken, om zodoende alleen relevante zetten door te rekenen.
Checkers kun je niet vergelijken met het officiele Russische damspel dat op een bord van 10x10 velden wordt gespeeld. Afgezien van het verschil in spelregels, is het door het grotere speelveld en het hogere aantal schijven stukken complexer. In mijn ogen kan het officiele damspel qua complexiteit goed wedijveren met het schaakspel.
Je laatste zin klopt niet want in het schaakspel heb je stukken met verschillende waardes die ook nog eens verschillende stappen kunnen maken.

Terwijl bij het dammen alle stukken dezelfde waarden hebben.
Maar dat maakt het helemaal niet moeilijker of makkelijker.
Bij dammen heb je minder mogelijk zetten per beurt, en zelfs nog minder omdat je verplichte zettenreeksen hebt.
Dit maakt e.e.a. wel sneller, maar geen orde van grootte beter.
Waarom een goed damprogramma eerder op de markt was dan een goed schaakprogramma, is omdat de evaluatiefunctie voor dammen veel eenvoudiger is.

Maar dammen en schaken zijn dan misschien niet wiskundig opgelost, praktisch gezien wint een programma op een huis-tuin en keuken pc van 99,999% van alle mensen. Dat is wel een keer genoeg nu.

Nu maar eens een behoorlijk go programma schrijven. Veel succes! }>
Bij schaken hebben de stukken ook dezelfde waarde, de pion slaat net zo hard een koning als de dame dat doet. Echter heb je hier een target(koning) en hebben de stukken verschillende mogelijkheden.

Als we het over waardes hebben, bijvoorbeeld pion is lager dan toren. Dan heeft ook dammen/checkers .verschillende waarden. Een dam is meer dan een gewone schijf.
Je snapt denk ik niet helemaal wat hij bedoelt. Bij dammen heb je de gewone damschijf en een dam. Meer niet. Je hebt dus een bepaald aantal verdelingen van de stenen en die wordt groter door de dam, maar als je 2 damschijven van positie wisselt, win je niks. Een schaakspel heeft veel meer verschillende stukken, waardoor er veel meer verschillende posities zijn. Daarbij bewegen de stukken ook allemaal anders, vooral paarden maken rare bewegingen vergeleken met lopers en torens... Schaken is echt voor een computer nog veel complexer dan dammen, hoewel ik echt niet wil zeggen dat dammen een eenvoudig spelletje is ofzo ;)

Als je een klein beetje verstand van kansrekening/statistiek hebt, snap je dat je met een gegeven aantal stukken op een gegeven aantal vakjes meer mogelijke unieke verdelingen van die stukken krijgt als je meer verschillende stukken hebt. Probeer maar 's 2 rode Ferrari's op zoveel mogelijk manieren in 3 parkeerhavens te krijgen... Je zult merken dat dat op 3 manieren kan (rood/rood/leeg, rood/leeg/rood en leeg/rood/rood). Als je echter een rode en een zilverkleurige Ferrari gebruikt, heb je zes mogelijkheden (zilver/rood/leeg, rood/zilver/leeg, zilver/leeg/rood, rood/leeg/zilver, leeg/zilver/rood en leeg/rood/zilver). Dat zijn ineens 2x zoveel mogelijkheden.

[Reactie gewijzigd door Grrrrrene op 20 juli 2007 18:21]

Ik denk dat ik zijn waardes dan verkeerd begreep. Ik dacht dat hij waardes bedoelde als in een hierarchie: pion -> toren -> paard -> loper -> dame -> koning.
De hierarchie is officieus de volgende: pion (1 punt), paard en loper (3 punten), toren (5), dame (9) en koningen (oneindig).
@ Grrrrene
Dat lijkt me alles behalve de realiteit

De computer kijkt niet naar kleuren/merken/soorten/ranken.
Bij een toren zou hij niet denken, als ik een koning was geweest had ik het zo kunnen doen.
Dus je hebt bij dammen een x aantal stenen
en bij schaken een x aantal stukken, maar de hoeveelheid berekeningen blijven gelijk aan factor maal x.
Lijkt me een klusje voor DPC }:O

[Reactie gewijzigd door Erasmo op 20 juli 2007 13:58]

Te laat.

Bovendien is dit geen parameter-sweep application. D.w.z. je kunt niet een stukje data nemen en daar een uurtje op gaan zitten rekenen, je moet constant communiceren met de andere nodes (voornamelijk om geen 1020-dubbel werk te doen) en daarvoor heeft DPC een veel te hoge latency.

[Reactie gewijzigd door tybris op 20 juli 2007 14:06]

Zie ik daar weer een andere DPC klus aankomen? Een efficiente manier van rekenen analyseren. :)

Ik vraag me wel af wat er gebeurt als twee Chinooks tegen elkaar spelen. Als ik het goed begrijp moet er dan altijd remise uit komen. Of is die nog niet op een dusdanig niveau dat het klopt?

In ieder geval interessante materie en weer een voorbeeld dat onze huidige computertechnologie geheel in het niet valt bij een of ander ouderwets spelletje met 24 stenen :').
Ik vraag me wel af wat er gebeurt als twee Chinooks tegen elkaar spelen. Als ik het goed begrijp moet er dan altijd remise uit komen. Of is die nog niet op een dusdanig niveau dat het klopt?
Het heeft weinig zin om 2 identieke programma's tegen elkaar te laten spelen, volgens mij.

Ik kan alleen spreken voor schaakprogramma's, maar wat een schaakprogramma doet is (binnen een vastgestelde tijd) zoveel mogelijk zetten berekenen, en verder te rekenen door uit te gaan van de beste zet die de tegenstander zou kunnen doen, om dan weer de beste zet voor zichzelf te kunnen doen, etc.

Als je 2 identieke programma's op elkaar loslaat, dan zouden ze theoretisch continu de zet doen die de ander al dacht dat hij zou doen. Je kunt net zo goed 1 computer tegen zichzelf laten spelen dan 2 computers tegen elkaar met hetzelfde programma. (Bij schaken zal er toch verschil in zitten, ivm openingsboeken, random keuze uit meerdere zetten die hetzelfde resultaat opleveren, etc.)
Als je 2 identieke programma's op elkaar loslaat, dan zouden ze theoretisch continu de zet doen die de ander al dacht dat hij zou doen.
Dat zou je denken, maar dat gaat zelfs voor volledig deterministische programma's niet op. Dat komt namelijk omdat ze niet vanuit dezelfde stelling rekenen.

Als beide programma's bijvoorbeeld exact zes ply ("halve" zetten; dus een zet van wit en zwart is 2 ply) vooruit denken, kan speler A in de huidige stelling een zet doen waardoor hij 7 ply later verliest, want dat is net te ver weg om te voorzien. Speler B denkt echter na over de stelling nádat A heeft gezet, en voor hem is die situatie dus wél binnen beriek. Daardoor heeft B betere informatie over de gevolgen van zetten, en kan zo een andere zet kiezen dan A had "verwacht".
Je bedoelt dus dat het er aan zou liggen wie er begint?
Als namelijk eerst de ene computer zou beginnen, zou deze perfect volgens het programma het spelletje van de ander nadoen, indien deze mocht beginnen. }:O
Als je pas echt een uitdagend klusje wil hebben, probeer dan eens hetzelfde te doen met Go. :P
Tijdens het college Fundamentele Informatica dit jaar kwam Go even te sprake.. Go is zeer waarschijnlijk een onoplosbaar probleem, zeker als je het volledig door wil berekenen. De reden hiervan is eigenlijk heel flauw.. Het aantal mogelijke spelsituatie in Go is meer dan het aantal (geschatte) atomen in ons universum dus word het voorlopig onmogelijk geacht om Go door te rekenen.. Ik neem me te herinneren dat mijn prof zei dat dat Go word geacht zit te bevinden hoog in de Exp klasse

[Reactie gewijzigd door martijnvanegdom op 20 juli 2007 19:49]

tenzij je natuurlijk een kwantum pc in elkaar weet te schroeven... dan heb je namelijk een theorethisch maximum van 2^(atomen_in_universe) als ik het wel heb...
enneuh, aangezien een atoom gemiddeld wel meer dan 1 electron heeft is er dus nog plaats aangezien men in een electron al wat info kan opslaan
Volgensmij hebben alle spellen mits perfect gespeeld, maar één uitkomst (winnen, gelijk, verliezen). Ga ik er natuurlijk wel even vanuit dat het geen kansspel is (dobbelsteen spellen etc). Dus ook go.
Toevallig zat ik laatst wat te lezen over Deep Blue en computerschaak. Na de overwinning op Kasparov had een engineer zich voorgenomen om een spel te bedenken, wat een stuk lastiger was dan schaken om door een computer doorgerekend te kunnen worden (alsof dat bij schaken al niet lastig genoeg was), maar simpel genoeg om door zijn zoontje gesnapt te kunnen worden.

Het resultaat is een spel genaamd Arimaa (zie ook Wikipedia). Bij dit spel is inzicht in positie belangrijker dan materiele voorsprong, wat het bij dammen/checkers en enigszins bij schaken nog mogelijk maakt om een redelijk krachtig programma te schrijven wat er goed in is.

[Reactie gewijzigd door 19339 op 20 juli 2007 14:48]

Erg leuk om te lezen, maar de groep mensen die hier feitelijk wat aan zullen hebben zal niet echt groot zijn lijkt me? Gek dat een grote computer firma hier niet achter is gaan staan, was een mooie PR kans geweest voor bijvoorbeeld SUN om IBM wat wind uit de zeilen te nemen met hun schaak computer capriolen. :)
Waarschijnlijk zijn de huidige supercomputers simpelweg niet krachtig genoeg. Bij Engels Dammen heb je meer dan 10tallen petabytes nodig om alles te kunnen berekenen....schaken zit wat ingewikkelder in elkaar.
Als ik dam dan eindigt het altijd in remise. Dus dat wil zeggen dat al mijn tegenstanders net zo een perfect spel spelen als ik ;)
Ik vind het jammer dat ze proberen spellen op te lossen.
Ik vind dat computers zich moeten houden buiten het terein van klassieke spelen.

Ok het is wel tof dat je kunt schaken tegen de computer, als er niemand anders is die met je wilt schaken, maarja, je kunt helaas geen emoties aflezen bij een computer, en dat maakt de klassieke spelen nou net zo leuk. Zien hoe een ander reageert als je hem/haar de loef kunt afsteken.

Internet gaming tegen andere personen met een kleine minichat, zoals msn games is wel wat leuker, maar toch ontgaat het word gezelschapspel dan een beetje, echt gezellig zoals met 2 naast elkaar een spel spelen is het niet.

De echte reden dat een computer zich eruit moet houden is wel dat ze spelen onbruikbaar maken. Als de winnende comnbinatie bekend is net zoals deze van bantummi ( nokia 3310 ) dit winnende zetten van dit afrikaans spel zijn bekend, er is altijd een winnaar, maar wie dat word licht gewoon aan wie begint, dus das een flauw spel nu.

Daarom hoop ik dat het nog lang duurt eer de computer het schaakspel oplost, mja , zelf nu zijn de computers eigenlijk al veeeels te sterk (voor mij toch)
Eigenlijk zeg je daarmee "ignorance is bliss". Dat is natuurlijk een misverstand en leid alleen maar tot beperking en pijn.

We kunnen de inzichten die we boeken beter zien als mogenlijkheden. Deze inzichten doen geheel nieuwe deuren open met wie weet wat daar achter te vinden is.

Schaken zal hetzelfde blijven als je het tegen een ander mens speelt, oplossing of niet. Een mens (althans in huidige vorm) zal nooit zo'n complexe oplossing kunnen toepassen.
Kan ik niet met je eens zijn...

Ten eerste zijn het niet de computers die zich met het spel bemoeien, maar mensen die de computer op het spel loslaten. Deep Blue heeft Kasparov niet uitgedaagd, maar de mensen van IBM. De computer is nog steeds een dom stuk gereedschap.

Maar dan nog: al zou het schaakspel "opgelost" worden door een computer, maakt dat dan een spelletje schaken tegen je neefje minder leuk? Het blijft een dusdanig complex spel wat je logisch denkvermogen zwaar op de proef stelt, dat het al dan niet bestaan (cq. bekend worden) van "de perfekte partij" de lol van het spel bederft. Het spel wordt zeker niet "onbruikbaar".

Boter-kaas-en-eieren is ook nog steeds geinig om in een verloren minuutje op de collegebank met je buurman te doen, ook al heb je Wargames gezien.
[quote][...] elk met 12 stenen, opde [b]zwarte[/b[ vlakken van een schaakbord spelen.[/quote]

Dat is dus op het bord van de foto niet mogelijk..... :|
De methode om vanaf de eindsituatie alle stellingen tot enkele zetten terug te bepalen en vervolgens vanuit de beginsituatie alle zetten bepalen om tot de opgeslagen stellingen te komen is blijkbaar een gangbare methode voor suboptimalisatie.

Cube Explorer (http://kociemba.org/cube.htm) gebruikt deze methode ook om het (suboptimale) minimale aantal keer draaien te bepalen bij het oplossen van een Rubic's kubus.
Voor geďnteresseerden: de genoemde website bevat ook de wetenschappelijke redenatie achter de gebruikte methodes voor het oplossen van een kubus.
"Hierbij werd niet gezocht naar alle mogelijke zetten en de gevolgen ervan, zoals Chinook of schaakcomputer Deep Blue dat zouden aanpakken; enkel de beste zetten werden geanalyseerd, namelijk de zetten die zo snel mogelijk tot winst zouden leiden."
Hoe weet je nou vóórdat je gaat analyseren welke zetten tot winst leiden :?

Op dit item kan niet meer gereageerd worden.



Apple iOS 10 Google Pixel Apple iPhone 7 Sony PlayStation VR AMD Radeon RX 480 4GB Battlefield 1 Google Android Nougat Watch Dogs 2

© 1998 - 2016 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Carsom.nl de Persgroep Online Services B.V. Hosting door True