download
match5		 Match 5, een zelflerend spel

Inleiding

Match5 is een bordspelletje.
Het kan op twee manieren worden gespeeld
    1. speler tegen computer
    2. speler tegen speler
De computer is zelflerend.
Bij verlies wordt de bordstand plus noodzakelijke aktie bewaard om niet opnieuw op deze manier te verliezen.

Installatie

Match5 is geschreven voor Windows. De programmeertaal is Delphi.
Download match5 door op het download (bliksem) icoontje bovenaan de pagina te klikken.
Er is geen installatieprocedure.
Kopieer match5 simpelweg naar een map.

Bestanden

Tijdens spelen tegen de computer wordt een lijst gemaakt met foutpatronen, de zg. "kennis" tabel.
De speler kan deze tabel op disk bewaren.
De naam van dit kennisbestand op disk is altijd de spelersnaam met de extensie .fivo
Zonder andere opgave wordt een kennisbestand opgeslagen in de map match5data,
die automatisch wordt gemaakt in dezelfde map als waarin het programma match5.exe staat.
Bij het opslaan van de kennis wordt ook de speler toegevoegd aan de Hall-of-Fame.
Dit bestand staat in dezelfde map als het kennisbestand.

Het spel

Het bord bestaat uit 9 x 9 vakjes.
In een vakje kan een blauwe of een rode bal worden geplaatst.
De computer speelt altijd met rood, de speler met blauw.
De spelers plaatsen om beurten een bal van hun kleur.
Winnaar is degene die als eerste 5 ballen van zijn kleur horizontaal, vertikaal of diagonaal op een rij zet.
Bekijk eens het plaatje hieronder, waar de computer met rood speelt en de speler met blauw.
Duidelijk is, dat de computer (nog) over weinig kennis beschikt en simpelweg door blauw wordt verslagen.

Het spel openen vanuit een .fivo bestand.

Klik op het .fivo bestand.
Windows vraagt de eerste keer met welke applicatie geopend moet worden.
Geef dan het match5.exe bestand op.
De kennisbestanden tonen daarna het match5 icoontje.

Spelen tegen de computer

De computer bouwt al verliezend een kennisbestand op en dit bestand kan de volgende status hebben:
    nieuw....... een nieuw kennisbestand wordt opgebouwd in het geheugen van de computer
    eigenaar.... een eigen (eerder opgeslagen) kennisbestand is geopend (geen password of password OK)
    gebruiker...het kennisbestand van een andere speler is geopend (password onbekend)
Een nieuw bestand kan met of zonder password worden opgeslagen.
Het password is niet verplicht.
Een kennisbestand kan alleen worden gewijzigd als het password klopt dwz. de speler is de eigenaar.
Een blanco password klopt altijd, zodat elke andere speler het kennisbestand kan uitbreiden met zijn spel,
of zelfs kan verwijderen.

Het level

Bij een spel hoort natuurlijk een vorm van beloning.
Die beloning is het behaalde level en dat is weer gelijk aan het aantal opgeslagen foutpatronen.
Dat is ruwweg gelijk aan het aantal keren dat van de computer is gewonnen.
Ook is er een Hall_of_Fame met ruimte voor de beste 100 spelers.

De Bediening

De start / stop knop rechtsonder schakelt tussen de menu en de spel modus van het programma.
In de menu-modus kan
    - een naam worden opgegeven
    - een password worden opgegeven
    - gekozen worden tussen "speler - computer" of "speler - speler"
    - opgeslagen foutpatronen worden bekeken met de knoppen |< < > >|
    - alle kennis worden verwijderd met de knop X alle
    - het getoonde foutpatroon worden verwijderd met de knop X 1
    - een nieuw kennisbestand worden geopend met de openen knop
    - kennis van het spel worden opgeslagen op disk met de knop bewaren
    - help / informatie worden getoond met de knop help
    - de Ere - Galerij worden bekenen
Met het keuzevakje mutaties tonen aangevinkt, wordt elke verandering van het kennisbestand getoond.

Een kennisbestand op disk kan worden gewist door
    - het kennisbestand te laden als eigenaar (password blank of OK)
    - met de X alle knop alle data in de computer te wissen
    - op de knop bewaren te drukken
Bij het opslaan van de foutpatronen op disk wordt ook de Hall-of-Fame bijgewerkt.
Is de kennis gewist, dan wordt de naam uit de Hall-of-Fame verwijderd.

Revisies

Match5 beleeft momenteel revisie 1.2
De eerste versie was 1.0
Aan 1.1 zijn de knoppen voor het wissen van de kennisdata toegevoegd, evenals de keuze om mutaties te tonen.
Ook is de map match5data ingevoerd om verschillende mappen te krijgen voor programma en data.
In 1.2 is een foutje verbeterd, dat sporadisch abussievelijk een kennispatroon wiste.

Het zelflerend Algoritme

Het algoritme is zeer simpel gehouden.
De computer speelt met opzet defensief, het voornaamste doel is niet te verliezen.

Het enige dat de computer kan constateren is winst of verlies, dwz. 5 ballen van dezelfde kleur op een rij.
De computer kijkt nooit vooruit (nog niet één zet), maar kan alleen eerder gemaakte fouten vermijden.

Het begint er dus mee, dat de computer 5 blauwe ballen op een rij ziet staan : een verloren spel.

Gedurende het spel worden gedane zetten bewaard in een tabel (geheten "movetable").
Als nu een patroon van 5 blauwe ballen optreedt, dan verwijdert de computer de laatste blauwe zet
zodat het patroon wordt: 
    BBBB0
B is een blauwe bal en 0 is een leeg veld.
Als bij volgende spelletjes dit BBBB0 patroon wordt gevonden, dan moet de computer reageren
met een rode bal in het lege veld.
Dan ziet het spel er zo uit: 
    BBBBR
Welke informatie moeten we bewaren?
De afmetingen van het patroon, inclusief alle blauwe en lege velden en ook het lege veld waar
het antwoord moet komen.
Dit lege veld coderen we als X.
Zodoende wordt het opgeslagen foutpatroon: 
    BBBBX
wat betekent: als er een patroon van 4 blauwe ballen met een leeg veld erachter optreedt,
dan moet de computer antwoorden met een rode bal in dat lege veld.

De foutpatronen worden linksboven uitgelijnd opgeslagen.
Bij het vergelijken met bordstanden worden verschuivingen en acht symmetrieën toegepast.
Over de symmetrieën later meer.

Bekijk nu het volgende spel.
Blauw probeert op dezelfde manier als eerst te winnen, maar de computer herkent het patroon
BBBB0 en reageert BBBBR.
Maar dan plaatst blauw een bal links van de rij en wint opnieuw (BBBBBR). 
    BBBBBR
Net als eerst verwijdert de computer de laatste blauwe bal, want die veroorzaakte het verlies.
Echter, de oorzaak van het verlies ligt dieper omdat de vorige rode zet niet vrijwillig was maar geforceerd,
om verlies te voorkomen.
Een geforceerde zet wordt apart gecodeerd in de movetable en ook deze zet wordt weggehaald,
samen met de voorafgaande blauwe zet.
Het foutpatroon ziet er nu zo uit: 
    0BBB00
Het laatst verwijderde blauwe veld is de plaats om rood te plaatsen en verlies te verwijden.
Dit is het opgeslagen foutpatroon: 
    0BBBX0
wat betekent: als een rij 3 blauwe ballen bevat met een leeg veld aan de ene en twee lege velden
aan de andere kant dan moet de computer een rode bal plaatsen in het X gemerkte veld.

Dit is het hele algoritme.
Bij verlies de laatste blauwe zet weghalen en in geval van een voorgaande gedwongen rode zet
ook die zet met weer de blauwe zet daarvoor.
Het X (focus) veld is het veld van de laatst verwijderde blauwe bal.

Hieronder staat een voorbeeld van een iets ingewikkelder situatie.
Wat rode ballen zijn weggelaten, de blauwe zijn meer van belang.
Neem aan, dat de computer deze foutpatronen al kent: BBBBX en 0BBBX0 
    0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0
0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0
0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0
0 0 0 B B 0 0 0 0   0 0 B B B 0 0 0 0   0 0 B B B R 0 0 0   0 0 B B B R 0 0 0
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   
0 0 0 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   
0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   
0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   
0 0 B B B R 0 0 0   0 0 B B B 0 0 0 0   
0 0 B 0 0 0 0 0 0   0 0 B 0 0 0 0 0 0   
0 0 R 0 0 0 0 0 0   0 0 R 0 0 0 0 0 0   
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0   
0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0
Lees de bordstanden hierboven van links naar rechts en van boven naar onder.
Na de eerste blauwe zet zijn er twee 0BBBX0 foutpatronen, een horizontaal en een vertikaal.
De computer reageert met R en elimineert dus de dreiging van verlies in horizontale richting.
Dan maakt blauw een rijtje van 4 in vertikale richting.
De computer herkent het foutpatroon en plaatst een R onderaan dit rijtje.
Dan wint blauw door een bal bovenaan het vertikale rijtje te plaatsen.

Het verloren spel herkenned, verwijdert de computer de laatste B en de voorafgaande R's ,
die immers gedwongen waren en ook de B's voor die R's.
Het laatst verwijderde B veld wordt gecodeerd als X.
Het foutpatroon dat aan de Knowledge tabel wordt toegevoegd is (linksboven uitgelijnd) 
       0
   B
   B
   X B B 0
   0
   0

Symmetrie

Bij het zoeken naar foute bordstanden worden 8 symmetrieën toegepast.
Zie hiervoor de tabellen hieronder: 
     R R R R 0 0 0 0 0
 B 0 0 0 0 0 0 0 0
 B 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 
     0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 R B B 0 0 0 0 0 0
 
     0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 B
 0 0 0 0 0 0 0 0 B
 0 0 0 0 0 R R R R
 
     0 0 0 0 0 0 B B R
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
    symmetrie -0- symmetrie -1- symmetrie -2- symmetrie -3- 


     0 0 0 0 0 R R R R 
 0 0 0 0 0 0 0 0 B
 0 0 0 0 0 0 0 0 B
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 
     0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 0 0 R
 0 0 0 0 0 0 B B R
 
     0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 B 0 0 0 0 0 0 0 0
 B 0 0 0 0 0 0 0 0
 R R R R 0 0 0 0 0
 
     R B B 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 R 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0
    symmetrie -4- symmetrie -5- symmetrie -6- symmetrie -7-
Symmetrie -0- is het originele patroon. (de kleuren dienen alleen om de symmetrie te demonstreren)
Symmetrie -1- tot -3- is het resultaat van rotatie met 90, 180 en 270 graden om het midden.
Symmetrie -4- tot -7- ontstaat door symmetrie -0- tot -3- te spiegelen om een vertikale lijn door het midden.

Opmerking 1:
Patronen worden in de linkerbovenhoek uitgelijnd.

Opmerking 2:
Bij het zoeken naar foutpatronen wordt naast symmetrie ook een x en y offset toegepast.
Het patroon wordt over het gehele bord verplaatst.

Opmerking 3:
Diagonale patronen staan los van de horizontale en vertikale.
Ze zijn dus geen symmetrie van elkaar.
Als de computer heeft geleerd dat 0BBBX0 een foutpatroon is, dan weet hij (nog) niet dat 
    0  
  B 
    B  
      B  
        X 
          0
ook een foutpatroon is.

Data structuren

"game", "comp" en "EP" zijn tweedimensionale arrays met afmeting 9 * 9.
Game bevat het spel met de rode en blauwe velden.
Wissen geeft alle 81 velden de waarde 0.
De velden kunnen als waarde hebben:
    0 : leeg
    1 : rood
    2 : blauw
Comp en EP bevatten foutpatronen.
De velden van EP en comp zijn gecodeerd:
    0 : leeg
    1 : rood
    2 : blauw
    3 : doet niet mee
Comp ontvangt een foutpatroon van de KN (knowledge) tabel.
De inhoud van comp wordt vergeleken met game om een foutpatroon te herkennen.

Tijdens een spel wordt het foutpatroon opgebouwd in EP.
Als de computer een spel verliest, dan wordt EP opgeslagen in KN.
EP wordt gewist door alle velden de waarde 3 te geven.

De movetable registreert alle rode en blauwe zetten.

Geassocieerd met game, comp en EP zijn de records gameRect, compRect en EPrect, van het type TEPrect 
type TEPrect = record
                full  : boolean; //active area
                x1,y1 : byte;    //left top
                x2,y2 : byte;    //right bottom
                fx,fy : byte;    //focus (x,y) winner, stopper
                level : byte;
                white : byte;    //number of white fields
                red   : byte;    //          red
                blue  : byte;    //          blue
		   end;
Hun betekenis is:
    full : true als de rectangle een patroon bevat (een rechthoek kan namelijk niet op nul gezet worden)
    x1,y1,x2,y2 : left-top en right-bottom van het foutpatroon
    fx,fy : de coördinaten van het X veld (focus)
    level : uitleg volgt
    white, red, blue : aantal velden van elke kleur, tbv snel zoeken van foutpatronen

Entries in de movetable zijn van type TMove 
    TMove = record
         x : byte;   //coordinate of game field
         y : byte;
         movetype : byte; //0:none; 1:red; 2:blue; 3:red stopper
        end;
Opmerking:
movetype 3 is een gedwongen zet (van de computer).
Het is een zet in het X veld.

Foutpatronen en bijbehorende data worden verpakt in array KN.
KN is een ééndimensionaal array van het type DWORD (= cardinal).
Een DWORD bevat een rij van 9 velden, dus 9 DWORDS zijn nodig per foutpatroon.
Een veld heeft 2 bits van het DWORD nodig.
Bits 0,1 bevatten veld 0 van een rij, bits 2,3 veld 1, enzovoorts.
Bits 0..17 bevatten een rij velden, bits 18..23 zijn ongebruikt.
De upper bits 24..31 van elk DWORD bevatten deze informatie:
    row 0 - x2
    row 1 - y2
    row 2 - fx
    row 3 - fy
    row 4 - level
    row 5 - white
    row 6 - red
    row 7- blue
    row 8 - none
opmerking:
- x1,y1 zijn altijd 0, dus hoeven niet bewaard te worden
- fx,fy zijn de coördinaten van het X veld
- white,red,blue zijn het aantal velden van die kleur
- entry n in KN houdt in KN[9*(n-1)]....KN[9*(n-1) + 8]

Game levels

Zoals eerder uitgelegd is het level van de speler het aantal opgeslagen foutpatronen.
In de KN tabel staat ook een level.
Dat level is het aantal verwijderde blauwe zetten na winst van de speler.
Dus , BBBBX is een patroon met level 1.
0BBBX0 is een patroon met level 2.
In de KN tabel worden de foutpatronen van laag naar hoog level gesorteerd.
Dit zorgt er voor dat eerst op de simpele patronen wordt getest.

Ontstaan van het foutpatroon.

Fout patronen worden tijdens en spel opgebouwd in array EP.
Aan het begin van een spel wordt elk veld in EP op 3 gezet, wat betekent dat het niet meedoet.
De vlag -full- wordt false gemaakt omdat er geen patroon aktief is.

EP wordt in drie gevallen veranderd.
1.
Als blauw wint.
De winnende 5 velden worden in EP op de waarde 2 (blauw) gezet.
2.
Als de computer een geforceerde zet heeft gedaan.
Zo'n zet is het gevolg van een compare tussen het foutpatroon in Comp en het spel in array Game.
In dit geval wordt het patroon in Comp gekopieerd naar EP.
Een veld in de comp rechthoek dat ongelijk is aan 3, wordt gekopieerd naar het overeenkomstige
veld in EP.
3.
Na een niet gedwongen zet van de computer wordt het EP array gewist. (velden worden op 3 gezet)

Als de computer een spel heeft verloren, dan wordt het patroon in EP bijgewerkt
met informatie uit de movetable (blauwe en rode geforceerde zetten verwijderd) zoals hiervoor uitgelegd.
Het EP patroon wordt dan verpakt in KN voor gebruik in de volgende spelletjes en ondertussen
is de computer weer iets slimmer geworden.

Hoe de computer een spel kan winnen

De opgeslagen foutpatronen voorkomen dat de computer verliest, maar bevatten automatisch ook
informatie hoe de computer kan winnen.
Als een foutpatroon (dat uit blauwe ballen bestaat) in het spel voorkomt in rood, dan zal een rode zet
in het X veld leiden tot winst.
De compare functie is hierop ingericht: die test of het foutpatroon voorkomt in alleen blauw of alleen rood,
dus test niet op een kleur maar op gelijke kleur.
Een resultaatcode 0,1,or 2 geeft aan of geen (0), een rood (1) of een blauw (2) patroon werd herkend.
Op deze manier gebruikt de computer de opgeslagen foutinformatie ook om te kunnen winnen.

Verwijderen van opgeslagen troep

De computer zal nooit slimmer worden dan de speler.
Het is mogelijk de computer slecht te instrueren, wat de opslag van flauwekul tot gevolg heeft.
Maar er is een simpele manier om later van die onzin af te komen.
Elk nieuw foutpatroon in KN wordt namelijk meteen vergeleken met alle andere foutpatronen.
Als het nieuwe patroon onderdeel is van een oud patroon, wat wil zeggen:
    - een 0 in het nieuwe is ook een 0 in het oude
    - een 2 in het nieuwe is ook een 2 in het oude patroon
dan wordt het oude patroon uit KN verwijderd (en daalt het spelersniveau met 1).
Als het verwijderde (oude) patroon een hoger level had dan het nieuwe, dan is troep verwijderd.

Een voorbeeld:
Stel dat de computer alleen foutpatroon BBBBX kent.
Bekijk nu dit spel met de computer aan zet: 
    0 0 0 0 0 0 0 0 0
B B B B 0 0 0 0 0
0 B 0 0 0 0 0 0 0
0 0 B 0 0 0 0 0 0
0 0 0 B 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

    0 0 0 0 0 0 0 0 0
B B B B R 0 0 0 0
0 B 0 0 0 0 0 0 0
0 0 B 0 0 0 0 0 0
0 0 0 B 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

    0 0 0 0 0 0 0 0 0
B B B B R 0 0 0 0
0 B 0 0 0 0 0 0 0
0 0 B 0 0 0 0 0 0
0 0 0 B 0 0 0 0 0
0 0 0 0 B 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
De EP data opgeslagen in KN wordt (level 2) 
    B B B X 0
  B
    B
      B
        0
Als nu in een later spel patroon 
    B
  B
    B
      B
        X
wordt gevonden (level 1), wat een onderdeel is van het vorige patroon, dan wordt dit oude patroon verwijderd
omdat het overbodig is.

In de praktijk heb ik nog niet gezien, dat een nieuw foutpatroon een lager level eruit werkte.
Bij het bekijken van de foutpatronen is allerlei regelmaat en structuur te zien.
Hier is stellig nog ruimte voor verdere studie.
Nieuwe inzichten kunnen zich aandienen.

Intelligentie

Hoe "slim" kan de computer worden?
Op het eerste gezicht zou men zeggen: "niet slimmer dan de speler" , want diens gedrag wordt gekopieerd.
Ik denk dat dat onjuist is. De computer kan veel slimmer worden dan de speler.
Een slimme speler levert alleen een kortere leertijd van de computer op.
Bij slecht, onnadenkend spel zal namelijk de speler af en toe bij toeval toch winnen.
En elk verlies van de computer vergroot zijn kennis.
Zelfs als de tegenspeler van de computer volkomen willekeurig speelt, zal het level van de computer nog toenemen,
zij het langzaam.
Voor evolutie is geen hogere macht nodig.
Het gaat om geheugen (dna, schrift) , structuur en selectie.

Hiermee kom ik aan het einde van deze beschrijving van dit zelflerend spelletje.
Tot slot nog een snapshot van een foutpatroon (level 3)
Een punt geeft een leeg veld aan. Velden buiten de aktieve rechthoek zijn grijs gekleurd.

Veel plezier gewenst!

David Dirkse
nov. 2012