Blog

Willem van Dam

finish(Tic Tac Toe vs Prolog)

Jaja, we gaan het verhaal afronden! We hebben een winnaar! Tic Tac Toe kan officieel gespeeld worden tegen Prolog! Allereerst wil ik even vertellen waarom dit bericht zo laat is. Ik heb in de tussentijd corona gehad en zijn mijn opa en oma aangereden. Ze maken het goed. Mijn hoofd stond er even niet naar om een bericht te schrijven, maar ik was wel verder gegaan met het programma. Oja en WordPress is troep, want in de tussentijd is deze website meer dan 5 keer gehacked geweest. Ook kregen alle blog berichten meer dan 100 Russische reacties en dat verwijderen is een drama.. Maar goed, het is gelukt!

Het idee

Ik heb bedacht om de Prolog werkend te krijgen in C# WPF. Hierin is een opzet gemaakt om boter kaas en eieren te spelen tegen Prolog. Allereerst is de basis gemaakt. In het WPF project is gebruik gemaakt van MVVM. Omdat ik de Prolog logica appart wil hebben van het programma is voor deze een Handler gemaakt. Zie hieronder een afbeelding van het uiterlijk van het spel. Zodra het spel wordt opgestart wordt de speler gevraagd welk karakter hij wilt gebruiken in het spel.

Tic Tac Toe vs Prolog

De Nuget package

Prolog kan op verschillende manieren gebruikt worden in een C# project, twee manieren hiervan zijn de command line en een Nuget package. Command line heeft als groot nadeel dat het niet geïntegreerd is in het programma, dus deze viel af. Nu heeft SWI Prolog ook een C# interface enkel is de documentatie van deze niet te bereiken, noch de website van de ontwikkelaar. Nu moest dus een andere implementatie van Prolog gebruikt worden.

Tijdens het zoeken kwam CSharpProlog naar boven. Deze is uiteindelijk gebruikt, omdat deze duidelijke voorbeelden heeft en geschikt is voor .NET Core. Dit was ook de meest recent bijgewerkte Nuget package van een Prolog implementatie.

De oefening

Natuurlijk heb ik geen ervaring met CSharpProlog. Nu was voor mij ook nog niet duidelijk wat voor resultaat deze zou terug geven. Om concreet te krijgen welke data het spel moet doorgeven aan de Prolog handler en wat CSharpProlog als input kan verwachten zijn tests geschreven, zie code hieronder voor een voorbeeld.

[Test]
public void GetPrologListShouldBeListWithLastX()
{
    const string prologDashList = "[A1,A2,A3,B1,B2,B3,C1,C2,'X']";
    _ticTacToe.Board["C3"] = "X";
    Assert.AreEqual(_ticTacToe.GetPrologList(), prologDashList);
}

De methode _ticTacToe.GetPrologList() geeft een lijst terug zoals de prologDashList is. Deze kijkt naar het bord en vult de lege posities met de positienamen beginnend met een hoofdletter. In Prolog wordt dit gezien als een variabele en Prolog gaat dan kijken wat mogelijk de waarde kan zijn van de variabele. Waarom ik geen tests heb geschreven voor de uiteindelijke werking vraag ik me nog steeds af, maar al debuggend is het in elkaar gezet.

Prolog in C#

De Tic Tac Toe handler is het bestand waar de Prolog query’s worden uitgevoerd en waar de data wordt omgezet naar data waar we wat mee kunnen. Er zijn twee methodes in Tic Tac Toe handler die het werk doen, namelijk GetAllPossibilities en GetWinner. Bij GetAllPossibilities wordt gebruik gemaakt van tic_tac_toe_v3.pl en bij GetWinner wordt gebruik gemaakt van een licht aangepaste versie van tic_tac_toe_v2.pl, deze hoeft namelijk geen string meer te printen met daarin de winnaar.

private static IEnumerable<Solution> GetV3Solutions(string list)
{
    Prolog.Instance.Engine.Reset();
    Prolog.Instance.Engine.Consult($@"{Directory.GetCurrentDirectory()}\Resources\tic_tac_toe_v3.pl");

    return Prolog.Instance.Engine.GetAllSolutions(null, $"win({list}).").NextSolution;
}

In de bovenstaande code wordt weergegeven hoe de oplossingen voor GetAllPossibilities worden opgevraagd van Prolog. Allereerst voert hij een reset uit, aangezien hij anders v2 en v3 tegelijk kan inladen, wat voor foutmeldingen zorgt, aangezien ze beide functies hebben met dezelfde namen. Nadat hij de engine een reset heeft gegeven gaat hij de v3 inladen bij Prolog, hierna vraagt hij alle oplossingen op van Prolog en geeft deze terug als lijst.

Wat Prolog precies terug geeft

GetAllPossibilities gaat op basis van de oplossingen verder en geeft daarna een lijst terug met alle mogelijke winst plekken voor beide karakters. In de afbeelding hieronder is te zien wat Prolog als oplossingen terug geeft voor de volgende query:

win(['X','O',A3,
      B1,'X',B3,
      C1,C2,C3]).

In het 6e resultaat staat het volgende:
A3 (namedvar) = C3
B1 (namedvar) = B1

B3 (namedvar) = C3
C1 (namedvar) = C1
C2 (namedvar) = C2
C3 (namedvar) = C3

Dit laat zien dat als A3 dezelfde waarde heeft als C3 en B3 ook dezelfde waarde als C3, waarbij C3 toevallig ook die waarde heeft dat het een winst scenario is. Dit levert voor ons programma niks op, dus gaan we deze eruit filteren en geven we een lijst terug met informatie waar we wat mee kunnen.

Hoe de data wordt vervormt

In GetAllPossibilities is een foreach loop die de data voor ons om zet in bruikbare data. Deze staat hieronder weergegeven.

foreach (var solution in solutions)
{
    var possibility = new List<string>();
    Atom key = null;
    foreach (var solutionVariable in solution.NextVariable)
    {
        var gameCharacter =
            possibilities.Keys.FirstOrDefault(x => $"'{x.Value}'" == solutionVariable.Value);
        if (gameCharacter == null) continue;

        key = gameCharacter;
        possibility.Add(solutionVariable.Name);
    }

    if (possibility.Count > 0 && key != null) possibilities[key].Add(possibility);
}

Deze foreach gaat langs alle oplossingen. Per oplossing kijkt hij naar de regels die worden terug gegeven, de oplossing variabelen, dit zijn de A1, A2, etc. Bij deze variabelen wordt gekeken of deze een karakter bevat. Als deze een karakter bevat, als deze een karakter bevat wordt deze opgeslagen als de key. De variabelen waar het karakter kan staan worden toegevoegd aan de mogelijkheden en deze worden dan toegevoegd aan de volledige lijst met mogelijkheden voor het betreffende karakter. Zie hieronder hoe dit er uit ziet voor X voor de hiervoor genoemde query.

Mogelijkheden X

Wat we met deze informatie doen

Prolog heeft nu nog niet zijn zet gemaakt in Tic Tac Toe vs Prolog, maar we weten wel wat de beste plekken zijn voor beide karakters. In de methode GetComputerPositionRequest van de Tic Tac Toe klasse maken we aan de hand van deze mogelijke plekken de eind beslissing voor Prolog op welke plek hij moet gaan staan. Zie de code hieronder.

public string GetComputerPositionRequest(GameCharacters gameCharacters)
{
    var possibilities = TicTacToeHandler.GetAllPossibilities(gameCharacters.AsList(), GetPrologList());

    var bestPosition = TicTacToeHandler.GetBestWinPosition(gameCharacters.Computer, possibilities);
    if (bestPosition != null) return bestPosition;

    var bestEnemyPosition = TicTacToeHandler.GetBestWinPosition(gameCharacters.Player, possibilities);
    if (bestEnemyPosition != null) return bestEnemyPosition;

    return possibilities[gameCharacters.Computer].Count == 0
        ? Board.First(x => x.Value == string.Empty).Key
        : TicTacToeHandler.GetBestPosition(gameCharacters.Computer, possibilities);
}

Allereerst willen we alle mogelijkheden hebben, daarna kijken we wat de beste positie is waarna we direct gewonnen hebben. GetBestWinPosition geeft uit de lijst van alle mogelijkheden de mogelijkheid terug waar maar één variabele gebruikt wordt, want dan heb je gewonnen. Zie bijvoorbeeld index 1 van de afbeelding ‘Mogelijkheden X’. Hier wordt maar één variabele als mogelijkheid gegeven, dus dan geeft GetBestWinPosition deze terug.

Als de computer deze positie niet heeft, dan gaat hij kijken of de speler wel zo een positie heeft, als dit zo is plaatst Prolog zijn karakter daar. Zo verdedigd hij zichzelf. Na deze verdediging gaat de computer op de eerst lege plek staan op het bord of op de best volgende plek. De best volgende plek is één van de posities die in een mogelijkheid zijn waar twee variabelen worden terug gegeven. Zie bijvoorbeeld index 0 van de afbeelding ‘Mogelijkheden X’. Als X op beide posities gaat staan heeft deze gewonnen, maar daarvoor moet hij eerst op één gaan staan, aangezien je niet op twee plekken in één keer mag gaan staan.

Het resultaat

Ik hoop dat ik jullie wat geleerd heb van Prolog en hoe dit kan werken in C#. Het resultaat wat ik heb neer gezet ben ik zeer tevreden over, want ik kan nu eindelijk zeggen dat ik een spel heb gemaakt waarbij je tegen de computer kan spelen. Ook ben ik blij met de kennismaking met Prolog. Deze heeft mij een andere manier van programmeren laten zien, wat je niet moet vergeten. Niet alles moet OO zijn.

Het programma en de source zijn hieronder te downloaden.

Bedankt.
Willem van Dam.
– Weet hoe Prolog werkt.
– Game developer.
– AI ontwikkelaar.

Willem van Dam

Prolog het werk laten doen

De vorige uitwerking liet niet de kracht van Prolog zien. Wel hebben we verschillende technieken gebruikt die in Prolog zitten, zoals lists en recursie. Zie voor de vorige uitwerking het vorige blog bericht, ticTacToeWinner.

We kunnen ook het programma zo schrijven, zodat we Prolog het werk laten doen. Deze zegt dan of ‘x’ of ‘o’ op de gegeven positie geplaatst moet worden om te kunnen winnen. Zo kunnen we zoeken naar de plek waarme we winnen of waar we de tegenstander moeten blokeren. Om dit voor elkaar te krijgen gaan we meer de manier van Prolog gebruiken, namelijk regels en feiten.

De uitwerking

win(X, X, X).
winRow([X1, X2, X3|Tail]):- win(X1, X2, X3); winRow(Tail).
winCross([ 
    X, _, _,
    _, X, _,
    _, _, X]).
winCross([ 
    _, _, X,
    _, X, _,
    X, _, _]).
winColumn([ 
    X, _, _,
    X, _, _,
    X, _, _]).
winColumn([ 
    _, X, _,
    _, X, _,
    _, X, _]).
winColumn([ 
    _, _, X,
    _, _, X,
    _, _, X]).

win(X):- winRow(X); winCross(X); winColumn(X).

/** <examples>

?- win([
  x, -, o,
  o, x, o,
  x, -, X
  ]).
*/

Download het bestand.

In de bovenstaande uitwerking zijn de regels en de feiten te zien van het nieuwe programma. Het is belangrijk in dit geval om geen anonieme variabelen te gebruiken bij het aanroepen van de win met de list als parameter. Als de o rechtsboven vervangen wordt door een anonieme variabel, de _, dan is de uitkomst nog steeds dat X ‘o’ en ‘x’ kan zijn.

?- win([
  x, -, _,
  o, x, o,
  x, -, X
  ]).

X = x
X = o

?- win([
  x, -, -,
  o, x, o,
  x, -, X
  ]).

X = x

Dit komt doordat Prolog ‘x’ en de ‘o’ kan samenvoegen met de anonieme variabel. Dit kan natuurlijk niet tegelijk, maar om een succes scenario te krijgen kan Prolog de anonieme variabel samenvoegen met ‘o’. Als Prolog deze variabel namelijk samenvoegt met ‘o’, dan kan ‘o’ ook worden toegewezen aan de variabel X en dan voldoet hij aan de onderstaande regel.

winColumn([ 
    _, _, X,
    _, _, X,
    _, _, X]).

Door gebruik te maken van een ‘-‘ gebeurd dit niet, omdat ‘-‘ een atom is die kan worden toegewezen aan een variabel, maar niet van waarde veranderd kan worden.

Wat kunnen we met dit programma?

Dit programma kunnen we gebruiken als voorspeller. Zie de onderstaande situatie. Hier is het de beurt van ‘o’. Deze wilt niet verliezen. We zouden Prolog iedere open plaats af kunnen laten gaan om te kijken waar ‘o’ een plaats kan innemen om te winnen en welke plaats ‘o’ kan innemen om verlies tegen te gaan.

?- win([
  x, -, -,
  o, x, o,
  -, -, X
  ]).

X = x

Nu weet ‘o’ dat als hij deze plek niet inneemt dat ‘x’ de volgende ronde kan winnen. Als het de beurt van ‘x’ zou zijn, dan zou deze nu weten dat als hij deze plaats inneemt dat hij zal winnen. Het programma kan niet zeggen wat de beste plaats zal zijn om in te nemen als er nog niemand kan winnen.

Willem van Dam

ticTacToeWinner

Nu ik de eerste vier hoofdstukken van het boek heb gelezen, heb ik een programma geschreven waar Prolog de winnaar van TicTacToe kan vinden. Het programma laat een klein beetje van de functionaliteiten van Prolog zien.

Zoals eerder gezegd in mijn eerste blog bericht wil ik een AI maken voor Boter Kaas en Eieren (TicTacToe). Dit is het begin. Met dit programma ben ik met Prolog aan het oefenen. Dit programma kan namelijk niet iets voorspellen. Hij kan enkel zeggen wie er gewonnen heeft, als er iemand gewonnen heeft. Het programma ziet er als volgt uit:

winner(X):- format('Winner is ~s', X).
win(X1, X2, X3):- X1 == X2, X2 == X3, winner(X1).
winRow([X1, X2, X3|Tail]):- win(X1, X2, X3); winRow(Tail).
winCross([ 
    X1, _, X4,
    _, X2, _,
    X5, _, X3]):- win(X1, X2, X3); win(X4, X2, X5).

win(X):- winRow(X); winCross(X).

whoWins:- win([
  x, _, _,
  o, x, o,
  x, _, o
  ]).

/** <examples>

?- whoWins.
*/

Download het bestand.

De werking

Het programma heeft een structure whoWins, welke de complex structure win/1 aanroept. Deze geeft de gegeven array door aan de winRow/1 en winCross/1 complex structures. winCross/1 kijkt of ‘x’ of ‘o’ in een kruis gewonnen heeft, dus van links boven naar rechts onder of van rechts boven naar links onder.

Bij winRow/1 wordt recursie gebruikt. Aangezien de items van links naar rechts in een list zitten weten we dat steeds 1 tot 3, 4 tot 6 en 7 tot 9 rijen zijn. Door steeds de eerste drie items van de list te gebruiken en de tail weer door te geven wordt de list door drie gedeeld. Steeds bij deze drie items kijkt hij of een winnaar is in de rij, door de items door te geven aan win/3.

win/1 is de simpelste structure. Deze kijkt enkel of de drie gegeven variabelen hetzelfde zijn, als dit zo is geeft hij de variabel door aan winner/1. Deze structure print tekst waarin staat wie de winnaar is.

Opdracht

Om ook anderen te helpen met het leren van Prolog heb ik een kleine opdracht bedacht. Het programma mist nog een stukje functionaliteit. Dit is het herkennen van een rij van boven naar beneden. Dit kan op meerdere manieren worden opgelost. Download het programma hieronder waar een oplossing in is verwerkt. Succes!

Download het bestand.

Willem van Dam

alternative(Book)

Het boek, Learn Prolog Now!, is een zeer interessant boek met veel informatie. Ik geloof dat niet alle informatie voor mij is weggelegd. De stof vind ik soms wat taai namelijk. Het is duidelijk beschreven, maar het mag van mij wel wat simpeler. Kijk bijvoorbeeld naar hoofdstuk 2, Unification and Proof Search. Dit is een belangrijk hoofdstuk in het boek, omdat het je leert hoe Prolog werkt. Bij het kopje ‘The occurs check’ gaan ze in op het unification algoritme van Prolog. Ze gebruiken bij ‘The occurs check’ de volgende query:

?-  father(X)  =  X. 

Het boek gebruikt meer dan 10 alinea’s en meer dan 1200 woorden om uit te leggen dat een gemiddeld algoritme zegt dat dit niet wordt samengevoegd, omdat X niet gelijk is aan father(X). Prolog doet dit anders. Door de onderstaande regel zegt Prolog dat deze twee wel samengevoegd worden, want de linkerhand is een term en de rechterhand is een variable. Wat Prolog doet is father(X) toewijzen aan X, maar in father(X) zit een X. Nu heeft Prolog zojuist father(X) aan de X toegewezen, waardoor Prolog weet dat het eigenlijk father(father(X)) is, maar deze heeft weer een X. Prolog gaat hier steeds mee door. Hoe Prolog hier mee doorgaat of wat het precies terug geeft ligt aan de versie en de implementatie van Prolog.

If term1 is a variable and term2 is any type of term, then term1 and term2 unify, and term1 is instantiated to term2 . Similarly, if term2 is a variable and term1 is any type of term, then term1 and term2 unify, and term2 is instantiated to term1 . (So if they are both variables, they’re both instantiated to each other, and we say that they share values.)

Ik geloof dat het boek dit ook korter had kunnen doen. Hiervoor zal ik enkel de eerste vier hoofdstukken van het boek lezen. Deze geven mij, verwacht ik, de nodige basis informatie. Om Prolog in zijn werking te zien heb ik een video bekeken van Derek Banas, zie https://www.youtube.com/watch?v=qgjjlZdGet8 voor de video. De video geeft niet veel uitleg over Prolog, maar laat voor een groot gedeelte zien wat er in Prolog zit. Waar ik achter kwam is dat ik Lists nog verder moet onderzoeken.

Ik zou adviseren om het boek tot hoofdstuk 4 te lezen en dan te gaan oefenen met Prolog. Het boek geeft veel informatie, waarbij soms maar een klein gedeelte nodig is. Dit advies is ook de manier waarop ik het nu ga doen. We zullen zien of dit een handige manier was om Prolog te leren. Hier kom ik nog op terug!

Willem van Dam

learningLanguage(Willem, Prolog).

Voor de course van APP van mijn opleiding is één van de opdrachten het jezelf aanleren van een nieuwe programmeertaal. Een uitdaging en een vooruitzicht. Het leren van nieuwe technieken en deze proberen toe te passen vind ik altijd wel interessant. De programmeertaal heeft wel een aantal eisen, zoals dat het een volledig ander paradigma moet zijn. De taal die ik gekozen heb is Prolog. Deze taal is logisch. Prolog is een afkorting van “Programming with logic”. De enige talen waar ik momenteel ervaring mee heb zijn voornamelijk object georiënteerd.

Prolog is een afkorting van “Programming with logic”.

Waarom Prolog?

De keuze voor Prolog was voor mij vrij snel gemaakt. Dit alles heeft namelijk een doel. Het behalen van de opdracht. Dit doe ik door het leren van de programmeertaal, het maken van een programmeeruitdaging en dit delen door middel van deze blog. Naar andere talen heb ik ook gekeken, maar ik kon niet direct bedenken wat voor een uitdaging ik zou kunnen maken.

Bij het kennis maken van Prolog had ik direct een tweetal ideeën in mijn hoofd. Prolog is namelijk goed voor AI. Je stelt namelijk een vraag aan Prolog en deze geeft dan het antwoord. Om het antwoord te krijgen moeten wel wat regels etc. worden opgesteld, hier komen we nog op terug. De eerste potentiële uitdaging is maken van een AI voor het spel boter, kaas en eieren. Als dit niet voldoende uitdaging heeft dan zou ik een AI voor een ander spel willen maken. Een andere potentiële uitdaging is het maken van een AI die een Rubiks kubus kan oplossen, enkel weet ik niet of dit mogelijk is of te complex is.

Om te taal te leren moet kennis worden opgedaan, dat is logisch. Om dit te doen maak ik gebruik van de digitale versie van het boek ‘Learn Prolog Now!’ van Patrick Blackburn, Johan Bos, and Kristina Striegnitz. Deze is te vinden op http://www.learnprolognow.org. Momenteel heb ik hoofdstuk 1 van het boek doorgenomen en de opdrachten hiervan uitgevoerd. Ik had wat onzekerheden bij het nakijken van mijn antwoorden, dus heb ik de antwoorden van Peter Urbak gebruikt om mijzelf te controleren. Deze zijn te vinden op https://github.com/dragonwasrobot/learn-prolog-now-exercises. Alle fouten die ik bij mezelf heb ontdekt heb ik duidelijk benoemd, om zo te weten waar ik op moet letten.

Wat viel op?

Prolog is een totaal andere taal dan ik gewend ben. De syntax is volledig anders, de manier van denken moet anders en het is een enorm interessante taal. Bij de meeste talen beschrijven we regels aan de hand van vergelijkingen. Bij Prolog geven we een collectie van feiten en regels. Daarna stellen we een vraag aan Prolog en deze gaat opzoek naar een antwoord. Voor mij is dit een uitdaging om een andere manier van denken aan te leren.

happy(yolanda).
listens2Music(mia).
listens2Music(yolanda):-  happy(yolanda).
playsAirGuitar(mia):-  listens2Music(mia).
playsAirGuitar(yolanda):-  listens2Music(yolanda). 

Hierboven staat een Prolog programma. Dit zijn dus een set regels en feiten. Bij het voor het eerst zien van dit programma snapte ik niet wat er stond, totdat ik begreep dat ‘:-‘ een if statement is. De if van Prolog werkt net andersom dan de if in de meeste talen. De left hand side van de :- is de head en de right hand side van de :- is de body. Als de body waar is dan is de head waar. Het wordt leesbaar door :- te vervangen door if.

listens2Music(yolanda) if happy(yolanda).

Aan dit Prolog programma kunnen we bijvoorbeeld vragen wie er allemaal luchtgitaar spelen. Dit doen we door de volgende query uit te voeren: ‘playsAirGuitar(X)’. X is het variabel waar het antwoord aan wordt toegewezen. Variabelen worden aangegeven door woorden die beginnen met een hoofdletter of beginnen met een underscore, zoals _x.

Zoals te zien in de bovenstaande afbeelding speelt Mia luchtgitaar. Omdat er meer mensen zijn die luchtgitaar spelen kunnen we ook op next drukken. Dit zal in dit geval Yolanda zijn. Het bijzondere aan dit vind ik dat Prolog zelf kan uitzoeken wie luchtgitaar spelen.

Het laatste dat ik wil laten zien van Prolog is het omzetten van tekst naar een programma. Opdracht 1.4 van het boek is zo een opdracht. Hier worden de volgende regels gegeven:

  1. Butch is a killer.
  2. Mia and Marsellus are married.
  3. Zed is dead.
  4. Marsellus kills everyone who gives Mia a footmassage.
  5. Mia loves everyone who is a good dancer.
  6. Jules eats anything that is nutritious or tasty.

Deze regels moeten omgezet worden naar een Prolog programma, welke er dan als volgt uit ziet.

killer(butch).
married(mia,marsellus).
dead(zed).
kills(marsellus, X):- footmassage(X, mia).
loves(mia, X):- goodDancer(X).
eats(jules, X):- nutritious(X); tasty(X).

Tot nu toe vind ik Prolog een geweldige taal om te leren. Ook heb ik enorm veel zin om de rest van de taal te leren en dit te delen. Hoe het gaat uitpakken in de programmeeruitdaging zie ik nog niet voor me. Wil je deze taal ook leren? Begin met het boek Learn Prolog Now!.