Go zo lastig dat computers het niet kunnen spelen?

[Oscar Mopperkont]

Ik las net het volgende op wikipedia:

Go is volgens de speltheorie een nul-somspel met volledige informatie, net als schaken en dammen; het toeval speelt geen rol en als de ene speler wint moet de andere verliezen; eindigen beide met evenveel punten dan is het spel remise. In theorie zou een voldoende krachtige computer alle mogelijke partijen vooraf kunnen berekenen en zo een optimale strategie voor beide spelers kunnen vinden. Het aantal mogelijke volgordes van zetten is echter groter dan het aantal atomen in het heelal. Anders dan bij schaken is er nog geen uitzicht op een go-spelende computer die zelfs maar een goede clubspeler zou verslaan. In deze zin is het spel complexer dan schaken. Tegenwoordig kan een computer een foutloos spel spelen op een bord van 5 bij 5, maar er zal waarschijnlijk nooit een computer zijn die foutloos speelt op het volledige bord van 19 bij 19 tegen een professionele speler.

Aangezien het dusdanig complex is, doet de mens ook niet "de beste" zet, maar probeert hij die te benaderen. Wat maakt Go nu zo moeilijk dat een computer dit niet kan benaderen of evenaren? Intuïtief zou ik zeggen dat het inderdaad zo moeilijk kan zijn dat je het nooit kunt doorrekenen, dat lukt bij schaken ook nog niet, maar een computer moet toch inmiddels wel krachtig genoeg zijn om het spel goed te spelen? Computers kunnen wel meer dingen niet, die de mens wel goed kan, maar dit lijkt mij dus iets wat een computer ook goed zou moeten kunnen.

En dan ben ik nu pas zo slim om ook even de Engelse versie te lezen...

The reasons why computers are not good at playing Go are attributed to many qualities of the game,[15] including:

• Although there are usually less than 50 playable (meaning acceptable) moves (and not uncommonly even fewer than 10) the area of the board is very large (five times the size of a chess board) and the number of legal moves rarely go below 50. Throughout most of the game the number of legal moves stay at around 150-250, but computers have a hard time distinguishing between good and bad moves.
• Whereas in most games based on capture (e.g. chess, checkers) the game becomes simpler over time as pieces disappear, in Go, a new piece appears every move, and the game becomes progressively more complex, at least for the first 100 ply.
• Unlike other games, a material advantage in Go does not mean a simple way to victory, and may just mean that short-term gain has been given priority.
• The non-local nature of the ko rule has to be kept in mind in advanced play.
• There is a very high degree of pattern recognition involved in human capacity to play well.

[ Voor 28% gewijzigd door Oscar Mopperkont op 25-10-2006 16:01 ]

[Confusion]

De crux ligt bij het laatste punt, maar met een twist: mensen kunnen heel goed patronen herkennen, maar ze weten eigenlijk zelf niet welke patronen ze herkennen. Zouden ze dat weten, dan zouden ze die patronen abstract kunnen beschrijven en aan een computer kunnen 'leren', die vervolgens een speelbord sneller op diezelfde patronen kan nalopen. Een schaakcomputer kan niet schaken, maar een Go computer moet Go kunnen spelen om te winnen.

Misschien is een spel juist leuk om dezelfde reden waarom een computer het niet kan spelen?

[ Voor 9% gewijzigd door Confusion op 25-10-2006 18:30 ]

[drooger]

Misschien is het ook handig om een link of uitleg over Go erbij te doen(zodat leken, zoals ik, weten waar je het over hebt).

Je moet er wel mee rekening houden dat de software geprogrammeerd moet worden door een mens, dus er kunnen zeker fouten in zitten. Ik denk dat het dan ook in de software zit, waardoor computers niet (goed) Go kunnen spelen.

Anders zou je het ook zo kunnen programmeren, dat de computer eerst kijkt welke zetten mogelijk zijn en daar 1 van doet. In principe speelt een computer dan Go, maar als het goed is...

[edie]

Een schaakcomputer hoeft volgens mij niet eens alles door te rekenen. Hij zoekt de bordpositie op in een database en selecteert de volgende zet. Dit kan omdat schaken veel minder mogelijke bordposities kent dan Go.

Een computer moet (vooralsnog) het gehele bord af om tot een goede zet te komen. De beginnende Go speler kan al intuitief een goede zet doen.

Daarnaast speelt patroonherkenning een zeer grote rol in het spel en computers zijn daar nou eenmaal nog niet zo goed in.

Ik heb eens ergens gelezen dat de beste Go-computer even sterk is als de persoon die het programma maakt. Verder hebben zelfs professionals meegewerkt om goede computerprogramma's te maken, maar voor sommige zetten hebben ze geen logische verklaring; 'deze zet voelt goed'.

[Verwijderd]

Een schaakcomputer hoeft volgens mij niet eens alles door te rekenen. Hij zoekt de bordpositie op in een database en selecteert de volgende zet. Dit kan omdat schaken veel minder mogelijke bordposities kent dan Go.

Alleen tijdens de openingsfase van het spel, en verder in een beperkt aantal eindspelsituaties. Vroeger of later zal er toch een "unieke" positie op het bord komen (eentje die niet in een database zit) en moet er gerekend worden. De grootste verschillen tussen schaken en go is dat er in elke positie in het schaken maximaal een stuk of 30-40 legale zetten zijn, dat het in het schaken een stuk makkelijker is om een positie te beoordelen en dat vaak binnen enkele zetten een onduidelijke positie al "opgelost" is (dat wil zeggen, dat wel duidelijk is wie er beter staat). Daardoor valt schaken op een brute-force manier door te rekenen. De kwaliteitsverschillen tussen schaakcomputers komen voort uit verschillen tussen de algorithmes die zo snel mogelijk besluiten of een variant nog verder doorgerekend moet worden.

Bij go is elke brute-force analyse hopeloos.

[ Voor 10% gewijzigd door Verwijderd op 25-10-2006 18:54 ]

[Jazzper]

Ik meen gehoord te hebben van een Go clubspeler dat zelfs de beste Go algoritmes nog een novice level hebben en na paar keer Go gespeeld te hebben als mens te verslaan zijn.

van wiki

In theorie zou een voldoende krachtige computer alle mogelijke partijen vooraf kunnen berekenen en zo een optimale strategie voor beide spelers kunnen vinden. Het aantal mogelijke volgordes van zetten is echter groter dan het aantal atomen in het heelal. Anders dan bij schaken is er nog geen uitzicht op een go-spelende computer die zelfs maar een goede clubspeler zou verslaan. In deze zin is het spel complexer dan schaken. Tegenwoordig kan een computer een foutloos spel spelen op een bord van 5 bij 5, maar er zal waarschijnlijk nooit een computer zijn die foutloos speelt op het volledige bord van 19 bij 19 tegen een professionele speler.

[MSalters]

Tja - een uitspraak als "er zal waarschijnlijk nooit een computer zijn die foutloos speelt" is net zo onderbouwd als "640K should be enough for everyone" of "5 computers zijn genoeg voor de hele wereld". Dat de auteur geen speltheoreticus is, is ook wel duidelijk: "er zal nooit een computer zijn die foutloos speelt tegen een professionele speler." Computers zijn niet onder de indruk van hun tegenstander; ze gaan niet opeens fouten maken doordat hun tegenstander wereldkampioen is.

[edie]

Volgens mij is het onmogelijk om Go foutloos te spelen. Simpelweg omdat er meerdere 'goede' zetten mogelijk zijn, en de reactie van je tegenstander kan je 'goede' zet omzetten naar een 'slechte' zet.

[edie]

drooger schreef op woensdag 25 oktober 2006 @ 18:12:
Misschien is het ook handig om een link of uitleg over Go erbij te doen(zodat leken, zoals ik, weten waar je het over hebt).

Je moet er wel mee rekening houden dat de software geprogrammeerd moet worden door een mens, dus er kunnen zeker fouten in zitten. Ik denk dat het dan ook in de software zit, waardoor computers niet (goed) Go kunnen spelen.

Anders zou je het ook zo kunnen programmeren, dat de computer eerst kijkt welke zetten mogelijk zijn en daar 1 van doet. In principe speelt een computer dan Go, maar als het goed is...

[Bordspel] Go / I-Go / Wei-Chi / Baduk

[kunnen]

edie schreef op woensdag 25 oktober 2006 @ 21:13:
Volgens mij is het onmogelijk om Go foutloos te spelen. Simpelweg omdat er meerdere 'goede' zetten mogelijk zijn, en de reactie van je tegenstander kan je 'goede' zet omzetten naar een 'slechte' zet.

Lees eens iets over speltheorie. Het idee van een goede zet is juist dat deze niet in een slechte zet omgezet kan worden. Als zulke (goede) zetten niet mogelijk zijn staat die speler dus op dat moment op verliezen, en wanneer de andere speler dan perfect speelt zal die winnen.

[Rey Nemaattori]

Confusion schreef op woensdag 25 oktober 2006 @ 18:10:
De crux ligt bij het laatste punt, maar met een twist: mensen kunnen heel goed patronen herkennen, maar ze weten eigenlijk zelf niet welke patronen ze herkennen. Zouden ze dat weten, dan zouden ze die patronen abstract kunnen beschrijven en aan een computer kunnen 'leren', die vervolgens een speelbord sneller op diezelfde patronen kan nalopen. Een schaakcomputer kan niet schaken, maar een Go computer moet Go kunnen spelen om te winnen.

Misschien is een spel juist leuk om dezelfde reden waarom een computer het niet kan spelen?

Daar zouden neurale netwerken een uitkomst kunnen bieden, gegeven genoeg training.
Ik denk dat het ook een stuk samenspel is. Doordat wij patronen herkennen, hoeven we niet alle mogelijke zetten te analyseren/overwegen, we hebben er varing, we kunnen generaliseren(een strategie bedenken en uitvoeren met een bepaalde foutmarge, ipv een enkele tactische zet helemaal doorberekenen)

Jazzper schreef op woensdag 25 oktober 2006 @ 18:52:
Ik meen gehoord te hebben van een Go clubspeler dat zelfs de beste Go algoritmes nog een novice level hebben en na paar keer Go gespeeld te hebben als mens te verslaan zijn.

van wiki

[...]

Aan de andere kant zijn er ook geen professionele spelers die foutloos spelen...naja hoogstens 1

Deep blue was ook niet foutloos, alleenwas de marge kleiner dan die van de regerend wereldkampioen, wat resulteerde in een overwinning.

[ Voor 5% gewijzigd door Rey Nemaattori op 25-10-2006 22:50 ]

[argro]

Verwijderd schreef op woensdag 25 oktober 2006 @ 18:50:
[...]


Alleen tijdens de openingsfase van het spel, en verder in een beperkt aantal eindspelsituaties. Vroeger of later zal er toch een "unieke" positie op het bord komen (eentje die niet in een database zit) en moet er gerekend worden. De grootste verschillen tussen schaken en go is dat er in elke positie in het schaken maximaal een stuk of 30-40 legale zetten zijn, dat het in het schaken een stuk makkelijker is om een positie te beoordelen en dat vaak binnen enkele zetten een onduidelijke positie al "opgelost" is (dat wil zeggen, dat wel duidelijk is wie er beter staat). Daardoor valt schaken op een brute-force manier door te rekenen. De kwaliteitsverschillen tussen schaakcomputers komen voort uit verschillen tussen de algorithmes die zo snel mogelijk besluiten of een variant nog verder doorgerekend moet worden.

Bij go is elke brute-force analyse hopeloos.

Het aantal mogelijke zetten bij schaken is veel groter dan 40 in een random stelling. Met een brute-force analyse kom je bij schaken ook niet heel ver. Mensen elimineren kansloze zetten veel sneller terwijl menig computer toch nog veel rekencapaciteit aan een dergelijke set besteed. Een goede schaakcomputer is een combinatie van databases (zoals eerder gezegd) en slimme algoritmes zodat de computer niet in tijdnood komt door gereken aan hopeloze zetten.

[Rey Nemaattori]

Maar dat geld voor een mens ook. Wij elimineren ook zetten omdat sommige zetten in het verleden tot verlies/verliezen(qua stukken, zonder de partij te verliezen) hebben geleid.

[Verwijderd]

Haha, dit heb ik vroeger eens op school gehad. En voorlopig nog lang niet door computers op te lossen.
Bij bijvoorbeeld schaken/dammen heb je gewoon enorm veel mogelijkheden.
Bijvoorbeeld: je kan 6 keuzes maken per beurt, als iets 3 beurten duurt zijn er dus 216 mogelijkheden
Dit gaat HEEL snel omhoog, en kan een computer niet aan!
6^3=216
6^6=46656
6^9=10077696
6^12=2176782336
6^15=470184984576
Elk probleem met exponentieel mogelijkheden eigenlijk niet te doen via brute force

[Oscar Mopperkont]

Verwijderd schreef op donderdag 26 oktober 2006 @ 16:57:
Haha, dit heb ik vroeger eens op school gehad. En voorlopig nog lang niet door computers op te lossen.
Bij bijvoorbeeld schaken/dammen heb je gewoon enorm veel mogelijkheden.
Bijvoorbeeld: je kan 6 keuzes maken per beurt, als iets 3 beurten duurt zijn er dus 216 mogelijkheden
Dit gaat HEEL snel omhoog, en kan een computer niet aan!
6^3=216
6^6=46656
6^9=10077696
6^12=2176782336
6^15=470184984576
Elk probleem met exponentieel mogelijkheden eigenlijk niet te doen via brute force

Je hoeft natuurlijk niet brute force alle mogelijkheden af te gaan, dat doet een schaakcomputer ook niet. Die heeft ook wel een systeem dat ie minder interessante paden laat vallen. Bovendien kan de mens het op de één of andere manier wel goed spelen en die heeft al helemaal geen brute force in zich, dus die doet het op patroonherkenning en op basis van andere algoritmen. Dat is moeilijker te programmeren, maar de computer heeft weer het voordeel dat ie sneller kan rekenen dan de mens.

Maar kennelijk is bij Go patroonherkenning voorlopig de enige methode op basis waarvan je het spel nog goed kunt spelen en de computer kan daar dus nog niet goed in getraind worden. Toch wel geinig om te zien dan dat een mens hier beter in is, terwijl ik toch wel had verwacht dat een computer dit ook wel aardig zou moeten kunnen.

[soulrider]

effe gezocht op 't net:

schijnbaar zijn er toch al verschillende programma's waarbij de pc toch zelfstandig al 19x19 velden speelt:

http://www.reiss.demon.co.uk/webgo/compgo.htm

zoektermen:
computer go
in google helpt al veel

en hier vind je enkele programma's die het wel kunnen (bij naam - een zoekmachine bezorgt je wrs wel de site ervan)

http://www.cs.unimaas.nl/olympiad2006/

bv: gnugo, go++, crazy stone, go intellect, goking, neurogo, ...

maw: ze staan er toch al verder mee dat dat je wiki-tekst wilt zeggen

[ Voor 14% gewijzigd door soulrider op 27-10-2006 09:03 ]

[Oscar Mopperkont]

Maar dat zegt natuurlijk nog niks over het niveau van die programma's

Het gaat er om dat een beetje geoefende speler op een 19x19 bord (nog) niet te verslaan is door een computer.

[drooger]

Maar dat zegt natuurlijk nog niks over het niveau van die programma's

Het gaat er om dat een beetje geoefende speler op een 19x19 bord (nog) niet te verslaan is door een computer.

Er is ook geen vereiste voor het niveau, bij dit topic Er wordt namelijk gevraagd als computers het kunnen spelen, het antwoord daarop is: ja. De vraag als computers het goed kunnen spelen, is iets heel anders

[Verwijderd]

De meeste computer-algoritmes maken gebruik van gewoon alle mogelijke combinaties te gaan bekijken en dan er de beste gaan uitnemen.

Een mens kan niet alle combinaties vooraf bedenken dus gaat hij anders gaan denken, op een meer effectieve manier want met veel minder hersenkracht kan hij al meer dan een PC.

PC's zijn al altijd slecht geweest met patronen en zullen het ook nog een tijdje zo blijven. Ik heb nog stage gedaan op een Onderzoeksafdeling waarbij men bezig was met gezichtsherkenning. Dit heeft ook veel te maken met patronen. De basis die ze gebruikten was een algoritme dat gebaseerd was op jarenlang onderzoek over hoe mensen gezichten gaan analyseren en verwerken in de hersenen. Dit omdat men er van uitgaat dat een mens nog altjid de beste is in het herkennen van een andere mens, dus zal het algoritme dat onze hersenen gebruiken wel een zeer sterk zijn daarin. (ter info, dit ding noemt de Gabor-decompositie). De software die ze hadden was vrij goed, maar de foutenmarge was nog boven de 5% voor Aziaten (tja, 't was een Japans bedrijf), 10% voor Europese type en meer dan 20% voor het Afrikaanse type (andere rassen werden nog niet ondersteund), dus totaal niet bruikbaar voor enige veiligheidstoepassing.

Eén van de redenen waarom PC's ook zo slecht zijn is door hun manier van opbouw. De volledige PC-structuur bestaat zoals gekend uit nullen en enen die afkomstig zijn van een hoog en een laag signaal aan de uitgang van een schakeling die bestaan uit transistoren. Je zou vrij strikt kunnen zeggen dan een computer enkel bestaat uit vele kleine cellen met twee ingangen, als beide ingangen gelijk zijn dan komt er hetzelfde uit, wanneer ze verschillend zijn komt er altijd een nul uit. Nu is het door jarenlang onderzoek en het genie van de mensheid dat men er in geslaagd is al tot wonderbaarlijke rekenkracht te komen door de juiste combinatie van deze domme eenheden.

Maar wederom zijn onze hersenen hier veel beter af. Wij bestaan uit neuronen ipv uit transistoren en dan beschikken we nog eens over de kracht om nieuwe verbindingen te kunnen leggen tussen onze neuronen. Als het ware een computer die zelf zijn transistoren gaat herschikken om beter te worden in sommige dingen. Verder kan een neuron meer dan van 2 ingangen een uitgang produceren.

Waar een PC dan wel weer beter is, is in opslag, maar op zich kan je dan zelfs zeggen dat een blad papier slimmer is dan de mens want eens je iets print staat het over 10 jaar nog op de blad terwijl jij al lang zal vergeten zijn wat je toen gelezen hebt :-)
En puur rekenen met getalletjes, daar is de PC uiteraard ook supersnel, zolang er maar ooit iemand geweest is die lang heeft nagedacht hoe alle transistortjes met elkaar moeten verbonden worden en de software geprogrammeerd om dit te kunnen.

[Verwijderd]

Op zich een interessant feit over Go in deze context:

Met de juiste regels (bijvoorbeeld super Ko en de juiste Komi) is gelijk spel uitgesloten en heeft het spel altijd een eindig aantal zetten. Een vrij eenvoudig resultaat in speltheorie dat dergelijk spel een winnende strategie heeft.

Een van de spellers kan dus altijd winnen. Naief gezien is dan ook de verwachting dat uitenidelijk een computer in het voordeel zou moeten zijn in dergelijk spel, aangezien je zou verwachten dat een computer die strategie zou moeten kunnen brute forcen. (Dat wil zeggen dit is voor een computer aanzienlijk makkelijker dan voor een mens, maar met het enorme aantal spel mogelijkheden van Go, met de huidige technologie nagenoeg even onmogelijk.

Echter voor Go op kleinen borden is het in principe mogelijk om een Go algoritme te hebben dat onverslaanbaar is als deze met de juiste kleur begint. (Ik geloof dat dit momenteel voor 5x5 Go gelukt is.)

[bangkirai]

Je moet dammen er niet bij halen, dat hoort eigenlijk niet meer in het rijtje thuis.

Dammen heeft beperkte mogelijkheden en er zijn al best veel top dammers overgeschakeld op go of schaken. Is blijkbaar niet zo uitdagend meer.

[Dido]

bangkirai schreef op maandag 30 oktober 2006 @ 22:00:
Je moet dammen er niet bij halen, dat hoort eigenlijk niet meer in het rijtje thuis.

Dammen heeft beperkte mogelijkheden en er zijn al best veel top dammers overgeschakeld op go of schaken. Is blijkbaar niet zo uitdagend meer.

Schaken en go hebben ook beperkte mogelijkheden, net zoals boter-kaas-en-eieren. In principe verschillen de spellen niet zoveel van elkaar vanuit speltheoretisch oogpunt.
Dammen wordt welliswaar maar op 50 velden gespeeld, maar heeft nog altijd enorm veel meer mogelijke situaties dan boter-kaas-en-eieren.

Het hoort m.i. wel degelijk in het rijtje thuis. Interessant is juist om te bekijken waarom sommige spellen in het rijtje wel door computers (brute-force of met een database-benadering) goed te spelen of zelfs op te lossen zijn, en welke niet.

[Verwijderd]

Confusion schreef op woensdag 25 oktober 2006 @ 18:10:
De crux ligt bij het laatste punt, maar met een twist: mensen kunnen heel goed patronen herkennen, maar ze weten eigenlijk zelf niet welke patronen ze herkennen.

Dit is denk ik de meest interessante opmerking uit dit topic. Uit hersenonderzoek blijkt dat professionele schakers veel minder hersenactiviteit vertonen bij het schaken dan onervaren mensen die "luk raak een beetje aan het proberen zijn". Voor muziek spelen geldt hetzelfde. Het blijkt ook dat ervaren schakers bepaalde slechte zetten gewoon "niet zien". Niet bewust in ieder geval. Ze kijken direct naar de patronen die ze herkennen en denken dan ook aan patronen die daar op lijken. Vooral dit "erop lijken" kan vaak tot interessante gedachten leiden die moeilijk te programmeren zijn. Als ik een boom zie, denk ik aan een boomdiagram eigenlijk ook meteen een beetje aan kansrekening. Die link is voor mij heel vanzelfsprekend, maar leer een computer dit maar eens...

Hersenen maken heel handig gebruik van "vaag nadenken" bij het analyseren van grote algemene structuren. Computers zitten veel meer vast aan rigide algoritmes waar niet vanaf geweken wordt.

[Soultaker]

Dido schreef op dinsdag 31 oktober 2006 @ 07:06:
Schaken en go hebben ook beperkte mogelijkheden, net zoals boter-kaas-en-eieren. In principe verschillen de spellen niet zoveel van elkaar vanuit speltheoretisch oogpunt.

Precies. Het antwoord op de vraag in de topic start is dus ook: er is geen fundamentele reden waarom een computer geen go kan spelen, maar daarvoor is (1) heel veel meer rekenkracht nodig en (2) veel betere evaluatiefuncties dan nu bedacht zijn.

Het evalueren van een schaakstelling is relatief 'makkelijk' omdat materiaal heel zwaar meetelt. Als je met schaken een paard achter staat en je kunt die niet binnenkort terugveroveren (of de tegenstander matzetten) dan kun je wel opgeven. Bij go is dat veel minder duidelijk, want het gaat niet om hoeveel stenen je op het bord hebt, maar om wáár ze precies staan.

(Maar echt goede schaakprogramma's zoals Deep Blue dan wel heel wat meer dan materiaal tellen alleen.)

Dammen wordt welliswaar maar op 50 velden gespeeld, maar heeft nog altijd enorm veel meer mogelijke situaties dan boter-kaas-en-eieren.

Interessanter dan het aantal stellingen is het aantal mogelijkheden per stelling (branching factor), omdat dat bepaalt in hoeveel verschillende situaties je na, zeg, zes kunt zijn.

Zowel qua branching factor als aantal stellingen geldt: boter-kaas-en-eieren << dammen << schaken << go.

Overigens heb je (vooral) bij dammen en (in mindere mate) schaken veel repeterende stellingen en in go bijna geen (normaal gesproken plaats je om de beurt een steen op het bord; je kunt wel herhaling krijgen wanneer stenen geslagen wordt maar er worden niet zo vaak stenen geslagen behalve in ko-gevechten, en dan is er een ko-regel die herhaling verbiedt). Dat scheelt ook weer een stuk.

Het is trouwens wel interessant om te bedenken dat er twintig jaar geleden best redelijke schaakprogramma's waren, maar dat schaakmeesters dachten dat ze nog altijd eenvoudig konden verslaan. Toen waren er vast ook mensen die dachten dat de computer nooit van de mens zou winnen. Het is dus niet onwaarschijnlijk dat go-programma's ook geleidelijk opklimmen tot het nivo van menselijke spelers.

[ Voor 13% gewijzigd door Soultaker op 31-10-2006 17:09 ]

[boner]

Kan iemand mij uitleggen op hoeveel manieren je twee kleuren steentjes op 19 * 19 punten kunt leggen?

Dat kan toch nooit zoveel zijn als er atomen in het heelal zijn?

[MSalters]

boner schreef op woensdag 01 november 2006 @ 20:10:
Kan iemand mij uitleggen op hoeveel manieren je twee kleuren steentjes op 19 * 19 punten kunt leggen?

Dat kan toch nooit zoveel zijn als er atomen in het heelal zijn?

10⁸⁰ atomen in het heelal, grofweg.

[Mithrandir]

boner schreef op woensdag 01 november 2006 @ 20:10:
Kan iemand mij uitleggen op hoeveel manieren je twee kleuren steentjes op 19 * 19 punten kunt leggen?

Dat kan toch nooit zoveel zijn als er atomen in het heelal zijn?

Dat is meer dan 2^(19*19), wat 4,7 * 10¹⁰⁹ is. Dat is dus best veel

er zijn er nog meer (dit is het geval wanneer je op een plek óf een steen hebt, óf niet. Je kunt natuurlijk óf een zwarte, óf een witte, óf geen steen hebben. Maar ook ewer niet meer dan de helft zwarte en de helft witte stenen, en hoe dat uitgerekend moet worden weet ik niet precies)

[ Voor 30% gewijzigd door Mithrandir op 01-11-2006 20:33 ]

[edie]

boner schreef op woensdag 01 november 2006 @ 20:10:
Kan iemand mij uitleggen op hoeveel manieren je twee kleuren steentjes op 19 * 19 punten kunt leggen?

Dat kan toch nooit zoveel zijn als er atomen in het heelal zijn?

Het is eigenlijk vrij simpel:

voor de 1e zet zijn er 19*19 legale mogelijkheden
voor de 2e zet zijn er 19*19 - 1 legale mogelijkheden
voor de 3e zet zijn er 19*19 - 2 legale mogelijkheden
voor de 4e zet zijn er 19*19 - 3 legale mogelijkheden
etc.

Standaard berekening levert: (19*19) * (19*19 - 1) * (19*19 - 2) * (19*19 - 3) * (19*19 - 4) * ....
En dat zijn heeel veel mogelijkheden.

Van http://senseis.xmp.net/?ComplexityOfGo:

It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end result of about (120!)^2 = 4.5×10^397 different (no-capture) games, for a total of about 9.3×10^567 games. Allowing captures gives as many as 10^(7.49×10^48) possible games, most of which last for over 1.6×10^49 moves! (By contrast, the number of legal positions in chess is estimated to be between 10^43 and 10^50, and physicists estimate that there are not more than 10^90 protons in the entire universe.)

[Verwijderd]

Interessant is juist om te bekijken waarom sommige spellen in het rijtje wel door computers (brute-force of met een database-benadering) goed te spelen of zelfs op te lossen zijn, en welke niet.

Door de vorige posters is je antwoord gegeven: door het ongelooflijk grote aantal mogelijke spelverlopen heb je voor een effectieve Brute Force benadering van Go een rekenkracht nodig die voorlopig op geen enkele manier te realiseren valt.

[Dido]

Verwijderd schreef op woensdag 01 november 2006 @ 21:19:
Door de vorige posters is je antwoord gegeven: door het ongelooflijk grote aantal mogelijke spelverlopen heb je voor een effectieve Brute Force benadering van Go een rekenkracht nodig die voorlopig op geen enkele manier te realiseren valt.

offtopic:
Weet ik, maar wat jij hier quote was een reactie op een gevoelsmatige uitsluiting van sommige spellen uit de discussie. Ik gaf alleen maar aan dat dat uitsluiten niet interessant was, omdat je dan niet tot de door jou aangehaalde conclusie komt; die is immers het resultaat van vergelijking tussen verschillende gelijkaardige spellen als dammen, schaken en go.

[Verwijderd]

De oplossing van uw problemen liggen verscholen in de complexiteitstheorie.

Uw hulpmiddel is de theoretisch turing-machine.

Wat deze machine theoretisch kan oplossen zou een PC ooit met voldoende rekenkracht moeten kunnen. Wat deze machine niet kan oplossen zal een PC ook nooit kunnen.

Voor deze machine zijn er verschillende verzameling van problemen.
Een eerste zijn de P-problemen die makkelijk oplosbaar zijn in een korte tijd.
Dan heb je de NP-problemen waarvan niet-deterministisch te bepalen is of ze in een polynomiale tijd kunnen opgelost worden (wrede miserie dus, want je weet niet of een PC ooit het probleem zal kunnen oplossen of niet)
Een NP-compleet probleem dan is zeker niet op te lossen in een polynomiale tijd (dwz, niet binnen een eindige tijd met gelijk welke machine)
Een overigens wel leuke eigenschap van een gewoon NP-probleem is wel dat, als we een oplossing voorstellen, we deze binnen een polynomiale (dus eindige) tijd kunnen verifiëren.
Een nog groter geluk is dat er ooit twee slimme wiskundigen in de jaren 70 hebben kunnen bewijzen dat elk NP probleem om te vormen is tot een NPcompleet probleem binnen een polynomiale tijd.

Dan kunnen we bv. komen tot het schaken, maar vooralsnog is dacht ik niet bewezen dat de beste keuze voor de volgende zet binnen de NPcomplete problemen valt. Wat er dus op wijst dat schaken nog "moeilijker" is dan het oplossen van een NPcompleet probleem. Wat dus wil zeggen dat (als er kan bewezen worden dat schaken geen NP(compleet) probleem is) het niet binnen een eindige tijd te berekenen valt of een voorstel voor een volgende zet binnen dit spel de best mogelijk is. Wat er dus op neer komt dat een PC nooit onfeilbaar kan gemaakt worden binnen het schaakspel.
Er zijn dacht ik probeersels voor bewijzen die starten met : 2 Turing machines beschikken over een algoritme die binnen een eindige tijd een voorstel van het (?)NP probleem volgende stap in het schaken beide kunnen perfect kunnen berekenen of het de best mogelijke volgende stap is. In dit geval zou elk schaakspel tussen deze beide computers in een remise moeten eindigen.

Verder mijn verontschuldigingen voor eventuele fouten, maar het is al een paar jaartjes geleden dat ik die cursus over compexiteitstheorie nog geblokt heb.

Verder kan je op het net en op wikipedia de nodige info vinden

[Verwijderd]

Verwijderd schreef op donderdag 02 november 2006 @ 19:08:
De oplossing van uw problemen liggen verscholen in de complexiteitstheorie.

Uw hulpmiddel is de theoretisch turing-machine.

Wat deze machine theoretisch kan oplossen zou een PC ooit met voldoende rekenkracht moeten kunnen. Wat deze machine niet kan oplossen zal een PC ook nooit kunnen.

[...]

Gezien mijn eerdere opmerkingen, is het duidelijk dat een computer met voldoende rekenkracht/geheugen het spel Go (met de juiste variant regels) perfect zou moeten kunnen spelen. (In ider geval voor een van de twee partijen.) Echter, zoals anderen hier keurig voorrekenen, lijkt het erop dat de grote en de leeftijd van het heelal een beprekende factor vormen voor het bouwen van dergelijke computer.

[Soultaker]

Het probleem is niet alleen rekenkracht hoor. De reden dat schaakcomputers grootmeesters kunnnen verslaan zit niet primair in de rekenkracht (al helpt het wel veel), maar ook in goede evaluatiefuncties. De overwinning van Deep Blue is al tien jaar geleden. Tegenwoordig heb je ChessBrain waarmee honderden processoren van een hele nieuwe generatie ingezet kunnen worden, maar toch speelt ChessBrain aanmerkelijk zwakker.

Het is zo dat je met oneindige rekencapaciteit eenvoudig een perfect spelend programma kan bouwen, maar dat betekent niet per se dat het met beperkte capaciteit fundamenteel onmogelijk is om een sterk programma schrijven. Het komt er maar op aan dat iemand datgene wat menselijke spelers 'goed' maakt weet te vertalen in een algoritme. Dat is tot nu toe niemand gelukt.

[Verwijderd]

Soultaker schreef op donderdag 02 november 2006 @ 20:12:
Het probleem is niet alleen rekenkracht hoor. De reden dat schaakcomputers grootmeesters kunnnen verslaan zit niet primair in de rekenkracht (al helpt het wel veel), maar ook in goede evaluatiefuncties. De overwinning van Deep Blue is al tien jaar geleden. Tegenwoordig heb je ChessBrain waarmee honderden processoren van een hele nieuwe generatie ingezet kunnen worden, maar toch speelt ChessBrain aanmerkelijk zwakker.

Het is zo dat je met oneindige rekencapaciteit eenvoudig een perfect spelend programma kan bouwen, maar dat betekent niet per se dat het met beperkte capaciteit fundamenteel onmogelijk is om een sterk programma schrijven. Het komt er maar op aan dat iemand datgene wat menselijke spelers 'goed' maakt weet te vertalen in een algoritme. Dat is tot nu toe niemand gelukt.

Klopt, dat claimde ik ook niet. Ik betwijfelde alleen het nut van het probleem met behulp van theoretische turing machines te analyseren, aangezien dat je alleen maar gaat vertellen, dat een computer in principe perfect Go zou moeten kunnen spelen. Maar aangezien de voor de hand liggende methode nagenoeg pratisch uitgesloten is zegt deze niks over of je een efficienter algoritme zou kunnen verzinnen, zodat een computer redelijk Go zou kunnen spelen. (Zoals, bij schaken bijvoorbeeld wel het geval is, aangezien je daar redelijke algoritmes kunt verzinnen om te bepalen wat een 'goede' zet is.)

[MicroWhale]

Ik vind het jammer dat er zoveel richting brute-force en rekenkracht gedacht wordt.

Wij zijn ook geen rekenmachines, gebruiken geen brute-force, hebben een ongelofelijk laag aantal Mhz, maar kunnen toch goed Go spelen.

Waar ligt dat aan?

Als je het antwoord kunt programmeren, waarvan ik zeker denk dat dat mogelijk is met de huidige stand van techniek, dan heb je je Go computer speler. Die moet waarschijnlijk wel eerst leren wat goed en fout is, maar deze zal uiteindelijk beter zijn dan een menselijke Go-er. Hetzelfde geldt voor schaken overigens.

[Verwijderd]

Van de discussies hierboven krijg ik de indruk dat men het er min of meer over eens is dat Go-spelers een "algoritmische" methode gebruiken dat geheel anders is dan wat nodig is voor schaken en dat voor schaken computer programateurs al weten hoe je "master kwaliteit" schaken op een computer kan programmeren. . .Gary Gasparov speelde tenslotte minder goed dan Deep Blue, en voor zover ik weet kan je op dat vlak de computer nog zeer veel beter laten spelen. . .als je het zou willen. Het argument van Gaparov dat Deep Bue niet kon schaken is natuurlijk niet terecht: hij verloor, en dus kon Deep Blue beter schaken. Punt uit.

Stel nu dat Go-spelers geen algoritmishe aanpak hebben(of veel minder dan schakers doen. . . hoe komt het eienlijk dat we Go-spelers niet Goers noemen?. . . maar dat het spel zelf zo veel mogelijkheden biedt (vanwege de eenvoud) om aan de hand van hoe de tegenstander speelt zijn taktiek te veranderen zonder dat hij zelf van te voren deze taktiek al voorbereid heeft.

Bekijk het een beetje als het proces van "iemand ontwijken" als je toevallig zou gaan botsen op het pad in een winkel: de taktiek is simpel omdat je gewoon opzij moet stappen. Het proces is identiek ongeacht hoe je loopt maar er zijn allerleij manieren om te lopen(hard lopen, slenteren, zigzagloop, dronkemansloop, etc etc. Al je een dronkeman tegen komt is het gemakkelijk hem te ontwijken maar als je allebei hard loopt is het ontwijken alleen gemakkelijk als je snel kunt reageren. Soms gebeurt het dat je allebei drie of vier keer tegelijkertijd naar dezegde kant stapt (en dat kan ook snel gebeuren) en dan realiseren beide mensen zich dat het niet lukt en staan even stil om te bababelen: "Zullen we door gaan met deze dans of zullen we afspreken dat jij naar links gaat en ik ook? Dan botsen we niet en kunnen we verder gaan met boodschappen doen?" en zo onstaat een oplossing voor het heen en weer stappen.

Ik denk dat met Go dit het probleem is om een computer te programmeren: het is niet alleen zo dat men niet weet welk algorithme mensen gebruiken, het is denk ik veel meer een zaak van dat mensen zelf geen algorithme gebruiken en als een tegenstander iets doet dat niet voorzien is dat er dan iets bedacht wordt op het probleem op te lossen. . .dus geen complexe vooruitziende blik en geen plan maar meer roeien met de riemen die je hebt en maar kijken welke kant er een opening is om weg te kunnen roeien zonder dat de roeispanen elkaar al te veel in de weg zitten. Er varing help dan niet zoveel als je plotseling een kind in roeiboot tegen komt die iets doet dat je niet verwacht.

Zoiets is niet gemakkelijk te programmeren maar als je op deze manier gaat denken als je een programma gaat schrijven dan is er misschien een manier om een computer een expert Goer te slim af te zijn. . .af en toe. . .en zou het winnen een kansspel worden: wie kan het beste de kansen berekenen dat een bepaalde zet van de tegenstander een grote of kleine kans van slagen heeft?

[MicroWhale]

wat mensen heel goed kunnen en computers niet, is deductive reasoning.

Men ziet een aantal complexe situaties (bijvoorbeeld een go-partij) en formuleert hieruit een "regel": Als deze situatie voorkomt, dan doe ik dit.

Dit systeem wordt in de hersenen constant uitgebreid en aangepast (op elkaar gestapeld. hogere vaste regels: doe nooit dit of dat. kleinere tactische regels, als hij dit dan ik dat. etc...) totdat een patroon ontstaat dat "werkt". Om dit een computer te laten doen heb je heel wat andere software nodig dan iets wat ff brute-force uit kan rekenen wat de beste oplossing is.

[ Voor 12% gewijzigd door MicroWhale op 03-11-2006 13:37 ]

[Confusion]

MrWilliams schreef op vrijdag 03 november 2006 @ 13:36:
wat mensen heel goed kunnen en computers niet, is deductive reasoning.

Men ziet een aantal complexe situaties (bijvoorbeeld een go-partij) en formuleert hieruit een "regel": Als deze situatie voorkomt, dan doe ik dit.

Dit systeem wordt in de hersenen constant uitgebreid en aangepast (op elkaar gestapeld. hogere vaste regels: doe nooit dit of dat. kleinere tactische regels, als hij dit dan ik dat. etc...) totdat een patroon ontstaat dat "werkt".

Alleen weten we zelf niet welke regels we formuleren en kunnen we het werkende patroon niet beschrijven. Konden we dat wel, dan konden we een computer datzelfde patroon laten toepassen.

Verwijderd schreef op dinsdag 31 oktober 2006 @ 15:00:
Hersenen maken heel handig gebruik van "vaag nadenken" bij het analyseren van grote algemene structuren. Computers zitten veel meer vast aan rigide algoritmes waar niet vanaf geweken wordt.

Ik vraag me af of het wel zo 'vaag' is. Mijn hypothese/fantasie is dat de hersenen zichzelf middels rewiring en selectie op de functionaliteit van de nieuw ontstane wiring telkens verbeteren. Ik zie geen reden waarom de wiring niet in een computeralgoritme, zonder intrinsieke randomness, omzet zou zijn: de wiring representeert dan een complex algoritme; complex in de zin dat het op grond van zeer kleine verschillen branched en ontzettend veel takken kent, die bovendien weer samen kunnen komen. De hersenen zijn fysiek een übercomplex netwerk, maar kan daardoor ook een stuk van zichzelf als een übercomplex algoritme laten functioneren.

[edie]

MrWilliams schreef op vrijdag 03 november 2006 @ 13:36:
wat mensen heel goed kunnen en computers niet, is deductive reasoning.

Men ziet een aantal complexe situaties (bijvoorbeeld een go-partij) en formuleert hieruit een "regel": Als deze situatie voorkomt, dan doe ik dit.

Dit systeem wordt in de hersenen constant uitgebreid en aangepast (op elkaar gestapeld. hogere vaste regels: doe nooit dit of dat. kleinere tactische regels, als hij dit dan ik dat. etc...) totdat een patroon ontstaat dat "werkt". Om dit een computer te laten doen heb je heel wat andere software nodig dan iets wat ff brute-force uit kan rekenen wat de beste oplossing is.

Nog een probleem van Go is dat er niet één complexe situatie is, maar meerdere verspreidt over het bord.

Zo heb je altijd het globale gevecht (wie heeft op het eind het meeste territorium) maar ook lokale gevechten (welke groep gaat dood, etc). Een sterke lokale zet kan desastreus zijn voor het globale resultaat. En zoiets heet 'inzicht', iets wat je een computer nog niet kan geven.

[Verwijderd]

Verwijderd schreef op dinsdag 31 oktober 2006 @ 15:00:
Als ik een boom zie, denk ik aan een boomdiagram eigenlijk ook meteen een beetje aan kansrekening. Die link is voor mij heel vanzelfsprekend, maar leer een computer dit maar eens...

Je bedoelt te zeggen dat het voor een computer moeilijk, zoniet onmogelijk is om bepaalde verbanden te associëren die niet in een wiskundig model te vangen zijn?

[Verwijderd]

Nog een interessante wikipedia-link :
http://en.wikipedia.org/wiki/Game_complexity

Go is blijkbaar een stuk moeilijker dan schaken (toch zeker voor een PC)

Verder kan Go ook niet opgelost worden in een polynomiale tijd wat er op wijst dat brute forcen hopeloos is om hier tot een oplossing te komen.

Edoch, het blijft een deterministisch probleem wat wil zeggen dat een puur deterministische machine als een PC tot een oplossing kan komen als de enige beperking de oneindigheid is.
Wat dus ook al door vele mensen hier beschreven is.

[ Voor 59% gewijzigd door Verwijderd op 04-11-2006 11:30 ]

[frickY]

Dit zou toch prima te doen moeten zijn met neurale netwerken?
In je applicatie leg je alleen de spelregels vast, en je neurale netwerk laat je hiermee aanklooien tot het zichzelf voldoende heeft geleerd om slimme zetten te maken?

Bij een brute-force hoef je natuurlijk ook niet alle mogelijkheden af te gaan. Je zou eerst brute-force kunnen bepalen welke zetten er uberhaipt mogelijk zijn, en van bijv de helft hiervan bruteforce bepalen welke zet mgoelijk de beste is. Of wordt het dan te twijfelachtig of je een ware Go-master hebt die altijd wint?

[ Voor 41% gewijzigd door frickY op 04-11-2006 12:15 ]

[Oscar Mopperkont]

frickY schreef op zaterdag 04 november 2006 @ 12:13:
Dit zou toch prima te doen moeten zijn met neurale netwerken?

Neurale netwerken zal wellicht het uitgangspunt moeten zijn, maar je zet niet zomaar even een neuraal netwerk in elkaar dat Go kan spelen.

[Opi]

frickY schreef op zaterdag 04 november 2006 @ 12:13:
Dit zou toch prima te doen moeten zijn met neurale netwerken?
In je applicatie leg je alleen de spelregels vast, en je neurale netwerk laat je hiermee aanklooien tot het zichzelf voldoende heeft geleerd om slimme zetten te maken?

Neurale netwerken zijn in principe niet meer dan een mapping van inputs en outputs. Buiten het feit dat je eerst de fout moet definieren, is backpropagation gebaseerd op een lokale minimalisatie van de fout. Het eerste kan opgelost worden door reinforcement learning te gebruiken. Dit laatste kan zelfs met eerder genoemde techniek niet overwonnen worden zonder workarounds in te bouwen.

[rapture]

Bij de rekenkracht moet je idd niet zoeken. Tactisch (strategisch is een heel ander niveau) werkt je met patronenherkenning en vooral de geschiedenis van voorgaande partijen. Geen wonder dat officieren, de hele wereldgeschiedenis op vlak van oorlogvoering moeten studeren. Als de tegenstander 1 zet maakt, dan weet je al wat hij van plan is en counteren.

Bovendien hebben een hoop inferieure legers erin geslaagd om bv Amerikanen wat manieren bij te leren. Creativitieit van de mens is ook iets dat je niet zomaar kan programmeren. bv Kosovo-oorlog. Serviërs hadden verouderde luchtafweer en een computer zou dan de verouderde wapensystemen gebruiken in de hoop dat het iets doet. Maar officieren zoals Zoltan Dani werken zeer sluw. Anti-radar-raketten, dus radar afzetten (computer zou denken dat hij game-over is als de wapensystemen inactief zijn). De vijand tapt/luister af, dus geen draadloze communicatie, wel over draad, auto's, wandelende boodschappers, fietsers,... (computer zou denken dat deze trage en resourcesintensieve manier van werken niet goed is). Zonder radar ben je blind zou de computer denken, de officier zet overal mensen neer die "vliegtuig" moeten roepen als er een vliegtuig voorbij vliegt en je hebt nog altijd zicht op het slagveld. Er worden veel smeulende afvalhopen neergezet om warmte-zoekers aan te trekken. Veel nepdoelwitten om de vijand te laten denken dat aan het winnen zijn. Servische mist was dicht genoeg om lasers van lasergeleide wapens tegen te houden..............

Oorlog voeren is stukken interessanter dan oorlogsimulaties. Met elke oorlog ontdekt het Westen dingen die we nog nooit gezien hebben. Een computer kan enkel in de geschiedenis kijken, maar kan niet zomaar in de toekomst kijken. Dankzij creativiteit kunnen we een stap voor de computer zijn.

Bovendien kunnen mensen ook dingen misbruiken voor iets totaal anders. We kunnen zetten/wapentuig/tactieken volledig snappen, terwijl de computer het in een object met x aantal properties stopt. Het aantal properties is eindigd en de computer kan maar een beperkt aantal dingen mee doen. bv een tractor ziet volgens de computer eruit als een landbouwvoertuig dat traag rijdt, geen wapensystemen aanboord heeft. Maar de mensen ziet dat het ook een blok staal is en het kan radargolven weerkaatsen (verstoren).

[ Voor 12% gewijzigd door rapture op 04-11-2006 13:03 ]

[Opi]

rapture schreef op zaterdag 04 november 2006 @ 12:51:
Bij de rekenkracht moet je idd niet zoeken. Tactisch (strategisch is een heel ander niveau) werkt je met patronenherkenning en vooral de geschiedenis van voorgaande partijen.

Wanneer je het op deze manier stelt lijkt het net alsof het de bedoeling is een patroon te identificeren dat van begin tot eind het gehele spel vast legt. Ondanks dat uiteindelijk je enige relevante feedback de uitkomst van een spel is, vraag ik me af of er gezocht moet of kan worden naar if-then-rules die de gewenste actie als uitkomst geven, gegeven de volledige huidige staat.

In hoeverre is het efficiënter om if-then rules van substates en sets van substates te zoeken? Zijn er überhaupt AI-technieken die op deze manier werken?

[Soultaker]

Wat versta je onder 'if-then rules' en 'substates'? Dat is bepaald geen standaardterminologie.

[Opi]

Soultaker schreef op donderdag 09 november 2006 @ 00:20:
Wat versta je onder 'if-then rules' en 'substates'? Dat is bepaald geen standaardterminologie.

If-then-rules zijn voor zover ik weet erg gangbaar in programmeren en de term wordt ook vaak gebruikt bij fuzzy-logic;
if<deze staat>, then<deze actie>

Met substates doel ik erop dat niet de volledige state vector (de huidige toestand) beschouwd wordt, maar een deel ervan. Ik was in de veronderstelling dat in bepaalde vakgebieden binnen AI standaard was.

[Felicia]

Overigens heb je (vooral) bij dammen en (in mindere mate) schaken veel repeterende stellingen en in go bijna geen (normaal gesproken plaats je om de beurt een steen op het bord; je kunt wel herhaling krijgen wanneer stenen geslagen wordt maar er worden niet zo vaak stenen geslagen behalve in ko-gevechten, en dan is er een ko-regel die herhaling verbiedt). Dat scheelt ook weer een stuk.

Sterker nog, het is een regel dat geen enkele situatie zichzelf tijdens een partij mag herhalen. Dus ook buiten een Ko-gevecht om mag dit niet gebeuren

Het probleem met Go op een computer krijgen is dat Go niet zozeer in rekentermen werkt maar met vormen. Je hebt een bepaalde opstelling waarvanuit een bepaalde actie komt. Die actie kan zijn aanvallen maar ook versterken. Dit is met name in de opening wanneer er minder dan 20 stenen liggen heel moeilijk te bepalen. Het is voor beginnende spelers naast leven en dood ook zo'n beetje het moeilijkste om te leren.
Het is overigens ook heel moeilijk om voor niet professionele spelers een programma te schrijven omdat ze de regels wel kennen maar simpelweg niet sterk genoeg zijn om een programma te schrijven dat de "regels" van de professionals kan begrijpen. Ik vraag me in dat opzicht wel af wanneer er eens een programma komt uit Korea (die pro's zijn momenteel absurd sterk ).

Ohja, ik ben momenteel maar 12k

[Verwijderd]

Felicia schreef op zaterdag 11 november 2006 @ 11:32:
...
Het is overigens ook heel moeilijk om voor niet professionele spelers een programma te schrijven omdat ze de regels wel kennen maar simpelweg niet sterk genoeg zijn om een programma te schrijven dat de "regels" van de professionals kan begrijpen. Ik vraag me in dat opzicht wel af wanneer er eens een programma komt uit Korea (die pro's zijn momenteel absurd sterk ).
...

De beste programma's worden al door (5-dan), en met behulp van (9p), professionals gemaakt. Het probleem is dat professionals niet altijd kunnen uitleggen waarom ze een bepaalde zet maken. Zoals gezegd: ze weten niet welke patronen ze herkennen.

[H!GHGuY]

in veel gevallen gebruikt een schaakcomputer een minimax tree. Mocht je deze helemaal opbouwen voor elke mogelijke positie (dus ook elk mogelijk spel) ben je heel lang bezig. Hoe dieper je kan itereren in je boom, hoe beter, maar door beperkte tijd kan je nooit de hele boom doorlopen.

Wat kun je dan doen? Op een bepaald niveau in de tree wordt een schatting gegeven van de stukken in de positie zoals ze daar staan. Zo kan men de "beste" mogelijkheid kiezen.

Wat een schaakcomputer dus goed maakt is het kunnen inschatten van hoe goed/slecht je staat gegeven de stukken op het bord. Je kan dit doen door zelf berekeningen te doen bvb: hoeveel stukken staan gedekt, hoeveel stukken heb ik nog, hoeveel stukken heeft de tegenstander, sta ik mat/schaak, staat de tegenstander mat/schaak? etc.

Beter nog is wanneer je een minimax tree combineert met AI. Je laat de schatting dan over aan het AI gedeelte terwijl je algoritme de rest uitvoert. Daarna laat je je AI gedeelte miljoenen schaakspellen bekijken met de wetenschap welke speler gewonnen is om zo te leren om de schaakposities naar waarde te schatten.

Ik durf wedden dat ook GO voor een vergelijkbare tactiek vatbaar is, hoewel ik het spel eigenlijk niet ken.

[Oscar Mopperkont]

H!GHGuY schreef op zaterdag 11 november 2006 @ 17:19:
Ik durf wedden dat ook GO voor een vergelijkbare tactiek vatbaar is, hoewel ik het spel eigenlijk niet ken.

Go is zeker vatbaar voor dezelfde techniek, waar het niet dat Go "ietsjes" complexer is dan schaken. Bij schaken zijn computers snel genoeg om de gevolgen van een zet behoorlijk wat zetten door te rekenen. Bij Go stijgt het aantal mogelijkheden echter zo explosief dat je die brute force tactiek niet kan gebruiken en dat is dus het grote verschil met schaken.

[Opi]

Oscar Mopperkont schreef op zaterdag 11 november 2006 @ 17:22:
[...]

Go is zeker vatbaar voor dezelfde techniek, waar het niet dat Go "ietsjes" complexer is dan schaken. Bij schaken zijn computers snel genoeg om de gevolgen van een zet behoorlijk wat zetten door te rekenen. Bij Go stijgt het aantal mogelijkheden echter zo explosief dat je die brute force tactiek niet kan gebruiken en dat is dus het grote verschil met schaken.

Ik ben helaas niet helemaal into de gebruikte algoritmen op het gebied van schaken, maar hier lees ik dat er sinds een aantal jaren succesvol een overstap gemaakt is van brute force naar een focus op patronen. Verschil in complexiteit is voor zover ik weet niet kwantificeerbaar en in hoeverre zich dit uit bij algoritmen is mij zodoende ook niet bekend. Het enige wat ik zo snel kan bedenken is hoog nonlinear gedrag wanneer het aankomt op gebruik van neurale netwerken. Dit gedrag kan leiden tot problemen met trainen van de netwerken (zeer veel lokale optima).

[Oscar Mopperkont]

Opi schreef op zaterdag 11 november 2006 @ 21:47:
Ik ben helaas niet helemaal into de gebruikte algoritmen op het gebied van schaken, maar hier lees ik dat er sinds een aantal jaren succesvol een overstap gemaakt is van brute force naar een focus op patronen. Verschil in complexiteit is voor zover ik weet niet kwantificeerbaar en in hoeverre zich dit uit bij algoritmen is mij zodoende ook niet bekend. Het enige wat ik zo snel kan bedenken is hoog nonlinear gedrag wanneer het aankomt op gebruik van neurale netwerken. Dit gedrag kan leiden tot problemen met trainen van de netwerken (zeer veel lokale optima).

Ik ben daar (natuurlijk) ook niet in thuis, maar bij schaken zit je met minder velden op het bord en met minder stukken, terwijl er bij Go elke zet een stuk bijkomt. H!GHGuY had het over een strategie die voor een groot deel gebaseerd was op brute force en dat is bij Go dus heel moeilijk omdat je niet ver vooruit kunt kijken, daar is het aantal zetten te groot voor. Dus je zult denk ik meer dan bij schaken moeten leunen op een goede patroonherkenning, maar aangezien een computer nog niet in staat is om een goede speler op een 19x19 bord te verslaan, is het kennelijk nog niet gelukt om dat er in te stampen. Maar hoe zou je zo'n programma ook moeten trainen? Als je een programma wilt trainen moet je hem toch wel kunnen vertellen wanneer een bepaalde spelsituatie "goed" is en wanneer niet? Of zie ik dat verkeerd?

En wat bedoel je eigenlijk precies met dat de complexiteit niet kwantificeerbaar is? Kun je niet zeggen dat Go complexer is omdat het aantal spelmogelijkheden veel groter is?

[Confusion]

H!GHGuY schreef op zaterdag 11 november 2006 @ 17:19:
Ik durf wedden dat ook GO voor een vergelijkbare tactiek vatbaar is, hoewel ik het spel eigenlijk niet ken.

Het probleem met Go is dat stenen kunnen worden 'gedood', waarbij ze van het bord worden genomen. Met de juiste serie zetten kan je bij wijze van spreken met een net iets andere uitgangssituatie het spel overniew beginnen. De waarde van een positie is daarom heel moeilijk vantevoren te schatten: heel diep in de boom zou weleens een veel betere positie tevoorschijn kunnen komen. In het schaken is de schatting van de toekomstige situatie op basis van de huidige stelling (of het schatten van de situatie over 10 zetten op basis van de situatie over 5 zetten) vrij betrouwbaar en dat is de reden dat computers topschakers kunnen verslaan. Bij Go is dat vrijwel niet mogelijk en daarom zijn de algoritmen die bij schaken gebruikt worden niet op Go toepasbaar.

[H!GHGuY]

@confusion:

dat maakt niet uit. een minmax tree houdt eigenlijk rekening met het feit dat je zelf de zet doet die uiteindelijk het best uitkomt voor jou en dat de tegenstrever dit ook voor zichzelf doet.

Het probleem ligt denk ik idd in het explosief aantal mogelijkheden. Hoewel dit voor het "juiste" neuraal netwerk geen probleem mag zijn.
Ik denk dat het wachten is op een neuraal netwerk dat zowel krachtig genoeg als performant genoeg is om Go te spelen. Je kan natuurlijk enkele miljarden neuronen aan het werk zetten en enorme hoeveelheden spellen erdoor jagen, maar het zal uiteindelijk nog performant moeten blijven om op een gemiddelde PC te draaien...

[Confusion]

H!GHGuY schreef op zondag 12 november 2006 @ 13:32:
Ik denk dat het wachten is op een neuraal netwerk dat zowel krachtig genoeg als performant genoeg is om Go te spelen. Je kan natuurlijk enkele miljarden neuronen aan het werk zetten en enorme hoeveelheden spellen erdoor jagen,

Al legde je het oppervlak van de aarde vol met neuronen en liet je die een miljoen jaar spellen spelen, dan nog zou het systeem niets van Go bakken op basis van een minimax methode.

[Opi]

Oscar Mopperkont schreef op zaterdag 11 november 2006 @ 22:17:Als je een programma wilt trainen moet je hem toch wel kunnen vertellen wanneer een bepaalde spelsituatie "goed" is en wanneer niet? Of zie ik dat verkeerd?

Tot op zekere hoogte. Een spelsituatie op zich is niet 'goed' of 'fout'. Ter illustratie het volgende; als je op een schommel zit en je wilt zo hoog mogelijk naar voren (of hoe je dat ook uitlegt ), dan zal je toch op een gegeven moment naar achteren moeten. De situatie om achter te zijn is relatief ten op zichte van de uitgangssituatie 'fout'. Op de lange termijn is hij wel voordelig. Een kostenfunctie is niet zozeer gebaseerd op een individuele actie maar op een set van acties door middel van welke het uiteindelijke doel behaald wordt.

En wat bedoel je eigenlijk precies met dat de complexiteit niet kwantificeerbaar is? Kun je niet zeggen dat Go complexer is omdat het aantal spelmogelijkheden veel groter is?

Een systeem is niet noodzakelijkerwijs meer gecompliceerd dan een ander systeem enkel omdat het aantal mogelijkheden groter is. Dingen als afhankelijkheid van toestanden en acties spelen ook een rol.

H!GHGuY schreef op zondag 12 november 2006 @ 13:32:
Het probleem ligt denk ik idd in het explosief aantal mogelijkheden. Hoewel dit voor het "juiste" neuraal netwerk geen probleem mag zijn.
Ik denk dat het wachten is op een neuraal netwerk dat zowel krachtig genoeg als performant genoeg is om Go te spelen.

Een neuraal netwerk generaliseert en wat dat betreft is het probleem te overwinnen. Zoals ik eerder aangegeven hebben convergeren ze echter niet noodzakelijkerwijs naar het globale optimum en dit is iets wat met het toepassen het alternatief wel mogelijk is.

[Oscar Mopperkont]

Opi schreef op zondag 12 november 2006 @ 17:35:
Tot op zekere hoogte. Een spelsituatie op zich is niet 'goed' of 'fout'.

Ik zeg het wat te simpel, maar je zult wel moeten bepalen hoe gewenst de situatie is, wat je zelf zegt er moet een bepaalde kostenfunctie aan zitten om de ene situatie van de andere te kunnen onderscheiden.

[Soultaker]

Opi schreef op zondag 12 november 2006 @ 17:35:
Tot op zekere hoogte. Een spelsituatie op zich is niet 'goed' of 'fout'.

Ben ik het niet mee eens. Natuurlijk maakt het uit wat je er zelf van maakt, maar vaak kan een go-speler wel zeggen wie er vóór staat. Een probleem met go is dat elke individuele zet maar een heel klein beetje verschil maakt, maar met tien zwakke zetten op een rij sta je wel achter.

Confusion schreef op zondag 12 november 2006 @ 12:38:
Het probleem met Go is dat stenen kunnen worden 'gedood', waarbij ze van het bord worden genomen.

Dat is niet de kern van het probleem, om twee redenen:
• als je op een beetje nivo speelt, is het slaan van meer dan één steen tegelijk zeldzaam. Het spel gaat dus eigenlijk altijd 'vooruit', een grote groep slaan en opnieuw beginnen kan in theorie, maar komt in praktijk eigenlijk nooit voor (en als het wel gebeurt, geeft de tegenstander meestal op).
• andere spellen waarbij impliciete verbindingen een grote rol spelen maar waarbij geen stukken geslagen worden zijn net zo moeilijk te programmeren. Kijk bijvoorbeeld naar Havannah, wat simpelere regels heeft dan Go (een variant op Hex) en waarbij alleen maar stenen worden geplaatst (nooit verplaatst, nooit geslagen).

In het schaken is de schatting van de toekomstige situatie op basis van de huidige stelling (of het schatten van de situatie over 10 zetten op basis van de situatie over 5 zetten) vrij betrouwbaar en dat is de reden dat computers topschakers kunnen verslaan.

Bingo.

[burne]

De meest voor de hand liggende link heb ik nog niet langs zien komen:
http://en.wikipedia.org/wiki/Computer_Go

[Opi]

Soultaker schreef op maandag 13 november 2006 @ 01:22:
Ben ik het niet mee eens. Natuurlijk maakt het uit wat je er zelf van maakt, maar vaak kan een go-speler wel zeggen wie er vóór staat. Een probleem met go is dat elke individuele zet maar een heel klein beetje verschil maakt, maar met tien zwakke zetten op een rij sta je wel achter.

Punt blijft dat je een indivuele spelsituatie niet altijd als 'goed' of 'fout' kunt bestempelen. In de mij bekende algoritmen wordt dit ook niet gedaan.

[Verwijderd]

Computers kunnen nu wel winnen tegen mensen alleen ze kunnen nog niet zo effecient omgaan met bv schaken dan wij mensen .

Een computer moet alle stenen langsgaan om te bepalen welke het beste is. terwijl wij een pion gewoon laten staan behalve als we hem echt nodig hebben. maar de vraag is hoe doen wij dat nou eigenlijk en dat is best complex (ik kan het je iedergeval niet 1,2,3 uitleggen).

de schaak programma's die van de top spelers gewonnen hebben, laten ze meestal eerst tegen zichzelf spelen en dat een paar miljoen keer zodat het programma vanzich zelf kan leren. Er zijn nog geen systemen waarbij het net zo efficient als bij ons gaat.

Bij het spel GO is dit zelfs nog complexer.

[Opi]

Verwijderd schreef op maandag 13 november 2006 @ 20:12:
Een computer moet alle stenen langsgaan om te bepalen welke het beste is. terwijl wij een pion gewoon laten staan behalve als we hem echt nodig hebben. maar de vraag is hoe doen wij dat nou eigenlijk en dat is best complex (ik kan het je iedergeval niet 1,2,3 uitleggen).

Een mens neemt ook de volledige spelsituatie in zich op. Ik vermoed dat je bedoelt dat niet elke afzonderlijke zet beschouwd hoeft te worden door de mens. Dit is bij een aantal algoritmen ook het geval.

de schaak programma's die van de top spelers gewonnen hebben, laten ze meestal eerst tegen zichzelf spelen en dat een paar miljoen keer zodat het programma vanzich zelf kan leren. Er zijn nog geen systemen waarbij het net zo efficient als bij ons gaat.

Het kan goed zijn dat een programma efficienter leert dan een mens, maar alleen op een andere manier. De meeste algoritmen zijn inderdaad gebaseerd op trial-and-error, maar dit is denk ik het geval om de flexibiliteit zo groot mogelijk te houden; wanneer je taktieken expliciet in het algoritme zet dan kan het zijn dat je bepaalde mogelijkheden onbenut laat.

Bij het spel GO is dit zelfs nog complexer.

Kan je me uitleggen waarin Go complexer is?

[Verwijderd]

Een mens hoef je alleen de zetten uitteleggen die elke steen kan maken meer niet. Vervolgens komen ze er zelf wel uit hoe het ongeveer moet (niet meteen super goed ofzo).
Het volledige spelsituatie hoeft een persoon niet eens in zich optenemen. Na 4 keer het spel gespeelt te hebben zie je toch wel (bij de meeste mensen) grote vooruitgang.
Een computer zou dit nooit kunnen. (tot nu toe).

Ik doel vooral op het feit dat wij dingen zo anders aanpakken dan computers het doen. en het meest intresante is dan ook hoe doen wij het dan. (ik heb hier wel ooit een programma overgezien was wel coowl (bij het schaken dan))

Wij zien gewoon welke taktiek/set het beste is en wij zien ook dingen over het hoofd per ongeluk.

Een computer zit meestal toch wel vast in een systeem. en leer systemen zitten weer vast in dat leersysteem. enzz.

De computers kunnen door stappen vooruit te denken wel bepalen wat de beste set is of 1 van de beste kiezen. alleen dit kost gigantisch veel rekenvermogen.

Ik denk dan ook dat je vooral moet gaan kijken hoe de mens het doet en daarme iets maken wat het op een redelijke zelfde manier het gaat oplossen.

[Christiaan]

Verwijderd schreef op dinsdag 31 oktober 2006 @ 15:00:
Dit is denk ik de meest interessante opmerking uit dit topic. Uit hersenonderzoek blijkt dat professionele schakers veel minder hersenactiviteit vertonen bij het schaken dan onervaren mensen die "luk raak een beetje aan het proberen zijn". Voor muziek spelen geldt hetzelfde. Het blijkt ook dat ervaren schakers bepaalde slechte zetten gewoon "niet zien". Niet bewust in ieder geval. Ze kijken direct naar de patronen die ze herkennen en denken dan ook aan patronen die daar op lijken. Vooral dit "erop lijken" kan vaak tot interessante gedachten leiden die moeilijk te programmeren zijn. Als ik een boom zie, denk ik aan een boomdiagram eigenlijk ook meteen een beetje aan kansrekening. Die link is voor mij heel vanzelfsprekend, maar leer een computer dit maar eens...

Dit is wat binnen de cognitieve psychology 'expert minds' worden genoemd. Het is iets wat voorkomt bij mensen die zeer goed geworden zijn in wat ze doen, zoals programmeurs, schakers, atleten, enz. Met name bij meer abstracte problemen valt direct op dat deze mensen ontzettend snel patronen herkennen en daar op in kunnen spelen. Niet alleen deze herkenning is sneller, vooral omdat ze in de loop der tijd veel patronen hebben ontwikkeld, ze hebben ook een speciaal geheugen ontwikkelt om bijvoorbeeld vele series van vorige zetten te onthouden. Daarnaast zie je dat experts vaak zeer abstract kunnen denken, dus in het geval van programmeurs volstrekt los van de code zelf.

[Opi]

Christiaan schreef op zaterdag 18 november 2006 @ 00:20:
Daarnaast zie je dat experts vaak zeer abstract kunnen denken, dus in het geval van programmeurs volstrekt los van de code zelf.

Kan abstract denken hier beschouwd worden als het kunnen isoleren van relevante patronen binnen een oneindige hoeveelheid mogelijke patronen. Is binnen de (cognitieve) psychologie bekend hoe dit proces in zijn werk gaat of zijn er hypothesen over?

[Christiaan]

Opi schreef op zaterdag 18 november 2006 @ 00:47:
Kan abstract denken hier beschouwd worden als het kunnen isoleren van relevante patronen binnen een oneindige hoeveelheid mogelijke patronen.

Yep

Is binnen de (cognitieve) psychologie bekend hoe dit proces in zijn werk gaat of zijn er hypothesen over?

Niet voor zover ik weet. Als dat wel bekend zou zijn zou de stap naar veel betere AI zo gemaakt zijn. Menselijke denkprocessen lijken vooralsnog uiterst fuzzy. Vrij simpele denkprocessen zijn wel te simuleren met complexe cognitieve modellen (het pandemoniummodel is hier waarschijnlijk ook te gebruiken), maar zelfs als die simulaties in de buurt van het menselijk denken komen is het de vraag of mensen ook echt zo denken als die modellen suggereren. Maar aangezien ik geen cognitief psycholoog ben is mijn kennis over dit onderwerp beperkt.