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.Bert Zwart wrote:Hebben we nog twintig jaar, of minder?Eric van Dusseldorp wrote:En als het niet teveel gevraagd is, graag volgens de internationale regels.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.

8x8 dammen uitgeanalyseerd door Chinook
-
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
-
- Posts: 713
- Joined: Wed Dec 17, 2003 10:51
Wellicht te simpel redenerend:Bert Zwart wrote:Hebben we nog twintig jaar, of minder?Eric van Dusseldorp wrote:En als het niet teveel gevraagd is, graag volgens de internationale regels.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.
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?
-
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
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).Jaap van Galen wrote:Wellicht te simpel redenerend:Bert Zwart wrote:Hebben we nog twintig jaar, of minder?Eric van Dusseldorp wrote: En als het niet teveel gevraagd is, graag volgens de internationale regels.
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?
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.
-
- Posts: 713
- Joined: Wed Dec 17, 2003 10:51
Het Haagse Milan-festival eist blijkbaar zijn tol ....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).
Ergens in de tweede helft van deze eeuw zijn we uitgeanalyseerd, dat lijkt dus een aardige voorspelling. Ik houd het vooralsnog op 2050.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.
We hebben nog even om ons er op voor te bereiden....
- Klaas van der Laan
- Posts: 898
- Joined: Wed Sep 24, 2003 13:19
- Real name: Klaas van der Laan
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.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....
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?
-
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
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.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?
-
- Posts: 2199
- Joined: Tue Sep 30, 2003 01:52
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.
10x10 is niet zo relevant in Noord-Amerika, het is dus de vraag of hier fondsen beschikbaar voor komen.
http://en.wikipedia.org/wiki/Moore%27s_lawBert Zwart wrote:Moore's law ken ik niet.
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
-
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Bert, lees dit artikel van Schaeffer et al. eens: http://www.cs.ualberta.ca/~jonathan/Pap ... eckers.pdfBert 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.
Hierin wordt uitgelegd welke mix van slim programmeren en damkennis er voor nodig is (was, inmiddels) om checkers op te lossen.