Go Back   Shrimp Refuge Forums > Burgermannen > Hardware & Software > Design & Development

Reply
 
Thread Tools
Old 07-07-2008, 15:43   #1   link
Random
Shrimp Recidivist
 
Random's Avatar
 
Location: Gent
Go!

Een hele tijd geleden heb ik het boek Blondie24: Playing at the Edge of AI gelezen, waarin de auteur uitlegt hoe hij een AI-speler programmeert die zichzelf leert dammen (ik heb het hier op dit forum al eerder zitten spammen). Er is dus nooit een expliciete spelstrategie geprogrammeerd, de man liet de AI (een evoluerend neuraal netwerk met leercapaciteiten) gewoon enkele weken tegen zichzelf toernooitjes houden op een aftandse server en toen de onderzoeker de volgende keer met zijn creatie dammen speelde, is hij vakkundig ingemaakt en naar huis gestuurd. Overtroefd door zijn eigen losgeslagen creatie, als het ware. Ik heb zelden iets gelezen dat ik cooler vind dan dat, dus mijn voornemen om ooit zelf eens zoiets te schrijven dateert al vanaf de dag dat ik aan het boek begonnen ben en zie hier, van uitstel komt niet altijd afstel .

Om het enigszins doenbaar te maken om zo'n ding te programmeren heb je eigenlijk een bordspel nodig dat heel eenvoudige basisregels heeft die aanleiding geven tot een strategisch diepgaande gameplay. Onlangs ben ik de perfecte kandidaat hiervoor tegengekomen: het bordspel Go! Go is een oeroud Chinees spel dat je op 5 minuten kan leren, maar waar je jaren mee zoet bent als je het goed onder de knie wil hebben. Een heel eenvoudige tutorial kan hier gevonden worden, netjes vertaald naar het Nederlands door een KULaar. De basisregels zijn eigenlijk zo eenvoudig, dat ik ze gisterennamiddag op mijn gemakje volledig heb kunnen implementeren. Je kan de code die ik al heb hier downloaden. Het is een standaard Java-projectje, dus helemaal niet moeilijk om in gang te krijgen. Lees de readme.txt als je de code wil draaien en als je in je leven al ťťn keer een Java-programmaatje geschreven hebt, ben je er in een halve seconde mee weg. Momenteel zitten er drie tooltjes in:
Code:
  - run_testconsole is een command line console
    tool om de functies van de Go board engine uit
    te proberen. 

  - run_tournamenttest zet een eenvoudig Go-toernooi
    op tussen AI-spelers. Het aantal spelers, de bord-
    grootte, ... kan in de parameters in de .bat aangepast
    worden. 

    De enige AI-speler die momenteel geimplementeerd is, 
    voert gewoon zetten at random uit.

  - run_examplecode voert een voorbeeldapplicatie uit
    die het gebruik van de klasse engine/Board illustreert.
Waarom post ik dit hier? Gezien hier een boel IT'ers en IT-hobbyisten zitten, dacht ik dat er eventueel mensen zouden zitten die dit wel leuk of interessant zouden vinden. Het is een aangename manier om nieuwe dingen te leren, vind ik zelf. Dus als er mensen zijn die wel eens een eigen AI ineen willen knutselen en zien of mijn toekomstige er tegenop kan, go ahead (harhar). Of als je toch eens van plan was om deftig Java-GUI's te leren schrijven: het Go-board ook effectief zien zou wel tof zijn ('t is allemaal ASCII voor het ogenblik). Enthousiastelingen kunnen ook een clientinterface proberen maken om zelf tegen de AI of een andere speler te spelen om die oude Java-kennis weer wat op te frissen. Ook mensen die gewoon de code eens willen draaien of bekijken kunnen commentaar geven, natuurlijk.

Nog even benadrukken dat de code eigenlijk heel simpel in elkaar zit door een heel kort voorbeeldje van hoe de klasse kan gebruikt worden die ik momenteel al geschreven heb:
Code:
//7x7 Go-bord aanmaken
Board b = new Board(7);

//Geeft TileColour.Black terug (zwart begint)
TileColour currentPlayer = b.getTurn();
System.out.println("Current player is " + currentPlayer.name());
		  
//isLegalMove geeft hier true, het bord is nog leeg
if (b.isLegalMove(0,1)) System.out.println("(0,1) is a legal move for black");
		  
//Doe de zet, placeStone geeft true terug.
b.placeStone(0,1);
		  
//Wit aan zet
currentPlayer = b.getTurn();
System.out.println("Current player is " + currentPlayer.name());
		 
//Doe een zet
if (b.placeStone(0,0)) System.out.println("Stone placed at (0,0)");
		   
//Toon de huidige spelsituatie
System.out.println(b);
		 
//Zwart aan zet, illegal move attempt:
if (!b.placeStone(0,1)) System.out.println("Illegal move: " + b.getIllegalMoveMessage() + ", retrying...");
 
//Zwart nog steeds aan zet: 
if (b.placeStone(1,0)) System.out.println("Stone placed at (1,0)");
	 
//Toon de hele spelgeschiedenis
System.out.println(b.getRepresentation(7));

Output van de laatste regel (verloop van een spel van drie zetten):

== TURN 1 ==
   0  1  2  3  4  5  6
0  .  .  .  .  .  .  .
1  B  .  .  .  .  .  .
2  .  .  .  .  .  .  .
3  .  .  .  .  .  .  .
4  .  .  .  .  .  .  .
5  .  .  .  .  .  .  .
6  .  .  .  .  .  .  .

== TURN 2 ==
   0  1  2  3  4  5  6
0  W  .  .  .  .  .  .
1  B  .  .  .  .  .  .
2  .  .  .  .  .  .  .
3  .  .  .  .  .  .  .
4  .  .  .  .  .  .  .
5  .  .  .  .  .  .  .
6  .  .  .  .  .  .  .

== TURN 3 ==
   0  1  2  3  4  5  6
0  .  B  .  .  .  .  .
1  B  .  .  .  .  .  .
2  .  .  .  .  .  .  .
3  .  .  .  .  .  .  .
4  .  .  .  .  .  .  .
5  .  .  .  .  .  .  .
6  .  .  .  .  .  .  .
Dus als je helemaal niet veel programmeerervaring hebt, laat dat geen obstakel zijn om het eens uit te proberen als het je mocht interesseren.

Last edited by Random; 07-07-2008 at 15:56.
Random is offline   Reply With Quote
Old 09-07-2008, 21:25   #2   link
Wolf
Oh no
 
Wolf's Avatar
 
You so need a blog
__________________
If we must never take any chances, we should have nothing at all, for nothing is certain. óBlaise Pascal
Wolf is offline   Reply With Quote
Old 10-07-2008, 06:22   #3   link
ran
Senior Member
 
ran's Avatar
 
Location: Antares
Weet niet of ik snel tijd ga hebben om me er verder in te verdiepen, maar ik vind het in elk geval wel interessant...
__________________
It's extraordinary how we go through life with eyes half shut, with dull ears, with dormant thoughts. Perhaps it's just as well; and it may be that it is this very dullness that makes life to the incalculable majority so supportable and so welcome. Nevertheless, there can be but few of us who had never known one of these rare moments of awakening when we see, hear, understand ever so much ó everything ó in a flash ó before we fall back again into our agreeable somnolence.
ran is offline   Reply With Quote
Old 10-07-2008, 10:15   #4   link
Random
Shrimp Recidivist
 
Random's Avatar
 
Location: Gent
Ik heb intussen een (simpele) versie van een evoluerende AI-speler af die op een Go-bordje van 4x4 groot (standaardgrootte = 19x19) na een paar honderd generaties stabiliseert op een win rate van een whopping 57% tegen... een triviale tegenspeler die gewoon willekeurige zetten doet. Nog niet echt een wonderkind dus . Bij een bord van 5x5 zakt zijn winpercentage naar 55%... Als de code wat opgekuist is, zal ik ze nog eens uploaden.

Een standaardbenchmark is het laten evolueren van een XOR-netwerk (dus een netwerk dat de functie (f = x XOR y) leert). Mijn huidig algoritme ontdekt de XOR-functie gemiddeld in een honderdtal generaties, waar de netwerken in de literatuur het doen in een zestigtal. Dat vind ik al redelijk. Het probleem is dat je bij een onbekend probleem (de Go-speler) een heleboel designbeslissingen moet nemen waarover je eigenlijk in het duister tast (aantal layers in je neuraal netwerk, grootte van de layers, aantal individuen in je generaties, mutation & crossover rates, crossovermethode, ...). De keuze van die parameters bepaalt hoe snel je netwerk leert en hoe goed het uiteindelijk wordt. Bij een XOR-netwerk zijn de meeste designparameters van het (heel simpele) netwerk zelf gekend (het aantal layers en hun grootte), wat het een goede referentie maakt voor de kwaliteit van het evolutiealgoritme.

Volgende stap die ik zou willen nemen is nu een meta-evolutiealgoritme te implementeren dat niet de gewichten en biases in de neurale netwerken instelt (da's hetgeen dat het huidig algoritme doet), maar zoveel mogelijk van de onbekende designparameters die nu afhankelijk zijn van trial & error. Ik heb een artikel gevonden waar men zelfs nog verder gaat en een meta-meta-evolutie implementeert (het algoritme die de meta-evolutie uitvoert, heeft immers ook dergelijke onbekende designparameters). Maar misschien maak ik eerst wat functies die een betere monitoring toelaten, ik zal zien waar ik de meeste goesting in heb .
Random is offline   Reply With Quote
Old 10-07-2008, 11:15   #5   link
Karel
Senior Member
 
Karel's Avatar
 
Interessant probleem, heel gerelateerd aan mijn onderzoeksdomein (surrogaatmodelleren). Welke inputs gebruik je voor je neurale netwerk? Want die zijn op zich nog veel belangrijker dan de topologie van het netwerk. Een volledige configuratie van het spelbord, gedefinieerd als 16 discrete inputs {niks, zwart, wit}? Of iets anders?
Karel is offline   Reply With Quote
Old 10-07-2008, 11:50   #6   link
Random
Shrimp Recidivist
 
Random's Avatar
 
Location: Gent
Je hebt gelijk dat de input (en het formaat ervan) ook van cruciaal belang is, ik zat er ook net aan te denken.
Code:
public TilePosition calculateNextMove(Board currentGameState) {

	//Indices for general use
	int i=0, j=0;
	
	//Fill input vector of the neural net with
	//the current game state
	TileColour tc;
	for (i=boardSize-1; i>=0; i--) for (j=boardSize-1; j>=0; j--) {
		tc = currentGameState.getTileColour(i, j);
		input[i*boardSize+j] = 
			(tc == TileColour.Vacant ? 0 :
			(tc == currentGameState.getTurn() ? 1 : -1));
	}
	
	//Scores of the legal moves
	//The move with the highest score will be selected
	double currentScore;
	double highestScore;
	TilePosition highestScorePosition;
	
	//First of all, evaluate the current game state.
	//If the highest score is assigned to the current
	//state, the player will pass its turn by returning 
	//null as function value.
	highestScore = gnn.process(input)[0];
	highestScorePosition = null;
	
	//Get all legal moves and assign scores
	ArrayList<TilePosition> legalMoves = currentGameState.getLegalMoves();
	
	for (TilePosition tp : legalMoves) {
		
		//Simulate move right in the 
		//NN input vector
		i=tp.getX()*boardSize+tp.getY();
		input[i] = 1;
		
		//Calculate the score using the neural net
		currentScore = gnn.process(input)[0];
		
		//Update highest score if necessary
		if (currentScore >= highestScore) {
			highestScore = currentScore;
			highestScorePosition = tp;
		}
		
		//Undo the move
		input[i] = 0;
		
	}
	
	//Return the move with the highest score
	moveCount++;
	return highestScorePosition;
	
}
Dit is de basiscode momenteel, ik was er juist aan bezig. De game engine geeft de speler een lijst van alle mogelijke zetten die hij kan uitvoeren. Het netwerk kent aan elk van deze mogelijke zetten een score toe tussen 0 en 1, waarbij de input inderdaad de volledige toestand van het spelbord is (dus net nadat de potentiŽle zet gedaan is). De mogelijke waarden per positie op het bord zijn (-1, 0 en 1) voor resp. (kleur tegenstander, leeg en eigen kleur).

Er is nu wel een complicatie die ik wellicht te simplistisch heb opgevat, dat ga ik eens veranderen. Om de performantie te verbeteren, laat ik momenteel de potentiŽle zetten niet volledig uitwerken. Ik bedoel daarmee dat ik de stenen zonder vrijheidsgraden niet van het bord verwijder voordat ik de potentiŽle zet doorgeef aan het netwerk. Stel b.v. dat het huidige spelbord als volgt is (op een 3x3-bord, wit aan de beurt):
Code:
. W .
W B W
. . .
De winnende zet is hier dus de volgende:
Code:
. W .
W B W
. W .
Omdat dit herleidt tot
Code:
. W .
W . W
. W .
Waarna Black geen zetten meer kan doen. Ik geef momenteel de tweede toestand door aan het netwerk, waar de steen van Black nog niet verwijderd is. In principe zijn de tweede en derde toestand natuurlijk equivalent omdat de ene rechtstreeks volgt uit de andere, maar ik zie nu in dat het veel eenvoudiger is voor het netwerk om de derde toestand te quoteren dan de tweede omdat daar minder inzicht voor vereist is. Voor de laatste toestand zou b.v. een simpele optelling van de inputwaarden een heel ruwe spelstratgie kunnen vormen terwijl dit voor de 2e toestand niet het geval is.
Ik ga dat dus eens veranderen. Plus ook toelaten dat de speler zijn beurt past, daar was ik net aan bezig. De bovenstaande code is zojuist al aangepast, maar het probleem is momenteel dat een spel niet noodzakelijk meer eindig is als je toelaat dat de spelers kunnen passen (beiden kunnen gewoon altijd passen). Nu ben ik aan het twijfelen, ofwel bouw ik een limiet in op het aantal beurten per spel, waarbij een gelijkspel wordt verklaard als die limiet overschreden wordt, ofwel voeg ik een regel toe dat de tweede speler verliest als er twee keer na elkaar gepast wordt. De eerste oplossing is degene die Fogel ook gebruikt heeft bij Blondie24, maar bij Go wordt het in praktijk eigenlijk expliciet niet zo gedaan (twee spelers passen slechts wanneer er zonder discussie kan overeengekomen worden wie wint). Bij de tweede oplossing moet de game state uitgebreid worden met een code die aanduidt of er de vorige beurt gepast is. Ik denk dat ik daarvoor ga gaan.
Random is offline   Reply With Quote
Old 10-07-2008, 13:25   #7   link
Karel
Senior Member
 
Karel's Avatar
 
Je vergeet iets essentieel. Door gewoon de input als een lijst van discrete waarden te geven, verlies je informatie over de structuur van het bord, die totaal essentieel is voor een efficiŽnt leeralgoritme. Natuurlijk kan het algoritme die structuur aan zichzelf "leren" door ervaring, maar dat gaat serieus ten koste van uw performantie, want het algoritme moet eerst leren dat vakje x naast y ligt, VOOR het kan beginnen leren welke moves goed zijn.

Er zijn technieken waarbij je de banden tussen euclidisch dicht bij elkaar liggende "vakjes" versterkt in het neuraal netwerk, omdat die logischerwijs ook meer gerelateerd zijn. Maar da's complexe materie, en dan ga je wel een soort van voorkennis inbouwen, en misschien wil je echt een volledig blind lerend algoritme?

Last edited by Karel; 10-07-2008 at 13:28.
Karel is offline   Reply With Quote
Old 10-07-2008, 13:49   #8   link
Random
Shrimp Recidivist
 
Random's Avatar
 
Location: Gent
Quote:
Originally Posted by Karel View Post
Er zijn technieken waarbij je de banden tussen euclidisch dicht bij elkaar liggende "vakjes" versterkt in het neuraal netwerk, omdat die logischerwijs ook meer gerelateerd zijn. Maar da's complexe materie, en dan ga je wel een soort van voorkennis inbouwen, en misschien wil je echt een volledig blind lerend algoritme?
Wel, inderdaad, daar zeg je het. Eigenlijk geef je dan voorkennis mee en ik zal dat wel doen als ik niet verder geraak anders, maar ik zou liever eerst wat andere zaken uitproberen. Voor hele kleine bordjes moet het volgens mij wel mogelijk zijn om een goed algoritme te trainen zonder dat je het netwerk bij wijze van spreken de pap in mond geeft (bij grotere borden is dat misschien een beetje te flagrant wishful thinking ). De verschillende layers zijn volledig geconnecteerd momenteel, dus in principe is het netwerk in staat om zelf de gewichten zodanig in te stellen dat b.v. aangrenzende posities zwaardere gewichten krijgen.

Fogel gebruikt een methode waarbij hij alle combinaties van mogelijke vierkanten op het spelbord als input gebruikt. Bij een 3x3-bord b.v., zou hij 9 inputs genereren voor elk vakje (vierkant van 1x1) + 4 inputs voor de 4 verschillende 2x2-vierkanten (uitgemiddelde waarde over de 4 vakjes van elk 2x2-bord, als ik mij goed herinner) + 1 input voor het 3x3-bord zelf. Maar een dambord is natuurlijk wel kleiner dan een 19x19 Go-bord en het aantal combinaties wordt dan al gauw erg groot.

Weet je de naam nog van de technieken waarover je spreekt? Ik zou wel eens willen weten hoe het anders nog gedaan wordt.
Random is offline   Reply With Quote
Old 10-07-2008, 13:54   #9   link
Karel
Senior Member
 
Karel's Avatar
 
Ik zal er eens naar zoeken, ik denk dat ik het ergens in een paper tegengekomen ben, maar vraag me niet welke .
Karel is offline   Reply With Quote
Reply

  Shrimp Refuge Forums > Burgermannen > Hardware & Software > Design & Development

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT +1. The time now is 03:38.


Powered by vBulletin® Version 3.7.3
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.