Rubik's Cube - oplossing in ≤ 20 bewegingen

Dit is de plek voor onzin, off-topic gebrabbel en idiote moppen.
David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door David » 31 aug 2010, 21:42

Je bedoelt:
op=op schreef:Het wordt ook nog de populairste puzzel aller tijden genoemd. Nou, dat ik schaken.
?

Ik las eens een uiteenzetting over de toekomst van de schaakcomputer. Het artikel dateerde volgens mij uit 2004. Daarin betoogde een man dat "schaak" opgelost is rond het jaar 4000. Wellicht volgt daar een "perfecte partij" uit.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
meneer van Hoesel
Vergevorderde
Vergevorderde
Berichten: 395
Lid geworden op: 20 apr 2010, 14:43
Locatie: Zwolle

Re: Rubik's Cube - breaking news

Bericht door meneer van Hoesel » 01 sep 2010, 16:08

wat een onzin uitspraak...

dwz dat we nog zo'n 2000 jaar te gaan hebben om het antwoord te berekenen....

even de praktijk...

vanuitgaande: ik krijg het voorelkaar om daar een geschikt algoritme voor te bedenken (en ook dat is niet erg ingewikkeld maar vraagt wat meer tijd als je het niet slim aanpakt)

stel ik bouw een super computer (en die zet je tegenwoordig zo in elkaar)
stel ik krijg een sponsor die voor mij zo'n tweede supercomputer financiert

dan heb ik van wege de gift de rekencapaciteit verdubbeld en daarmee de tijdsduur gehalveerd

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - breaking news

Bericht door op=op » 01 sep 2010, 17:15

Nou ja, het is maar wat je een onzinnige uitspraak vindt.

Schaken is (ik twijfel er niet aan dat iedere goede schaker dat met me eens is) een remisespel.
Dat wil zeggen, dat een partij pas niet in remise eindigt als een van beide partijen een fout maakt.
Dus zullen schaakpartijen tussen computers die alles kunnen doorrekenen altijd in een remise eindigen.
Jouw perfecte partij zal een saaie vertoning worden.

Een paar supercomputers inzetten om alles door te rekenen is een te simpele voorstelling van zaken. Als alle supercomputers op de wereld samenwerken is de rekenkracht nog te gering om alles door te rekenen.

Het wachten is op de quantumcomputer.
Het schaken is een spel tussen mensen. Hoe sterk een computer kan schaken is totaal oninteressant.
Er zijn mensen die de wortel uit een getal van 20 cijfer uit het hoofd kunnen uitrekenen. Dat maakt op mij indruk. Knap! Dat de computer dat nog veel sneller en met getallen met veel meer cijfers kan maakt op mij totaal geen indruk. Dom ding!.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door David » 01 sep 2010, 19:16

De mogelijkheid dat een supercomputer erbij komt (de rekencapaciteit kan verdubbelen) vernietigt elke voorspelling. De rekenkracht kan onder een voorspelling ook bijv. verduizendvoudigen, en zo kan alles veel sneller worden gevonden. In de praktijk lijkt het me moeilijk te verdedigen dat voorspellingen zo gefalsificeerd kunnen worden. Verder moet je ervanuit gaan dat er onder het algoritme geen partij 2 keer wordt nagelopen.

Een perfecte partij of een lijkt me ook niet interessant. Het laat mij alleen zien dat mensen kunnen programmeren, niet dat ze kunnen schaken.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door tsagld » 02 sep 2010, 11:39

Het laat niet eens zien dat mensen kunnen programmeren. Naarmate de rekenkracht van een computer toeneemt, neemt de noodzaak tot het verzinnen van slimme algoritmes af.

De mensen die 20 jaar geleden schaakprogramma's schreven, die konden programmeren. Er wordt steeds meer met brute force gedaan. Logisch ook...

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door Sjoerd Job » 02 sep 2010, 13:34

tsagld schreef:Naarmate de rekenkracht van een computer toeneemt, neemt de noodzaak tot het verzinnen van slimme algoritmes af.
Onjuist, het wordt alleen minder gedaan.

Hoe vaak heb je niet dat je moet wachten op een computerprogramma, die even niet spoedig reageert? Ik stoor mij regelmatig aan het feit dat bepaalde programma's niet soepel reageren.
Zelfs spelletjes laten dit al duidelijk zien. Wie kent er nog een goed spel uit de oude tijd? Bijvoorbeeld "Wacky Wheels", dat draaide echt lekker, zelfs op mijn stokoude computer.
En dan nu? Ik heb een vrij krachtige laptop. Simpele racespelletjes draaien soms amper, desondanks mijn dedicated grafische kaart, Op de pc van mijn vrouw, met onboard kaart draait het zeker slomer.

Ook tekstverwerkers

Er wordt nu TE vaak gedacht: De PC's zijn toch wel snel, dus wij hoeven geen moeite te doen. Met enkele minuten denken, of misschien zelfs een uurtje, kan het algoritme sneller, zodat talloze mensen minder lang hoeven te wachten.

De `noodzaak' van slimmere algoritmes blijft. Het sorteren van rijen bijvoorbeeld heeft al genoeg slimme algoritmes. Toch word vaak een dommer algoritme gekozen omdat het simpeler is om te schrijven, en men gaat er van uit dat het toch wel snel genoeg is! Totdat er iemand aan komt die een stukken groter databestand heeft dan verwacht, en dan had het toch weer een uur kunnen schelen.

Naarmate de tijd vordert, worden computers sneller, maar de gegevens die we gaan verwerken worden ook meer!
``Life is complex. It has real and imaginary parts.''

Gebruikersavatar
meneer van Hoesel
Vergevorderde
Vergevorderde
Berichten: 395
Lid geworden op: 20 apr 2010, 14:43
Locatie: Zwolle

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door meneer van Hoesel » 02 sep 2010, 16:38

Gelukkig wordt er nog wel veel aan 'code optimisation' gedaan, waardoor bijvoorbeeld de JavaScript engine op de ene browser beduidend sneller is dan op de andere.

Maar de algemene trend is helaas wel dat weinig developpers zich druk maken om de efficientie waarme de programma code wordt uitgevoerd.

Het best zou zijn dat we en snellere hardware krijgen EN betere code.

pppp
Vast lid
Vast lid
Berichten: 96
Lid geworden op: 13 apr 2010, 20:17

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door pppp » 09 sep 2010, 21:29

Er wordt heus nog wel een hoop gedaan aan snelheids optimalisatie. Vergeet niet dat software nu vele malen complexer is dan 20 jaar geleden. Waar gebruiksvriendelijkheid voorop staat worden er soms keuzes gemaakt die ten koste van snelheid kunnen gaan.
Er wordt bij veel bedrijven volgens standaarden (design patterns, platforms) en met kwaliteitscontrole gewerkt (paired programming, korte iteraties, unit-, integratie en acceptatietests). En ja, de wil om echt goede code te schrijven is soms ondergeschikt aan het financiele belang; goede code is namelijk duur.
Waar over het algemeen wel heel wat meer aandacht aan besteed zou moeten worden is multi-core cq. Parallel programmeren. We hebben nu allemaal 2, 4 of zelfs 6 cores ter beschikking, maar worden amper gebruikt.
Hopelijk brengt de release van .NET 4.0 met haar parallel extensions hier verandering in.

Gebruikersavatar
meneer van Hoesel
Vergevorderde
Vergevorderde
Berichten: 395
Lid geworden op: 20 apr 2010, 14:43
Locatie: Zwolle

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door meneer van Hoesel » 09 sep 2010, 22:02

pppp schreef:Waar over het algemeen wel heel wat meer aandacht aan besteed zou moeten worden is multi-core cq. Parallel programmeren. We hebben nu allemaal 2, 4 of zelfs 6 cores ter beschikking, maar worden amper gebruikt.
Hopelijk brengt de release van .NET 4.0 met haar parallel extensions hier verandering in.
ik zou zeggen, stap over op MacOS op een fatsoenlijke machine. Dan heb je nog hele leuke dingen uit te pluizen, zoals OpenCL - volgens mij krijg je met een mooie PowerMac en een paar extra grafische kaarten een echte 'number cruncher' ter beschikking :)

MacOS X technology

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door op=op » 10 sep 2010, 07:35

@pppp:
Hoe kom je erbij dat software nu vele malen complexer is dan 20 jaar geleden. Het tegendeel is het geval.
En op slimme code zit ook niemand te wachten. Wel op slimme ontwerpen. De code moet niet slim maar transparant zijn, zodat eventuele fouten snel (ook door een ander) kunnen worden achterhaald.
Dat is ook de reden voor het gebruik van design patterns en de verdeling in hapklare brokken (platforms).
Wat wel een punt is, is dat er te weinig object-georienteerd wordt gewerkt. Het probleem is dat de leiding verliefd is op controle en mijlpalen. Dat werkt niet met OO, dat een groeiproces is. Vandaar die voorliefde voor kwaliteitscontrole. Het probleem is ook niet dat het ontbreekt aan goede code, maar aan goede programmeurs (die schrijven automatisch goede code).
Parallel programmeren is een steeds weer opnieuw opduikend ideaal. Dat wordt niets. En je hoop op .NET 4.0 vind ik hopeloos, zoals het gehele .NET project een ramp is gebleken.

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door Sjoerd Job » 10 sep 2010, 09:22

Parallel programmeren klinkt inderdaad als `moeten we doen', terwijl juist in parallelle code de mogelijkheden voor fouten groter worden:
- deadlocks
- race condities
- (etcetera?)
Om hier omheen te werken heb je of heel veel kennis en ervaring nodig, of je moet hier een goede library voor hebben.

Het OS zou hier de uitkomst moeten bieden: Verschillende applicaties automatisch op verschillende cores starten, of een automatische `core transfer' wanneer een core overlast wordt. Zo kunnen we meer applicaties draaien, die mooier verspreid zijn over de cores.
``Life is complex. It has real and imaginary parts.''

Gebruikersavatar
meneer van Hoesel
Vergevorderde
Vergevorderde
Berichten: 395
Lid geworden op: 20 apr 2010, 14:43
Locatie: Zwolle

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door meneer van Hoesel » 10 sep 2010, 10:00

op=op schreef:Parallel programmeren is een steeds weer opnieuw opduikend ideaal. Dat wordt niets.
even voor de duidelijkheid.... wat verstaan we onder parallel-computing?

want als het alléén maar zou gaan om 'domme' desktop applicaties als tekstverwerking of een e-mailtje lezen, dan kan het OS en de Kernel weinig anders doen als een reeks systeem taken zoals een toets aanslag (en alle honderd andere dingen die het ondertussen moet doen die om de hoek komen zeilen doordat we een muziekje afspelen of een mail-server checken etc...) - een reeks systeem routines dispatchen over verschillende 'cores' --- en die staan dus allemaal lekker niks te doen.

Zware systeem taken als een videootje afspelen of een 3D wereld renderen worden voor een groot deel door de grafisch kaart opgevangen - en blijken nou net die dingen te beschikken over tientallen of honderden cores en er daar dus op 'machinetaal niveau' de zaak gesplitst wordt in 'parallel' verwerking.

Blijven er nog een paar 'number crunchers' open te staan op de lijst voor 'echte parallel-computing', SETI, SPSS, photoshop (die moeten eens opschieten), Simulaties etc...
Ik mag toch hopen dat die jongens hun verstand gebruiken en wèl weten hoe ze moeten programeren????

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door tsagld » 10 sep 2010, 10:28

zoals het gehele .NET project een ramp is gebleken
Huh? Waar staaf je dat mee? Microsoft vaart er wel bij, en bovendien, het is mijn brood.

V.w.b. de discussie, ik heb alleen maar gezegd dat de noodzaak afneemt. Niet dat het verdwijnt. Daar waar men snelle response verwacht blijft de noodzaak. Maar voor het doorrekenen van 'de perfecte schaakpartij' is het minder van belang. Je kunt twee maanden spenderen aan het optimalizeren van je code, of aan processortijd...

Gebruikersavatar
meneer van Hoesel
Vergevorderde
Vergevorderde
Berichten: 395
Lid geworden op: 20 apr 2010, 14:43
Locatie: Zwolle

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door meneer van Hoesel » 10 sep 2010, 10:50

tsagld schreef:Je kunt twee maanden spenderen aan het optimalizeren van je code, of aan processortijd...
Gezien de stelling omtrent de schaakpartij kun je volgens mij beter 2 maand spenderen aan optimalisatie, dat lijkt me sneller terug verdiend te zijn, zelfs als de berekening maar een 0,01% sneller wordt - en dan heb ik het alléén maar over de faktor 'tijd'

ik vraag me af wat duurder is, 2 maand processortijd op een 'Blue/Gene' of een 'Cray/Jaguar' - of 2 maand programmeren

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door op=op » 10 sep 2010, 12:02

Ik weet niet wat je nu wilt met het programmeren van het schaakspel.
Op het moment is het zo dat een stijging in ELO rating van 3 punt neerkomt op een verdubbeling van code (de waarderingsfunctie moet daarvoor flink worden uitgebreid).
(N.B. De getallen komen uit de dikke duim, het is maar dat mijn punt duidelijk wordt).
Als je nu wist bij welke ELO rating de computer niet meer beter kan (m.a.w. als hij kan winnen zal hij winnen, als hij nog remise kan maken zal hij remise maken en winnen bij een foutje van de tegenstander),
dan weet je waar je naar toe moet werken. Nu blijft de situatie wazig.

Wat de .NET ramp betreft, dat is mijn prive mening. Als je M$ volgt heb je nu tig .NET versies (van niet malse grootte) op je pc staan. Tijd om opnieuw te beginnen bij versie 1.0, maar het dan meteen goed doen en ditmaal de voorgenomen eigen convensies handhaven. Er is al rommel genoeg op mijn pc.

Plaats reactie