[Java] Artificial Intelligence -> Hoe, Wat, Welke methode?

[coenbijlsma]

Hallo iedereen,

Mijn case
om de studie in Java enigszins intrigerend te houden voor mezelf ben ik op zoek gegaan naar een leuk actueel onderwerp. Dat heb ik (denk ik) gevonden in AI. Om dat in de praktijk te brengen, ben ik begonnen met het schrijven van een schaakspelletje, waarbij het de bedoeling is dat de computerspeler zelf het schaken leert; volgens mij dus Strong AI.

Ik heb mezelf al een beetje verdiept in onderstaande artikelen, maar ik wil graag jullie mening over AI weten, en welke methode jullie denken dat het beste is (als daar sprake van is). Misschien hebben jullie ook nog interessante zoektips?

Artikelen:
Strong AI op Wikipedia
Overzicht AI op Wikipedia
Genetic Programming
Google AI

Wat ik vooral met het maken van dit spelletje wil bereiken is:
- Er achter komen hoe je AI kunt implementeren
- Bestaande manieren de revue laten passeren
- Kijken of er toch niet nog een betere manier te vinden is

Ik ben erg nieuwsgierig naar jullie reacties!!

[NMe]

Hoeveel ervaring heb je met Java en programmeren in het algemeen? Heb je wel eens een "normale" AI geïmplementeerd? Om je schaakspel nog steeds als voorbeeld te gebruiken, ken je minimax?

Ik kan me niet echt aan de indruk onttrekken dat je geen idee hebt waar je aan wil beginnen. Zelflerende software is over het algemeen complex te noemen, en er zijn complete studies en boeken die het behandelen. Onderschat je het niet een beetje?

[eghie]

Ik heb er ooit een stukje geschreven voor de GoT PW contest: A.I.

Hier staan wat linkjes naar wat sites, die ik toen met behulp van andere mensen hier op GoT, heb uitgezocht. Ze gaan vooral over Genetische algoritmen en Neurale netwerken. Ik hoop dat je er wat aan hebt.

[JHS]

eghie: De wiki is voor mij niet bereikbaar, heb je het misschien in een ander formaat, of zijn het linkjes die we zelf ook wel kunnen vinden?

[Cloud]

Ik heb nog wel een linkje voor je, over AI binnen schaakprogramma's, link. Maar net als -NMe- twijfel ik eraan, of je hier wel aan moet beginnen op dit moment. En dan nog vooral schaken. Is het niet verstandiger een ander spel, ietwat gemakkelijker, te nemen als beginpunt? In elk geval succes ermee.

[12_0_13]

Makkelijker is het inderdaad om te beginnen met een simpeler spel, zoals boter-kaas-en-eieren (tic-tac-toe). Hier kan je al verschillende vormen van AI op loslaten, en het is een stuk minder complex dan schaken.

Leuke oefening bij het leren programmeren vind ik zelf is om tetris te maken. Hier kan je goed nadenken over de data-structuren, algoritmes, etc. die hierbij komen kijken. Heb je eenmaal een tetris, dan is de uitbreiding naar een computer-tetris speler die tegen een mens speelt natuurlijk een erg leuke uitbreiding

edit: strong ai is nog wel een beetje een ver-van-mijn-bed-show als je het mij vraagt, als ik de definities goed begrijp. Een leuk boek om te lezen is "On Intelligence" van Jeff Hawkins, dat handeld over "echte" AI vs. alle traditionele aanpakken

[ Voor 19% gewijzigd door 12_0_13 op 19-12-2005 19:13 ]

[Verwijderd]

cbijlsma schreef op maandag 19 december 2005 @ 18:43:
Hallo iedereen,

Mijn case
om de studie in Java enigszins intrigerend te houden voor mezelf ben ik op zoek gegaan naar een leuk actueel onderwerp. Dat heb ik (denk ik) gevonden in AI. Om dat in de praktijk te brengen, ben ik begonnen met het schrijven van een schaakspelletje, waarbij het de bedoeling is dat de computerspeler zelf het schaken leert; volgens mij dus Strong AI.

Ik heb mezelf al een beetje verdiept in onderstaande artikelen, maar ik wil graag jullie mening over AI weten, en welke methode jullie denken dat het beste is (als daar sprake van is). Misschien hebben jullie ook nog interessante zoektips?

Artikelen:
Strong AI op Wikipedia
Overzicht AI op Wikipedia
Genetic Programming
Google AI

Wat ik vooral met het maken van dit spelletje wil bereiken is:
- Er achter komen hoe je AI kunt implementeren
- Bestaande manieren de revue laten passeren
- Kijken of er toch niet nog een betere manier te vinden is

Ik ben erg nieuwsgierig naar jullie reacties!!

Tja, als je Java wilt leren kun je mini-max implementeren, maar om een schaakprogramma Strong AI te noemen..... Nee

In de wetenschappelijke wereld wordt aan het mogelijk zijn van Strong AI nog getwijfeld (dacht ik). Zelf twijfel ik er niet aan dat je een Strong AI zou kunnen maken. Een simpele definitie van een Strong AI is dat deze alles kan wat ik kan met dezelfde of hogere snelheid. Jouw schaakprogramma valt daar niet onder, omdat deze alleen maar dat kan. Strong AI is in mijn ogen al in theorie opgelost. Het probleem met deze oplossing is dat deze gigantisch veel rekenkracht nodig heeft. Een goede implementatie is >30<50 manjaar als een ruwe schatting. Vergeleken met Sun Solaris(3000 manjaar) is dit bijna niets.

[Alarmnummer]

Onder ai valt een heel breed skala van technieken en het is daarom verstandig om hier eerst een beeld van te krijgen, en daarna een of meer technieken te selecteren en daar wat mee te experimenteren. Ik ben in het verleden bv veel bezig geweest met ruleengines en expertsystemen, maar dat is maar zo`n klein onderdeel van het geheel dat je in de verste verte nog niet in aanraking komt met alle andere technieken.

Informatief boek (die ik zelf ook heb doorgelezen)
Artificial Intelligence: A Modern Approach

[jvo]

Alarmnummer schreef op maandag 19 december 2005 @ 21:07:
Informatief boek (die ik zelf ook heb doorgelezen)
Artificial Intelligence: A Modern Approach

Inderdaad absoluut een aanrader. Loopt van zoekalgorithmes tot planningssystemen. En een heel mooi uitgebreid stuk over eerste orde logica en de toepassing ervan in AI.

[BCC]

Pak dan: "Neural Networks, a comprehensive foundation" ook even mee.

[Verwijderd]

Zoals al is voorgesteld, zou ik eerst beginnen met een ander spel te leren spelen voordat je schaak doet.

http://www.natural-selection.com/Library/2001/IEEE-TEVC.pdf is een document van iemand die een damprogramma (eigenlijk checkers) mbh. neurale netwerken en evolutionaire algoritmen heeft geschreven. Het principe wordt heel duidelijk uitgelegd en je kunt het zelf ook wel namaken.

Bij schaken zit het wel anders en je zult dan ook een ander neuraal netwerk moeten gebruiken. Zonder kennis van neurale netwerken kom je er niet, omdat er, zoals in http://www.aaai.org/AITopics/html/chess.html staat, gigantisch veel mogelijke zetten zijn en je dus onmogelijk voor elke mogelijkheid gegevens bij kunt houden.

In plaats van de posities van vakjes te gebruiken zoals in de eerste link, kun je ook invoer voor je neurale netwerk berekenen aan de hand van een aantal variabelen (waaronder de posities van jouw en je tegenstanders zetten), maar dan maak je al gebruik van voorkennis van schaken, wat jij volgens mij niet wil. Volgens mij wordt deze methode het meest toegepast in schaaksoftware.

In plaats van evolutionaire algoritmen te gebruiken, zou ik reinforcement learning toepassen icm. minimax en een neuraal netwerk. Op http://lslwww.epfl.ch/~an...ack/classes/RLJavaBJ.html staat een voorbeeld van blackjack met reinforcement learning.. Een stuk makkelijker dan schaken als je wilt beginnen.

edit: zoals strong AI op Wikipedia is uitgelegd, gaat het erom dat je applicatie ook weet dat-ie aan het schaken is. Iets wat denk ik wel mogelijk moet zijn maar tegen die tijd zijn wij er denk ik allang niet meer. Machine learning is over het algemeen (en misschien zelfs wel) weak AI, maar ik ben geen filosoof.

edit 2: als we dan toch nuttige boeken opsommen; Sutton & Barto hebben een heel leesbaar boek geschreven over reinforcement learning. Vond het op gebied van AI het meest interessante boek wat ik dit jaar gelezen heb.

[ Voor 19% gewijzigd door Verwijderd op 19-12-2005 21:41 ]

[eghie]

JHS schreef op maandag 19 december 2005 @ 19:04:
eghie: De wiki is voor mij niet bereikbaar, heb je het misschien in een ander formaat, of zijn het linkjes die we zelf ook wel kunnen vinden?

Ik had hem nog open staan in een tabje van Firefox.

Hier volgen een aantal links met wat uitleg over neurale netwerken:
Inleiding Neurale Netwerken
Leren met Neurale Netwerken
Voorbeeld van Neurale Netwerken
Uitgebreide uitleg over Neurale Netwerken
Wikipedia
Reinforcement learning met voorbeeld

Ik wil er nog een keer een uitgebreid iets voor schrijven, voor die PW contest ([rml][ Contest] BotWars[/rml]), maar de kennis is er nog niet echt helemaal voor, dus wil me er nog enigzins in verdiepen.

[Eelke Spaak]

Alarmnummer schreef op maandag 19 december 2005 @ 21:07:
Informatief boek (die ik zelf ook heb doorgelezen)
Artificial Intelligence: A Modern Approach

Inderdaad een prettig boek, zij het wel wat erg toegespitst op de directe toepassing van AI technieken in de informatica.

Wat ik een interessante, andere, invalshoek van AI vind, is de manier waarop de menselijke psychologie en het menselijk brein ons inspiratie kunnen geven voor andere (evt. betere) algoritmes, en hoe het bestuderen van deze algoritmes weer leidt tot meer inzicht over de mens. Maar goed, dat is een andere discussie .

[Verwijderd]

ik zou met othello (reversi) beginnen omdat de evaluatie functie van deze heel simpel te bepalen is, minimax met het aantal stenen als punten functie. Bij schaken moet je wel goed nadenken over hoeveel punten je bepaalde stenen of situaties geeft. trouwens dat is zeker geen strong AI. Strong AI is gewoon een gedachte gang waarbij men denkt dat computers net zo kunnen denken als mensen (met bewustzijn en al) en met schaken of minimax word gewoon hard gerekend. om schaken perfect te kunnen spelen met minimax zou je miljoenen jaren kwijt zijn dus daar begint niemand aan. kijk ook eens naar AI op het gebied van spellen als GO, want die zijn dus echt nog niet opgelost, succes ermee in ieder geval maar ik zou je toch aanraden een informatica opleiding te doen voor dit soort onderwerpen :):)

[BCC]

Go wordt over het algemeen moeilijker geacht dan schaken. Begin eerst maar eens met iets als boter kaas en eieren

[ Voor 10% gewijzigd door BCC op 20-12-2005 22:02 ]

[Opi]

Zoals anderen al opgemerkt hebben is het onwaarschijnlijk dat je strong AI toe kunt passen. In principe ben je enkel bezig met een veredeld zoekalgoritme. Neurale netwerken (ik ga ervan uit dat de meesten op multilayer perceptrons duiden) hebben op dit vlak ernstige beperkingen aangezien ze in een lokaal minimum terecht kunnen komen. Lineare neurale netwerken (je zou een soort coarse coding kunnen proberen en in het bijzonder een variant op radial basis functions kunnen beschouwen) zijn wat dat betreft minder beperkt, maar hebben als nadeel dat ze alsnog erg veel geheugen vreten.

Reinforcement learning is een techniek die je kunt beschouwen, maar kan zeer veel tuning nodig hebben omdat het erg gevoelig kan zijn voor de waarde van bepaalde variabelen (oa discount factor en lambda (in het geval je eligibility traces toepast). Conversie naar de optimale oplossing is gegarandeerd (overigens nog niet wanneer function approximators gebruikt worden) onder de voorwaarde dat elk state-action paar een oneindig aantal keer geëvalueerd wordt.

De in [rml]playroll in "[ Java] Artificial Intelligence -> Hoe, W..."[/rml] geplaatste link naar het boek van Barto en Sutton is inderdaad erg nuttig. Het is een online versie van het boek zelf en het boek is zeker aan te raden. Andere bronnen die ik je aan kan raden zijn het boek Neuro Dynamic Programming van Tsitsiklis en Bertsekas en de paper Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore, ``Reinforcement Learning: A Survey,'' Journal of Artificial Intelligence Research, Volume 4, 1996.

offtopic:
Wedden dat ik weer een PM van Curry krijg omdat hij vermoedt dat ik nu aan accountsharing doe.

[Verwijderd]

Ik ben het niet helemaal eens met de uitspraken die o.a. Opi gedaan heeft over AI technieken zoals neurale netwerken en reinforcement learning. Ik zal proberen duidelijk te maken waarom.

De gangbare manier om een computer een bordspel (zg. zero-sum spel, voor 2 spelers, waarbij volledige informatie beschikbaar is en geen kansen of toeval in het spel zijn) te laten spelen, maakt gebruik van een evaluatiefunctie. Dit is een functie die bij een bepaalde stand van het spel een getal oplevert dat aangeeft hoe gunstig die bordsituatie is. Met behulp van het minimax-zoekalgorithme (of, beter nog, alpha-beta search, waar je ook nog allerlei pruning-technieken op kunt toepassen) kun je die functie gebruiken om voor een bepaalde bordpositie de beste zet te bepalen.

Zo'n evaluatiefunctie met de hand schrijven is in de praktijk niet te doen. Dus wil je die functie wiskundig benaderen. Het eerste waar je dan natuurlijk aan denkt is een neuraal netwerk (dat is eigenlijk gewoon een mechanisme om een willekeurige wiskundige functie te benaderen), maar er zijn ook een boel andere mogelijkheden.

Laten we zeggen dat we een neuraal netwerk gebruiken om de evaluatiefunctie te representeren. Dan heb je een paar nieuwe problemen: wat moet de layout van mijn netwerk zijn? Welk algorithme ga ik gebruiken om mijn netwerk te trainen? Maar al helemaal moeilijk is de vraag: waar haal ik mijn trainingsdata vandaan? Neem het schaakspel. Om een beetje interessante evaluatiefunctie te benaderen heb je ettelijke miljoenen bordsituaties nodig. Hoe ga je voor al die situaties bepalen wat de juiste waarde van de evaluatiefunctie is?

Het probleem hierbij is dat men met neurale netwerken (doorgaans) gebruik maakt van "supervised learning": je geeft je netwerk voorbeelden met daarbij ook een voorbeeld van het juiste antwoord. Het probleem is dat je deze informatie voor een spel zoals schaken niet hebt. Daarom kun je als alternatief bijvoorbeeld overwegen om reinforcement learning te gebruiken. Met reinforcement learning geef je een ander soort feedback (bijv. "je hebt verloren" in plaats van "je had zet x moeten doen"). Je hoeft de evaluatiefunctie dan niet te kennen. Als je bovendien temporal-difference learning gebruikt (een variant van reinforcement learning), kun je uit de uitkomst van een spel conclusies trekken over alle zetten in de partij. Je zou dan je programma tegen een ander programma - of tegen zichzelf kunnen laten spelen.

(overigens kun je RL en NN combineren, waarbij je RL gebruikt om het NN van feedback te voorzien)

Het grote nadeel van reinforcement learning is dat het in verhouding veel langer duurt om iets bruikbaars te leren dan met supervised learning, omdat er minder directe informatie voor handen is. De opmerking van Opi dat RL gevoeliger zou zijn voor parameters is naar mijn mening onzin; voor neurale netwerken zijn ook erg veel parameters van belang. Het is eerder het aantal benodigde trainingsrondes wat een probleem is.

De opmerking dat een neuraal netwerk "in een lokaal minimum terecht kan komen" slaat ook niet echt ergens op. Je hebt altijd kans dat je in een lokaal minimum zit. Zeker bij een enigszins complex probleem, daar zul je in de praktijk altijd in een lokaal minimum blijven steken, onafhankelijk van de manier waarop je je oplossing zoekt (je kunt immers nooit de hele probleemruimte doorzoeken). Je probeert alleen een zo goed mogelijk minimum te vinden. Dit heeft dus absoluut niets te maken met de eigenschappen van neurale netwerken.

Maar goed. Ik heb het idee dat het implementeren van een neuraal netwerk en/of reinforcement learning voor het leren van een evaluatiefunctie voor boter-kaas-en-eieren al behoorlijk hoog gegrepen is voor een beginnend programmeur. Laat staan voor een spel zoals schaken. Je hebt geen idee waar je aan begint...

[Opi]

Verwijderd schreef op woensdag 21 december 2005 @ 00:30:
Het grote nadeel van reinforcement learning is dat het in verhouding veel langer duurt om iets bruikbaars te leren dan met supervised learning, omdat er minder directe informatie voor handen is. De opmerking van Opi dat RL gevoeliger zou zijn voor parameters is naar mijn mening onzin; voor neurale netwerken zijn ook erg veel parameters van belang. Het is eerder het aantal benodigde trainingsrondes wat een probleem is.

Ik heb geen data waar supervised learning technieken vergeleken werden met reinforcement learning. Verder vergelijk ik nergens neurale netwerken alleen met reinforcement learning. Gezien het probleem lijkt de TS mij genoodzaakt om neurale netwerken als mapping te gebruiken van de value function die men middels reinforcement learning poogt te maken. Uit verschillende papers blijkt dat het aantal trainingsrondes gerelateerd is aan zowel de keuze van de function approximator (inclusief architectuur en andere parameters van het netwerk) als de keuze van de waarden van de parameters die in het reinforcement learning algoritme gebruikt worden.

De opmerking dat een neuraal netwerk "in een lokaal minimum terecht kan komen" slaat ook niet echt ergens op. Je hebt altijd kans dat je in een lokaal minimum zit. Zeker bij een enigszins complex probleem, daar zul je in de praktijk altijd in een lokaal minimum blijven steken, onafhankelijk van de manier waarop je je oplossing zoekt (je kunt immers nooit de hele probleemruimte doorzoeken). Je probeert alleen een zo goed mogelijk minimum te vinden. Dit heeft dus absoluut niets te maken met de eigenschappen van neurale netwerken.

Dit heeft alles te maken met neurale netwerken. Neurale netwerken zijn een lokaal zoek algoritme omdat ze gebaseerd zijn op de gradiënt van de kostfunctie. Globale zoek algoritmen, zoals, naar ik meen, genetische algoritmen, hebben een aanzienlijk grotere kans om een globaal optimum te vinden doordat ze de gehele zoekruimte doorzoeken (met een beperkte resolutie in acht nemende).

Maar goed. Ik heb het idee dat het implementeren van een neuraal netwerk en/of reinforcement learning voor het leren van een evaluatiefunctie voor boter-kaas-en-eieren al behoorlijk hoog gegrepen is voor een beginnend programmeur. Laat staan voor een spel zoals schaken. Je hebt geen idee waar je aan begint...

Yep.

Wellicht wil de TS kijken naar TD-gammon van Tesauro en proberen dit algoritme te reproduceren.

[ Voor 3% gewijzigd door Opi op 21-12-2005 00:58 . Reden: algorithme -> algoritme ]

[Verwijderd]

offtopic:
We hebben het hier toch wel over een "algoritme"?

[KopjeThee]

Bij mij staat (gelezen) in de kast:
Scalable Search in Computer Chess
van Ernst A. Heinz
Een aanrader (met hoofdletters) voor iemand die een schaakprogramma wil schrijven. Vergis je niet in de hoeveelheid werk...

De AI zit normaalgesproken voornamelijk in de zoektechniek (voor zover dat AI is) en uitgebreide positie evaluatie heuristieken. Dus eigenlijk komt er geen machine learning aan te pas, maar misschien valt er wel iets te bedenken. Er zijn wel wat dingen aan de hand die aandacht verdienen:
- Voor supervised methoden: Je wilt graag weten of je zet tot winst of verlies leidt. Dat weet je pas aan het einde van het spel en het is maar de vraag in hoeverre de huidige zet daar verantwoordelijk voor was.
- Er zijn veel mogelijk bordposities en wat een goede zet is, hangt vaak van subtiele verschillen af. Elke leermethode die onzorgvuldig met deze subtiliteiten omgaat, is ongeschikt.

Mijn vermoeden is dat het niet mee zal vallen een evaluatie functie te "leren" die net zo goed is als de huidige heuristische functies, omdat de heuristieken zich ruimschoots in de praktijk hebben bewezen.

Een andere kandidaat om machine learning toe te passen, is bij het bepalen van de volgorde waarin je zetten gaat evalueren tijden je zoekalgoritme (dynamic move ordering). Ook daar zal het niet meevallen om het beter te doen, omdat de iterative deepening score vaak wordt gebruikt.

Ik zou zeggen: Kijk hoe huidge schaakprogramma's werken. Elke plaats waar nu heuristieken worden gebruikt is een potentiele plaats voor machine learning. Maar die heuristieken zijn vaak redelijk geavanceerd en getuned, dus het zal niet meevallen, denk ik... Aan de andere kant... als iedereen zo zou denken, zou er geen vooruitgang meer zitten in computer schaak.

[ Voor 74% gewijzigd door KopjeThee op 21-12-2005 14:33 ]

[coenbijlsma]

Jongens,

allemaal heel erg bedankt voor jullie reacties, ik heb nog geen tijd gehad om ze te lezen, maar die is nu dan aangebroken.

@-NMe-: ik heb inderdaad geen idee waar ik aan begin, maar ooit moet ik een start maken

Zodra ik alles gelezen heb kom ik weer met nieuwe vragen. Ik houd jullie op de hoogte van 'mijn' ontwikkelingen!

edit:
Ik kom er inderdaad ook zo langzamerhand achter dat ik misschien beter mijn schaak-missie kan stopzetten en eens voorzichtig naar boter-kaas-en-eieren kan gaan kijken

[ Voor 23% gewijzigd door coenbijlsma op 21-12-2005 23:05 ]