Deep Blue vs Deep Blue

[jaapstobbe]

Ik vraag mij af wat er gebeurt als je 2 schaakcomputers tegen elkaar zou laten spelen. Laten we voor het gemak even aannemen dat dat de meest krachtige van het moment zijn, maar wel 2 identieke. Zou de machine die met wit begint dan altijd winnen? Of juist altijd remise?

[ShellGhost]

Moeilijke, denk dat remise een goede kans heeft...
Een computer zal nooit verder denken dan dat z'n programma hem toelaat...

[posttoast]

Wat let je om het te proberen? Gewoon met een simpele schaakgame.

[CrashOne]

posttoast schreef op maandag 12 september 2005 @ 16:42:
Wat let je om het te proberen? Gewoon met een simpele schaakgame.

ehm, ik neem aan dat hij niet in bezit is van 1 of beide machines.

Maar het lijkt mij dat het er aan ligt welke routines het best zijn geprogrammeerd.

[RobIII]

CrashOne schreef op maandag 12 september 2005 @ 16:59:
[...]


ehm, ik neem aan dat hij niet in bezit is van 1 of beide machines.

Maar het lijkt mij dat het er aan ligt welke routines het best zijn geprogrammeerd.

Wellicht bezit hij geen 2 "deep blue's", maar wel een ander stukje schaak-software (die overigens zelfs als freeware te verkrijgen is). Daarmee kun je het natuurlijk ook (alhoewel dus wel op "kleinere schaal") proberen.

[ Voor 24% gewijzigd door RobIII op 12-09-2005 17:04 ]

[posttoast]

CrashOne schreef op maandag 12 september 2005 @ 16:59:
[...]


ehm, ik neem aan dat hij niet in bezit is van 1 of beide machines.

Maar het lijkt mij dat het er aan ligt welke routines het best zijn geprogrammeerd.

Of je nou een supercomputer gebruikt of een 286: zolang je 2x dezelfde gebruikt lijkt het me geen verschil maken.

[Rac-On]

je kan natuurlijk een simpel stuk schaaksoftware 2 keer opstarten en op die manier tegen elkaar laten spelen (bij de ene software speel je zwart, bij de andere wit en je voert de zetten van de compu in in het andere programma) en kijken wat er gebeurd.

[Hu9o]

Doe deze test wel vaker dan 1 keer, anders zal het niet representatief zijn.

[Oscar Mopperkont]

Ben wel benieuwd wat er gebeurt als je 1 van beide (of beide) machines ook nog de informatie "meegeeft" dat de tegenstander hetzelfde denkt als hij. Lijkt me dat die informatie handig kan zijn met het doorrekenen van scenario's.

[Shin_Alu]

In principe gaan dit soort programma's ook uit van de beste zet van de tegenstander, dus 'weten' dat de ander hetzelfde geprogrammeerd is, zou weinig uit moren maken

[Oscar Mopperkont]

Shin_Alu schreef op maandag 12 september 2005 @ 17:08:
In principe gaan dit soort programma's ook uit van de beste zet van de tegenstander, dus 'weten' dat de ander hetzelfde geprogrammeerd is, zou weinig uit moren maken

Neem aan dat dit soort programma's gebruik maken van meer dan dat alleen. Zal tcoh wel meer kansrekening in zitten. Als het puur zou uitgaan van alleen de beste zet van een tegenstander en daar dus een 100% kans aan zou toedichten, dan zou het de overige zetten negeren en geen rekening meer houden met die scenario's, wat natuurlijk heel fout kan uitpakken.

[Hu9o]

Oscar Mopperkont schreef op maandag 12 september 2005 @ 17:04:
Ben wel benieuwd wat er gebeurt als je 1 van beide (of beide) machines ook nog de informatie "meegeeft" dat de tegenstander hetzelfde denkt als hij. Lijkt me dat die informatie handig kan zijn met het doorrekenen van scenario's.

Daar heb je weinig aan, omdat de zet van de tegenstander bepalend is van je eigen zet. Dus als de tegenstander move A doet, dan doe ik dit en als hij move B doet, dan doe ik dat. (maw, het is geen kwestie van, alvast deze zet doen).

Trouwens, de software weet al wat de tegenstander zal gaan doen, omdat de regels voor het schaken bekend zijn bij beide programma's en omdat de programma's hetzelfde zijn. Hierdoor hoef je alleen maar te schakelen naar, wat zou ik in zo'n situatie doen.

[ Voor 6% gewijzigd door Hu9o op 12-09-2005 17:13 ]

[heuveltje]

Overigens zit er in programma's ook een randomachtige functie. anders zou hij altijd dezelfde opening doen. ik denk dat dat ook een meer random verhouding zal laten ontstaan,

overigens wel een interesante test om eens te doen !

[SilentStorm]

Mja, er zijn een hoop verschillende technieken om een computer te laten schaken; ik heb het hierbij vooral over het algoritme voor de kunstmatige intelligentie die de zetten moet berekenen. De normale gang van zaken is om eerst een zettenlijst te genereren, met alle mogelijke zetten. Daarna geef je elke zet een waarde (goede / slechte zet). Uiteindelijk maak je een beslissing.

Er zijn dus 3 punten waarop er bij de ene computer een ander besluit kan worden genomen dan de andere computer. De eerste is het onwaarschijnlijkst. Uitgaande van een situatie waarin 2 zetten een gelijke waarde krijgen (wat bij goed programmeerwerk bijna niet voor zou komen), kun je door de volgorde van gegenereerde zetten te veranderen een andere keuze krijgen voor een zet.
Het toewijzen van een waarde hangt bij vooral wat geavanceerdere schaakcomputers niet alleen af van de kans op het al of niet kwijtraken/slaan van stukken, maar ook op bv de fase van het spel. (de variabelen die de keuze bepalen zijn verschillend bij begin, midden en endgame).

Het maken van de beslissing hoeft niet noodzakelijk de beste te zijn. Als een aantal waarden erg dicht bij elkaar liggen, zou de computer een (semi)random keuze kunnen maken tussen deze mogelijkheden.

Tot slot hebben een hoop schaakcomputers nog hun eigen 'extra'tjes. Een voorbeeld is bv de 'contempt'-factor. Als de tegenstander een hoop zetten doet, die volgens de computer erg inefficient zijn, kan deze bv meer risico gaan nemen met de volgende zet (en zo verder).

[Zoijar]

Zo train je juist een schaakcomputer, door hem (haar?) tegen zichzelf te laten spelen. Er wordt geen "perfecte" min-max gebruikt, sowieso is je zoek diepte beperkt. Verder gebruiken computers op dit niveau ook partij databases, bord stand wegingen, genetische algoritmes (oa. random afwijking om te voorkomen op een lokaal maximum uit te komen), tegenstander analyse, etc, etc. Waarschijnlijk zal het dus elke partij weer anders zijn, en waarschijnlijk ook steeds op hoger niveau.

[Resistor]

[disclaimer]
- Ik kan zelf niet schaken
- Ik weet niet hoe geavanceerd schaakcomputers zijn
[/dislaimer]

Als de computers niet zelflerend zijn denk ik dat er steeds op de zelfde manier gespeeld gaat worden, en de computers alleen maar de meest logische stappen zetten, die een aantal zetten later het gewenste resultaat oplevert (kansrekening)
Als de computers wel zelflerend zijn (kunnen leren hoe de tegenstander op bepaalde zetten reageert) zou ik niet weten wat er gaat gebeuren, omdat er dan zo'n beetje oneindig veel combinaties mogelijk zijn. Ik denk continue remise.

[Solomon]

Resistor schreef op maandag 12 september 2005 @ 19:42:
[disclaimer]
- Ik kan zelf niet schaken
- Ik weet niet hoe geavanceerd schaakcomputers zijn
[/dislaimer]

Als de computers niet zelflerend zijn denk ik dat er steeds op de zelfde manier gespeeld gaat worden, en de computers alleen maar de meest logische stappen zetten, die een aantal zetten later het gewenste resultaat oplevert (kansrekening)
Als de computers wel zelflerend zijn (kunnen leren hoe de tegenstander op bepaalde zetten reageert) zou ik niet weten wat er gaat gebeuren, omdat er dan zo'n beetje oneindig veel combinaties mogelijk zijn. Ik denk continue remise.

Nee, een computer maakt ook random zetten, ook al heeft de ene zet de voorkeur. Anders zou je tegen een schaakcomputer steeds hetzelfde spel kunnen spelen!

[Janoz]

Dat is natuurlijk wel een leuke test. Mocht het geheel onafhankelijk zijn van kans dan moet er telkens hetzelfde potje uit rollen. Ik denk echter dat uberhaupt de eerste zet al afhankelijk is van kans, maar misschien als je zelf de eerste paar zetten mag doen.....

[Sprite_tm]

Het hangt compleet van de chess-engine af. Ik heb het even met gnuchess geprobeerd: die heeft een commandline en als je daar het commando 'go' op geeft gaat 'ie meteen de zet van de speler die aan de beurt is zetten. Doe dus vaak 'go' en hij speelt zelf een spelletje.

Ik zal zo eens een paar potjes draaien en een zut stats opzetten. Dat kan alleen wel even duren; zelfs op mijn 3200+ kost een zet een seconde of 5.

[SilentStorm]

Sprite_tm schreef op maandag 12 september 2005 @ 21:27:
Het hangt compleet van de chess-engine af. Ik heb het even met gnuchess geprobeerd: die heeft een commandline en als je daar het commando 'go' op geeft gaat 'ie meteen de zet van de speler die aan de beurt is zetten. Doe dus vaak 'go' en hij speelt zelf een spelletje.

Ik zal zo eens een paar potjes draaien en een zut stats opzetten. Dat kan alleen wel even duren; zelfs op mijn 3200+ kost een zet een seconde of 5.

waarschijnlijk heeft ie een limiet van 5 sec, en probeert ie ongeacht de processor zoveel mogelijk zetten te analyseren. Mogelijk kun je het ook ergens aanpassen

---

Al klinkt het best leuk om er wat analyses op los te laten; ik ben bang dat je alleen hele specifieke antwoorden (per schaakbot) krijgt.. Volgens mij is het veel interessanter om eens te kijken wat voor techniek aan de basis ligt. Zie hier bijvoorbeeld.

[Tinuz___]

Ik heb eerlijk gezegd mijn twijfels of dit zo'n interessant experiment is. Bij een eenvoudig schaakprogramma zijn de uitkomsten waarschijnlijk te voorspelbaar. Als je uitgaat van een echt geavanceerde schaakcomputer als Deep Blue wordt dit experiment veel ingewikkelder, dan moet je waarschijnlijk flink wat beginparameters meegeven om zijn speelstijl te bepalen. Er bestaat niet zoiets simpels als dé optimale strategie. Kies je de strategiën gelijk en er wordt om en om met wit gespeeld dan denk ik dat de resultaten, bij enigzins intelligent gekozen parameters, convergeren naar remise.

Op http://www.chessgames.com/ staat trouwens een erg interessante database waarin een hele berg partijen tussen schaakgrootmeesters, ook vele klassiekers, zijn vastgelegd. Je kunt oa vanuit een bepaalde stelling (mits deze in de db voorkomt) de langetermijnkansen op winst, remise en verlies vinden van alle vervolgzetten die ooit gedaan zijn. Dus met name bij het beginspel kan je veel mogelijkheden vinden en "aan de hand van een grootmeester" doorspelen.

[jaapstobbe]

Tinuz___ schreef op dinsdag 13 september 2005 @ 00:33:
Ik heb eerlijk gezegd mijn twijfels of dit zo'n interessant experiment is. Bij een eenvoudig schaakprogramma zijn de uitkomsten waarschijnlijk te voorspelbaar. Als je uitgaat van een echt geavanceerde schaakcomputer als Deep Blue wordt dit experiment veel ingewikkelder, dan moet je waarschijnlijk flink wat beginparameters meegeven om zijn speelstijl te bepalen. Er bestaat niet zoiets simpels als dé optimale strategie. Kies je de strategiën gelijk en er wordt om en om met wit gespeeld dan denk ik dat de resultaten, bij enigzins intelligent gekozen parameters, convergeren naar remise.

Convergeren naar remise of convergeren naar gelijkspel(wit wint steeds) ?

[Tinuz___]

jaapstobbe schreef op dinsdag 13 september 2005 @ 07:41:
Convergeren naar remise of convergeren naar gelijkspel(wit wint steeds) ?

Winst zou mooi zijn, er zal ook ongetwijfeld af en toe een winstpartij uitrollen, maar als je er vanuit gaat dat een computer leert van voorgaande spelen moet het haast wel convergeren naar remise. Tenzij je uiteindelijk een strategie weet te vinden die voor wit altijd winst oplevert, zo'n beetje de heilige graal van het schaken. Maar als zo'n strategie al zou bestaan denk ik dat deze eerder wordt gekraakt door hier een supercomputer aan te laten rekenen.

[Rey Nemaattori]

posttoast schreef op maandag 12 september 2005 @ 17:02:
Of je nou een supercomputer gebruikt of een 286: zolang je 2x dezelfde gebruikt lijkt het me geen verschil maken.

Beide partijen zullen namelijk nooit dezelfde zetten doen, dus zullen ze nooti hetzelfde reageren...

Zoijar schreef op maandag 12 september 2005 @ 19:38:
Zo train je juist een schaakcomputer, door hem (haar?) tegen zichzelf te laten spelen. Er wordt geen "perfecte" min-max gebruikt, sowieso is je zoek diepte beperkt. Verder gebruiken computers op dit niveau ook partij databases, bord stand wegingen, genetische algoritmes (oa. random afwijking om te voorkomen op een lokaal maximum uit te komen), tegenstander analyse, etc, etc. Waarschijnlijk zal het dus elke partij weer anders zijn, en waarschijnlijk ook steeds op hoger niveau.

Het is dan nog maar de vraag in hoeverre er gebruik word gemaakt van een geschiedenis van gespeelde partijen....

Tinuz___ schreef op dinsdag 13 september 2005 @ 00:33:
Ik heb eerlijk gezegd mijn twijfels of dit zo'n interessant experiment is. Bij een eenvoudig schaakprogramma zijn de uitkomsten waarschijnlijk te voorspelbaar. Als je uitgaat van een echt geavanceerde schaakcomputer als Deep Blue wordt dit experiment veel ingewikkelder, dan moet je waarschijnlijk flink wat beginparameters meegeven om zijn speelstijl te bepalen. Er bestaat niet zoiets simpels als dé optimale strategie. Kies je de strategiën gelijk en er wordt om en om met wit gespeeld dan denk ik dat de resultaten, bij enigzins intelligent gekozen parameters, convergeren naar remise.

En dan kun je ook nog tussendoor laten switchen van stijl/strategie, maar dit is bij beide partijen afhankelen van dezelfde variabelen...

[ Voor 30% gewijzigd door Rey Nemaattori op 13-09-2005 09:33 ]

[Sprite_tm]

Nou, gnuchess heeft er zeker ook een random factor bij (of leert van z'n fouten, maar afaik is dat niet zo.) Ik heb helaas geen mooie statistiekjes (mijn scriptje had 'n foutje erinzitten) maar ik zag wel dat over de duur van tig potjes zowel zwart als wit wonnen.

[Tinuz___]

Sprite_tm schreef op dinsdag 13 september 2005 @ 11:49:
Nou, gnuchess heeft er zeker ook een random factor bij (of leert van z'n fouten, maar afaik is dat niet zo.) Ik heb helaas geen mooie statistiekjes (mijn scriptje had 'n foutje erinzitten) maar ik zag wel dat over de duur van tig potjes zowel zwart als wit wonnen.

Maar wat is dan de waarde van zo'n uitkomst? Hoe interpreteer je het resultaat? Het lijkt me op z'n minst essentieel om van te voren vast te leggen wat voor type engine je gebruikt (wat voor beslissingsalgoritme, al dan niet zelflerend) hoeveel zetten je vooruit denkt, of je een database met gespeelde partijen gebruikt etc. etc.

[Verwijderd]

Het zal afhangen van de instellingen. Als beide computers op safe spelen rolt er waarschijnlijk vaak remise uit: Er zijn genoeg openingen die zo in remise eindigen. Daarentegen zullen agressievere instellingen tot meer winst leiden, doordat de partij dan makkelijker door een kleine fout uit evenwicht raakt. Net als in grootmeesterpartijen...

100 procent remise zal het in ieder geval nooit worden (in ieder geval niet zolang niet telkens dezelfde partij gespeeld wordt): daarvoor is het geheel niet symmetrisch genoeg. Doordat de spelers niet tegelijk aan zet zijn, zullen zij niet exact dezelfde search-trees doorlopen en bestaat dus de kans dat de ene speler een stelling evalueert die de ander gemist heeft.

Ik vermoed overigens dat het aantal remises erg hoog zal zijn ongeacht de instellingen: Computers maken veel minder tactische fouten dan mensen, en bovendien kunnen ze elkaars strategische fouten (die computers meer maken dan grootmeesters) niet goed afstraffen.

[ Voor 3% gewijzigd door Verwijderd op 13-09-2005 13:19 ]

[the_stickie]

Chessmaster speelt meestal, maar niet altijd, remise als hij tegen zichzelf speelt.
De niet remise-matchen zijn vrij toevallig verdeeld...

volgens mij is dat de gewoon de random die erin zit...

[Guru Evi]

Deep Blue heeft een team wetenschappers erachter steken heeft die zo nu en dan de algoritmes beter updaten (ik weet niet of het tijdens het spel ook was). Dus de beste wetenschapper-team zou winnen.

Als je 2 pc's tegen elkaar laat spelen ga je volgens de wetten van de wiskunde altijd uitkomen op evenveel winsten als verliezen en eventueel een hoop remises.

Het probleem met schaken en andere spelen is dat je op verschillende manieren kunt beginnen, anticiperen en eindigen. Daar is de random functie voor (welk stuk verzet je vb. eerst). Als je een perfecte random functie hebt denk ik dat je dus een gelijke score gaat halen na een tijd.

Ook moet je kunnen leren uit je fouten, iets wat moeilijk te implementeren is. Bij een klassieke (evolutie-gebaseerde) leerfunctie zal de eerstwinnende computer het meest winnen daar de goede oplossingen gehouden worden, de slechte verworpen. Je kunt dit natuurlijk oplossen door je spel verder te analyseren maar ja...

[RobIII]

Verwijderd schreef op dinsdag 13 september 2005 @ 13:17:
Ik vermoed overigens dat het aantal remises erg hoog zal zijn ongeacht de instellingen: Computers maken veel minder tactische fouten dan mensen, en bovendien kunnen ze elkaars strategische fouten (die computers meer maken dan grootmeesters) niet goed afstraffen.

Ook een goede: Computers raken niet vermoeid na uren spelen, mensen wel. En dat gaat leiden tot meer fouten.

[hanhoo]

De theorie leidt wat mij betreft inderdaad naar het feit dat er altijd een remise gespeeld moet worden.

Echter gaat die stelling alleen op als alle factoren gebaseerd zijn op logica. Ik heb ooit eens een film gezien waarbij een computer van de amerikaanse defensie aan het einde van de film Tic Tac Toe tegen zichzelf speelde. Deze kwam er uiteindelijk achter dat het zinloos is omdat het resultaat altijd hetzelfde is: remise. Dat komt voornamelijk omdat de regels van Tic Tac Toe heel logisch en rechtlijnig zijn. Er is geen deceptie of ondoorzichtelijke strategie mogelijk. De regels en pionnen in het spel zijn in elke situatie gelijkwaardig.

Nu het schaakspel. De logica daar is moeilijker te zoeken. Niet alle regels en stukken zijn gelijkwaardig aan elkaar. Dat leidt tot miljoenen mogelijkheden, strategien en scenario's. De theorie volgende leidt mij tot de volgende conclusie:

1) Deep Blue vs Deep Blue starten beiden met een blanco "intelligentie". Zij starten louter met de basisregels van het schaken.
2) Winst van de eerste partij is dan volledig random. Tijdens de partij bouwen beiden intelligentie op
3) De Deep Blue die het meeste fouten maakt leert het meest (verdediger). De winnende Deep Blue bouwt de meeste strategien op.
4) Resultaat: er zal uiteindelijk 1 van de twee Deep Blue's blijven winnen. Degene die er het meest van heeft opgestoken. Die loopt namelijk altijd een stapje voor op de ander.

Bottomline is dat tijdens het spelen van de spellen de ene een andere logica op het spel ontwikkeld dan de ander. Interessant wordt het pas als je vervolgens de ervaringen uitwisseld tussen de twee.

[Zoijar]

Guru Evi schreef op woensdag 14 september 2005 @ 19:03:
Als je 2 pc's tegen elkaar laat spelen ga je volgens de wetten van de wiskunde altijd uitkomen op evenveel winsten als verliezen en eventueel een hoop remises.

Ook moet je kunnen leren uit je fouten, iets wat moeilijk te implementeren is. Bij een klassieke (evolutie-gebaseerde) leerfunctie zal de eerstwinnende computer het meest winnen daar de goede oplossingen gehouden worden, de slechte verworpen. Je kunt dit natuurlijk oplossen door je spel verder te analyseren maar ja...

Dat is niet waar, de eerst winnende computer kan wel op een lokaal maximum lopen, daar de eerst verliezende computer het eerst slechter doet om vervolgens een beter maximum te vinden dan het lokale maximum van de eerste winnaar. Dit gaat ook op voor je eerste stelling over gelijke aantal winst en verlies partijen; dat hoeft helemaal niet.

[RobIII]

hanhoo schreef op donderdag 15 september 2005 @ 14:42:
1) Deep Blue vs Deep Blue starten beiden met een blanco "intelligentie". Zij starten louter met de basisregels van het schaken.
2) Winst van de eerste partij is dan volledig random. Tijdens de partij bouwen beiden intelligentie op
3) De Deep Blue die het meeste fouten maakt leert het meest (verdediger). De winnende Deep Blue bouwt de meeste strategien op.
4) Resultaat: er zal uiteindelijk 1 van de twee Deep Blue's blijven winnen. Degene die er het meest van heeft opgestoken. Die loopt namelijk altijd een stapje voor op de ander.

And now put those two together.... huh? huh? See what I mean?
/Joey mode...

Meer serieus: Als je beide DB's (Deep Blue's) zou koppelen met hun kennis om daar beide weer van te profiteren... wat zou er dan gebeuren? Ergens moet het dan toch ophouden? Of het "ideale potje schaak" gevonden worden? Lijkt me... Let wel dat ik geen uitspraak doe over de termijn waarna dit zou gebeuren, dat is namelijk niet te zeggen. Maar het is een "eindige" verzameling mogelijke zetten, dus érgens moet er iets uit komen lijkt me.

[ Voor 13% gewijzigd door RobIII op 15-09-2005 17:34 ]

[hanhoo]

RobIII schreef op donderdag 15 september 2005 @ 17:33:
[...]

And now put those two together.... huh? huh? See what I mean?
/Joey mode...

Meer serieus: Als je beide DB's (Deep Blue's) zou koppelen met hun kennis om daar beide weer van te profiteren... wat zou er dan gebeuren? Ergens moet het dan toch ophouden? Of het "ideale potje schaak" gevonden worden? Lijkt me... Let wel dat ik geen uitspraak doe over de termijn waarna dit zou gebeuren, dat is namelijk niet te zeggen. Maar het is een "eindige" verzameling mogelijke zetten, dus érgens moet er iets uit komen lijkt me.

Hmm, zo even nadenkend lijkt mij er een eenvoudig antwoord op deze vraag:

Het gaat net zolang door totdat de capaciteiten van Deep Blue zijn bereikt. Dus de oneindigheid wordt ge-eindigd door de fysieke beperking. Tenzij Deep Blue een dergelijke kunstmatige intelligentie heeft ontwikkeld dat het zijn eigen capaciteit kan uitbreiden. Conform de film "There is no spoon".

[RobIII]

hanhoo schreef op donderdag 15 september 2005 @ 17:50:
[...]


Hmm, zo even nadenkend lijkt mij er een eenvoudig antwoord op deze vraag:

Het gaat net zolang door totdat de capaciteiten van Deep Blue zijn bereikt. Dus de oneindigheid wordt ge-eindigd door de fysieke beperking. Tenzij Deep Blue een dergelijke kunstmatige intelligentie heeft ontwikkeld dat het zijn eigen capaciteit kan uitbreiden. Conform de film "There is no spoon".

Ik denk eerlijk gezegd dat het aantal zetten/strategieën (de nuttige dan natuurlijk) eerder "eindig" is dan een bult GB's (geheugen/hd's/whatever) met die gegevens. (En i.p.v. GB's kun je natuurlijk wellicht beter TB's, PB's of EB's lezen )

[Zoijar]

RobIII schreef op donderdag 15 september 2005 @ 17:55:
Ik denk eerlijk gezegd dat het aantal zetten/strategieën (de nuttige dan natuurlijk) eerder "eindig" is dan een bult GB's (geheugen/hd's/whatever) met die gegevens. (En i.p.v. GB's kun je natuurlijk wellicht beter TB's, PB's of EB's lezen )

Je beseft dat schaken over getallen in de richting van 10^50 gaat, en 10^130 oid bij beperkte brute force? Dat 'EB's' daar niet bij in de buurt komen, in verre na niet. Voor de eerste 6 zetten zijn er bv al 119,060,324 mogelijkheden. Ter vergelijk, als het bekende universum met neutronen wordt bepakt dan zijn dat er zo'n 10^128, een huidige deeltjes schatting komt op iets van 10^85

Anyway schaken is maar een kinder spelletje voor computers; de echte stoere computers rekenen aan Go

[Ivo]

De beste Go computers worden dan ook resoluut verslagen door een bovengemiddelde Go-speler. Dat is ook niet zo raar, want een Go spel heeft 19*19 = 361 plaatsingsmogelijkheden. Elke zet heeft implicaties op een heleboel niveaus van het spel. Een zet die lokaal erg sterk lijkt kan globaal een ramp veroorzaken. Een mens rekent wel een aantal mogelijkheden door, maar tegelijkertijd gebruik je intuïtie om te kijken hoe de stand van zaken globaal veranderd en dat kan een computer niet.

[RobIII]

Zoijar schreef op donderdag 15 september 2005 @ 19:12:
[...]

Je beseft dat schaken over getallen in de richting van 10^50 gaat, en 10^130 oid bij beperkte brute force? Dat 'EB's' daar niet bij in de buurt komen, in verre na niet. Voor de eerste 6 zetten zijn er bv al 119,060,324 mogelijkheden. Ter vergelijk, als het bekende universum met neutronen wordt bepakt dan zijn dat er zo'n 10^128, een huidige deeltjes schatting komt op iets van 10^85

Anyway schaken is maar een kinder spelletje voor computers; de echte stoere computers rekenen aan Go

Ja, leuk allemaal die "mogelijkheden". Maar als je gaat beperken naar de "nuttige/zinvolle" zetten (en daar gaat het om bij schaken) dan kun je denk ik al heel hard beperken. Neemt niet weg dat EB's wellicht ook nog wat aan de krappe kant zijn, maar you get my drift Enniewee, daar ging deze discussie verder ook niet over en ik zal deze offtopic dan ook van mijn kant iig smoren in de kiem

[Ivo]

De computer zal toch echt alle mogelijkheden moeten bekijken wil hij zeggen wat zinvol is en wat niet.

[RobIII]

Ivo schreef op zaterdag 17 september 2005 @ 00:10:
De computer zal toch echt alle mogelijkheden moeten bekijken wil hij zeggen wat zinvol is en wat niet.

Jawel, maar dan hoef je ze dus niet alle 10^9999 door te rekenen hé?

[Ivo]

Je moet elke zet zover doorrekenen tot het duidelijk is of de zet zinvol of niet zinvol is. Bij sommige zetten zal dat al gauw duidelijk zijn (misschien zelfs meteen na de zet), maar de meeste zullen een aantal stappen doorgerekend worden en om na een zet door te rekenen moet je weer allerlei mogelijkheden proberen. Dus als je initieel X mogelijkheden hebt, dan zul je minimaal X stappen moeten doorlopen in het beste geval. Dat beste geval zal echter bijna nooit voorkomen. Een goeie schatting van de slechtste geval looptijd is lastig, omdat het aantal mogelijkheden niet stijgend of dalend is na een verloop van zetten, maar ik denk dat je richting X^X moet denken.

[Zoijar]

RobIII schreef op zaterdag 17 september 2005 @ 00:17:
Jawel, maar dan hoef je ze dus niet alle 10^9999 door te rekenen hé?

Alle zetten is ook bv een getal als 10^130, en als je het erg slim doet kan je dat terug brengen tot iets van 10^50: een gigantisch veel kleiner getal, ondenkbaar veel kleiner. En nog is dat veel te groot...

[Verwijderd]

Wat je in het computerprogramma moet inbouwen is de wetenschap dat de andere computer precies hetzelfde algoritme gebruikt, de computer zal dan voorzien dat iedere zet die hij zet ook door de andere computer is voorzien.

Volgens mij na 1 zet remise.

[Ivo]

Tenzij de computer die de eerste zet maakt een onvermijdelijk overwinningspad weet. Elke zet in het pad brengt je in een situatie waar er voor elke zet die de tegenstander kan doen weer een zet is die jouw binnen het pad naar de overwinning houdt.

[Soultaker]

Even om te beginnen: schaakalgoritmen doen niet aan 'kansrekening', want dat is funest tegen een serieuze tegenstander. Wel zit er in veel programma's een random factor zodat zetten die ongeveer gelijkwaardig zijn allemaal gekozen kunnen worden, om te voorkomen dat de menselijke tegenstander zich gaat vervelen (altijd dezelfde opening) of het programma te voorspelbaar wordt en daardoor makkelijk te bestrijden (als de computer telkens hetzelfde zet heb je maar één partij nodig om altijd van 'm te winnen).

Verder 'leren' schaakalgoritmen over het algemeen niet zelf. De kennis die ze hebben is er door experts in gestopt en die kan weer bijgewerkt worden nadat die experts gespeerde partijen hebben geëvalueerd (desnoods softwarematig), maar het algoritme doet dat in principe niet. (Of heeft iemand bronnen dat Deep Blue dit wel doet?)

De basis van een schaakprogramma is dat alle variaties tot, zeg, 10 zetten doorgerekend worden en dat het programma dan de zet kiest waarmee hij de best mogelijke stelling kan forceren. Dat betekent dus dat als hij zet X doet omdat hij daarmee denkt een pion te winnen, dat ook gebeurt (binnen 10 zetten), of beter natuurlijk als zijn tegenstander het niet handig uitspeelt. Er zijn een heleboel variaties en verfijningen op dit basisalgoritme, maar dit is wel in de basis hoe een schaakprogramma werkt.

Winnen op 'geluk' of 'een foutje' kan dus niet van een schaakcomputer; iemand als Kasparov kan winnen van Deep Blue doordat Kasparov stellingen beter kan evalueren dan een computer en hij dus steeds de computer in een richting kan dwingen die voor de computer acceptabel lijkt, maar waarbij de computer steeds een heel klein beetje terein verliest. Uiteindelijk staat Kasparov dan iets sterker en kan 'ie winst afdwingen.

Denk er aan dat de computer ook maar beperkt is: als Kasparov in 12 zetten een pion winst kan afdwingen dan ziet de computer dat niet als 'ie maar 10 zetten diep denkt en kan dus eerst een foute zet doen, waarna hij zijn fout inziet (want die ligt dan voor de horizon van 10 zetten). De manier waarop de ene computer van de andere wint werkt op dezelfde manier: het is best mogelijk dat een bepaalde zet geen schadelijke gevolgen blijkt te hebben als de computer 10 zetten vooruit denkt, maar dan is zijn tegenstander aan de beurt en die denkt dan dus een halve zet verder (aangezien de positie een halve zet gevorderd is) en ziet de fout wél in. In de praktijk is het algoritme veel ingewikkelder en dat levert allerlei mogelijke situaties op waarin de ene speler wél een gevolg doorziet wat de ander niet gezien heeft. Twee schaakprogramma's die tegen elkaar spelen maken dus niet noodzakelijkerwijs remise, maar als ze goed genoeg zijn (nivo Deep Blue) dan denk ik dat het verschil in spelsterkte te klein is om er één te laten winnen; bij schaken is de remisemarge nog vrij groot (veel groter dan bij een spel als go maar veel kleiner dan bij een spel als dammen).

Verwijderd schreef op zaterdag 17 september 2005 @ 22:26:
Wat je in het computerprogramma moet inbouwen is de wetenschap dat de andere computer precies hetzelfde algoritme gebruikt, de computer zal dan voorzien dat iedere zet die hij zet ook door de andere computer is voorzien.

Volgens mij na 1 zet remise.

Stel dat je 5 minuten hebt om een zet te bedenken. Als je dan wil weten wat je tegenstander doet moet je eerst 5 minuten rekenen, maar dan is je tijd om, terwijl je je eigen zet nog niet bedacht hebt! Dat werkt dus niet.

Ivo schreef op zondag 18 september 2005 @ 13:43:
Tenzij de computer die de eerste zet maakt een onvermijdelijk overwinningspad weet. Elke zet in het pad brengt je in een situatie waar er voor elke zet die de tegenstander kan doen weer een zet is die jouw binnen het pad naar de overwinning houdt.

Er is een vrij sterk vermoeden dat er voor schaken niet zo'n pad bestaat, maar dat is heel lastig definitief te bewijzen door de grootte van het aantal toestanden (zoals Zoijar al aangaf).

[ Voor 14% gewijzigd door Soultaker op 18-09-2005 14:08 ]