8x8 dammen uitgeanalyseerd door Chinook

Rein Halbersma · Post by **Rein Halbersma** » Sun Jul 29, 2007 22:22

Bert Zwart wrote:
Eric van Dusseldorp wrote:
Jaap van Galen wrote: Inderdaad, maar hopelijk slaan die checker-players 1 stap over en gaan ze direct naar versie N+2, ofwel lekker 10x10 spelen, dat zou mooi zijn.
En als het niet teveel gevraagd is, graag volgens de internationale regels.
Hebben we nog twintig jaar, of minder?

Stef Keetman heeft in Dammen wel es uitgerekend wat ervoor nodig is om 10x10 dammen uit te analyseren, met extrapolatie van Moore's Law, en hij kwam uit op het jaar 2100 of daaromtrent.

Jaap van Galen · Post by **Jaap van Galen** » Sun Jul 29, 2007 22:33

Bert Zwart wrote:
Eric van Dusseldorp wrote:
Jaap van Galen wrote: Inderdaad, maar hopelijk slaan die checker-players 1 stap over en gaan ze direct naar versie N+2, ofwel lekker 10x10 spelen, dat zou mooi zijn.
En als het niet teveel gevraagd is, graag volgens de internationale regels.
Hebben we nog twintig jaar, of minder?

Wellicht te simpel redenerend:
Bij checkers gebruiken ze 8*8/2 ofwel 32 velden. Wij gebruiken 50 velden.
Op elk veld kan ofwel een witte schijf ofwel een zwarte schijf ofwel een witte dam ofwel een zwarte dam ofwel niets staan. Bij checkers zijn er dus 32^5 mogelijke standen, bij ons 50^5 mogelijke standen. Om ons dammen uit te rekenen moet je dus uitgaan van 18^5 meer mogelijke posities, ofwel 1889568 keer zoveel posities, als bij checkers. De vraag is hoe snel de ontwikkeling van de computer gaat. Bij twintig jaar zou dit betekenen dat de computers elk jaar ongeveer 2,1 keer "beter" zouden moeten worden. Worden de computers ongeveer 2,6 keer "beter" per jaar dan duurt het 15 jaar, worden ze ongeveer 4.2 keer "beter" per jaar dan duurt het 10 jaar, worden ze ongeveer 1,6 keer "beter" dan duurt het 30 jaar.
Gezien de ontwikkelingen lijkt me die twintig jaar wel te gaan lukken, dan zijn wij ook uitgeanalyseerd, maar wellicht heeft iemand een betere schatting?

Rein Halbersma · Post by **Rein Halbersma** » Mon Jul 30, 2007 00:35

Jaap van Galen wrote:
Bert Zwart wrote:
Eric van Dusseldorp wrote: En als het niet teveel gevraagd is, graag volgens de internationale regels.
Hebben we nog twintig jaar, of minder?
Wellicht te simpel redenerend:
Bij checkers gebruiken ze 8*8/2 ofwel 32 velden. Wij gebruiken 50 velden.
Op elk veld kan ofwel een witte schijf ofwel een zwarte schijf ofwel een witte dam ofwel een zwarte dam ofwel niets staan. Bij checkers zijn er dus 32^5 mogelijke standen, bij ons 50^5 mogelijke standen. Om ons dammen uit te rekenen moet je dus uitgaan van 18^5 meer mogelijke posities, ofwel 1889568 keer zoveel posities, als bij checkers. Gezien de ontwikkelingen lijkt me die twintig jaar wel te gaan lukken, dan zijn wij ook uitgeanalyseerd, maar wellicht heeft iemand een betere schatting?

Deze berekeningen kloppen niet helemaal: de machtsverheffingen zijn precies andersom. Als de verwisselingen van identieke stukken even verwaarlozen, en ook dat we beginnen met elk 20 schijven, dan zijn er volgens jouw telling 5^32 stellingen (niet 32^5) bij checkers en 5^50 bij dammen (niet 50^5).

5^32 = 2 * 10^22 en 5^32 = 8 * 10^34, dus dammen is ongeveer 10^12 keer zo lastig voor een computer als checkers. Verder geldt dat 2^10 = 1000 en 1000^4 = 10^12 dus 2^40 = 10^12. Als we nu Moore's Law nemen als verdubbeling in capaciteit per 2 jaar, dan is er nog 80 jaar te gaan voor dammen gekraakt is. Jaar 2087. Maken we niet meer mee denk ik.

Aan de andere kant, Schaeffer en zijn team hebben wel een paar slimme trucs gebruikt om de 10^22 posities van checkers door te rekenen. Ze gebruiken ongeveer 10^11 stellingen in eindspeldatabases (alle 10-stukken databases: ongeveer 2x zo groot als de 8-stukken databases bij dammen zouden zijn) en verder hebben ze ongeveer 10^14 stellingen doorgerekend met vooruitzoeken.

Als dit verdeel-en-heers ook bij dammen opgaat (omvang van de rekentijd is ongeveer de wortel van de omvang van het probleem), zou je misschien "maar" 10^6 zoveel berekeningen als bij checkers nodig hebben. Dan is het nog maar 20 Moore's verdubbelingen (40 jaar?) tot dammen uit is.

Jaap van Galen · Post by **Jaap van Galen** » Mon Jul 30, 2007 07:36

Rein Halbersma wrote:Deze berekeningen kloppen niet helemaal: de machtsverheffingen zijn precies andersom. Als de verwisselingen van identieke stukken even verwaarlozen, en ook dat we beginnen met elk 20 schijven, dan zijn er volgens jouw telling 5^32 stellingen (niet 32^5) bij checkers en 5^50 bij dammen (niet 50^5).

Het Haagse Milan-festival eist blijkbaar zijn tol ....

Rein Halbersma wrote:........ dan is er nog 80 jaar te gaan voor dammen gekraakt is. Jaar 2087.
Aan de andere kant, Schaeffer en zijn team hebben wel een paar slimme trucs gebruikt om de 10^22 posities van checkers door te rekenen. ...... Dan is het nog maar 20 Moore's verdubbelingen (40 jaar?) tot dammen uit is.

Ergens in de tweede helft van deze eeuw zijn we uitgeanalyseerd, dat lijkt dus een aardige voorspelling. Ik houd het vooralsnog op 2050.
We hebben nog even om ons er op voor te bereiden....

Klaas van der Laan · Post by **Klaas van der Laan** » Mon Jul 30, 2007 10:35

Jaap van Galen wrote: Ergens in de tweede helft van deze eeuw zijn we uitgeanalyseerd, dat lijkt dus een aardige voorspelling. Ik houd het vooralsnog op 2050.
We hebben nog even om ons er op voor te bereiden....

Nieuwe technieken zullen veel eerder voor revolutionaire vooruitgang zorgen waardoor Moore's wet de prullebak in kan. Ik denk b.v. aan biologische chips, multitaal i.p.v. digitaal, processors met lichtsnelheid, kwantumtechnieken o.i.d.

composite · Post by **composite** » Mon Jul 30, 2007 19:37

Even concreet: in 8x8 zijn vele miljarden posities mogelijk. In 10x10 ligt dat aantal nog veel hoger. Een aanzienlijk deel ervan kan als niet relevant worden weggepoetst. Blijft de vraag of een menselijk brein zonder hulp van een digitaal bestand tijdens de partij in staat is om in het gigantische doolhof van dat oneindig aantal varianten steeds de beste te kiezen. Al die mogelijkheden 'uit je hoofd leren' is immers ondoenlijk. Hoe schatten de deskundigen dit in?

Rein Halbersma · Post by **Rein Halbersma** » Mon Jul 30, 2007 20:55

composite wrote:Even concreet: in 8x8 zijn vele miljarden posities mogelijk. In 10x10 ligt dat aantal nog veel hoger. Een aanzienlijk deel ervan kan als niet relevant worden weggepoetst. Blijft de vraag of een menselijk brein zonder hulp van een digitaal bestand tijdens de partij in staat is om in het gigantische doolhof van dat oneindig aantal varianten steeds de beste te kiezen. Al die mogelijkheden 'uit je hoofd leren' is immers ondoenlijk. Hoe schatten de deskundigen dit in?

met de 8-stukken database kan al het einde van Woldouby en De Haas-Fabre gezien worden. Dit doet vermoeden dat de beste damcomputers ruim voorbij de topgrootmeesters zijn inmiddels. De matches van Flits en Buggy van een aantal jaren terug waren nog met de 6-stukken eindspelen en toen al was het erg close.

Bert Zwart · Post by **Bert Zwart** » Tue Jul 31, 2007 21:30

Het aantal mogelijkheden alleen lijkt me niet zo relevant, als enkele slimme dammers het aantal relevante posities op slimme wijze weten te beperken zijn we vrij snel klaar. Moore's law ken ik niet. Veel zal afhangen hoeveel mogelijkheden (i.e. rekenkracht) er beschikbaar zijn.
10x10 is niet zo relevant in Noord-Amerika, het is dus de vraag of hier fondsen beschikbaar voor komen.

ildjarn · Post by **ildjarn** » Wed Aug 01, 2007 07:40

Bert Zwart wrote:Moore's law ken ik niet.

http://en.wikipedia.org/wiki/Moore%27s_law

Rein Halbersma · Post by **Rein Halbersma** » Sat Aug 04, 2007 21:36

Bert Zwart wrote:Het aantal mogelijkheden alleen lijkt me niet zo relevant, als enkele slimme dammers het aantal relevante posities op slimme wijze weten te beperken zijn we vrij snel klaar. Moore's law ken ik niet. Veel zal afhangen hoeveel mogelijkheden (i.e. rekenkracht) er beschikbaar zijn.
10x10 is niet zo relevant in Noord-Amerika, het is dus de vraag of hier fondsen beschikbaar voor komen.

Bert, lees dit artikel van Schaeffer et al. eens: http://www.cs.ualberta.ca/~jonathan/Pap ... eckers.pdf
Hierin wordt uitgelegd welke mix van slim programmeren en damkennis er voor nodig is (was, inmiddels) om checkers op te lossen.