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.