# Vier op een Rij AI: Hoe denkt de computer? ## 1. Het Virtuele Bord De computer ziet geen gekleurde schijfjes op een bord. Voor de computer is het bord een tabel met cijfers: - **0** = Lege plek - **1** = Gele schijf - **2** = Rode schijf Het bord heeft 7 kolommen en 6 rijen. Na elke zet controleert de computer alle richtingen (horizontaal, verticaal en schuin) om te kijken of iemand vier op een rij heeft. --- ## 2. Wat is een "Ply"? Een **ply** is één zet van een speler. Als de AI op ply 6 staat, kijkt hij 6 zetten vooruit. Omdat spelers om de beurt spelen, betekent ply 6 dat de AI 3 van zijn eigen zetten en 3 zetten van de tegenstander bedenkt. Meer plies = slimmere zetten, maar het duurt langer om te berekenen. Op de ESP32-C3 is ply 4 bijna meteen klaar, ply 6 duurt ongeveer een seconde, en ply 8-10 kan enkele seconden duren. Terwijl de AI nadenkt, zie je een knipperend lichtje. --- ## 3. De Minimax Strategie ### Het basisidee Stel je voor dat je Vier op een Rij speelt tegen een vriend. Voordat je je schijfje laat vallen, denk je: "Als ik mijn schijfje hier leg, wat doet mijn vriend dan? En wat doe ik daarna?" Dat is precies wat de computer doet, alleen kijkt hij naar **alle** mogelijke zetten, niet alleen een paar. ### Twee spelers, twee doelen De AI noemt de twee spelers **Max** (de computer zelf) en **Min** (jij): - **Max** wil de hoogste score (de computer wint). - **Min** wil de laagste score (jij wint). De AI gaat ervan uit dat jij altijd je beste zet doet. Hij hoopt niet dat jij een fout maakt. ### Een eenvoudig voorbeeld Stel je voor dat er nog maar 3 kolommen over zijn en de AI kijkt 2 zetten vooruit. Hij maakt een soort boom: ```text Beurt van de AI (Max - kiest de hoogste score) / | \\ kolom 2 kolom 3 kolom 4 / \\ / \\ / \\ Jouw beurt (Min - kiest de laagste score) ... ... ... ... ... ... +5 -3 +2 +8 -1 +4 ``` 1. Na kolom 2: jij zou de laagste score kiezen (-3). 2. Na kolom 3: jij zou de laagste score kiezen (+2). 3. Na kolom 4: jij zou de laagste score kiezen (-1). De AI kiest dan de kolom met de hoogste score die overblijft, in dit geval kolom 3 (+2). ### Scoren: Hoe de AI een Bord Waardeert Na het doorspelen van een "wat als?"-scenario, moet de AI beslissen: is dit een goed of slecht resultaat? Hij gebruikt een gelaagd scoringsysteem: - **+1000 of meer: "Ik win!"** De AI heeft een manier gevonden om vier op een rij te krijgen. Hoe sneller hij kan winnen, hoe hoger de score. Winnen in 2 zetten scoort hoger dan winnen in 6 zetten. Daarom gaat de AI altijd voor de snelste overwinning. - **-1000 of minder: "Ik verlies!"** De tegenstander krijgt vier op een rij. Hoe sneller hij verliest, hoe slechter de score. Dit zorgt ervoor dat de AI het hardst vecht tegen zetten die dreigen tot een direct verlies. - **Heuristiek-score: "Ik weet het nog niet, maar ik kan zien hoe goed het eruitziet."** Als de AI zo ver vooruit heeft gekeken als hij kon (door zijn plies heen) en niemand heeft gewonnen, beoordeelt hij de positie met een heuristiek — een snelle schatting van wie er sterker voor staat. ### De Heuristiek: Het Bord Lezen In plaats van elke onbesliste positie "neutraal" te noemen, bekijkt de AI elke mogelijke groep van vier opeenvolgende cellen op het bord (horizontaal, verticaal en beide diagonalen — 69 groepen in totaal). Voor elke groep telt hij de schijfjes: - **3 AI-schijfjes + 1 leeg (speelbaar):** De lege cel kan nu meteen gevuld worden (hij zit op de onderste rij of er zit een schijfje onder). Dit is een directe dreiging. Score: **+100**. - **3 AI-schijfjes + 1 leeg (nog niet speelbaar):** De lege cel zweeft in de lucht — de dreiging bestaat maar kan nog niet benut worden. Score: **+40**. - **2 AI-schijfjes + 2 leeg:** Een veelbelovende opbouw die zich tot een dreiging kan ontwikkelen. Score: **+5**. - **3 tegenstander-schijfjes + 1 leeg (speelbaar):** Een direct gevaar. Score: **-100**. - **3 tegenstander-schijfjes + 1 leeg (nog niet speelbaar):** Een toekomstig gevaar. Score: **-40**. - **2 tegenstander-schijfjes + 2 leeg:** De tegenstander bouwt iets op. Score: **-5**. - **Gemengde groepen** (beide spelers hebben schijfjes in dezelfde groep): Geblokkeerd — niemand kan hier winnen. Score: **0**. Daarbovenop gebruikt de AI twee extra scorebonussen: - **Controle over de middelste kolom:** +3 per AI-schijfje in de middelste kolom, -3 per tegenstander-schijfje. De middelste kolom is betrokken bij meer winnende lijnen dan elke andere kolom, dus het beheersen ervan is waardevol. - **Vorkdetectie:** Als een speler **twee of meer** drie-op-een-rij dreigingen tegelijk heeft, is dat een vork — de tegenstander kan er maar één per beurt blokkeren, dus de andere wint het spel. De AI geeft een grote bonus (**+200** of **-200**) wanneer hij een vork detecteert, waardoor hij agressief vork-opstellingen najaagt en wanhopig probeert te voorkomen dat de tegenstander er een maakt. Al deze scores tellen bij elkaar op. De maximale heuristiek-score ligt ruim onder 1000, dus het verstoort nooit de echte winst/verlies-detectie — een gegarandeerde winst wint altijd van de beste heuristiek-positie. Deze heuristiek betekent dat de AI nu het verschil kan zien tussen een sterke positie (veel dreigingen in opbouw, vooral speelbare) en een zwakke (de tegenstander heeft alle dreigingen), zelfs als hij geen gedwongen winst of verlies kan zien binnen zijn zoekdiepte. ### Waarom de middelste kolom belangrijk is De AI controleert altijd eerst de middelste kolom (kolom 3), en werkt dan naar buiten toe (2, 4, 1, 5, 0, 6). De middelste kolom is betrokken bij meer mogelijke winnende lijnen dan de randen, dus door deze eerst te controleren, vindt de AI sneller goede zetten en kan hij slechte zetten eerder overslaan (dankzij alpha-beta snoeien). De heuristiek geeft ook een kleine bonus voor controle over het midden, wat dit natuurlijke voordeel versterkt. --- ## 4. Alpha-Beta Snoeien: De Slimme Snelweg ### Het probleem Acht plies vooruit kijken in Vier op een Rij betekent miljoenen bordposities verkennen. Zelfs een snelle microcontroller kan ze niet allemaal in een redelijke tijd controleren. ### De oplossing **Alpha-Beta pruning** is een manier om takken van de boom over te slaan die de uiteindelijke beslissing niet kunnen veranderen. _"to prune" betekent snoeien of snijden_ Stel je voor dat je een verjaardagscadeau koopt. Je gaat naar Winkel A en vindt een leuk speelgoed voor 10 euro. Dan ga je naar Winkel B. Het eerste artikel dat je ziet, kost 15 euro, en je merkt dat alles in Winkel B nog duurder is. Je hoeft niet elk artikel in Winkel B te controleren — je weet al dat Winkel A beter is. Je verlaat Winkel B en bespaart tijd. De AI doet hetzelfde: - **Alpha** is de beste score die de AI (Max) tot nu toe heeft gevonden. Denk hierbij aan: "Ik weet al dat ik ten minste dit goed kan doen." - **Beta** is de beste score die de tegenstander (Min) tot nu toe heeft gevonden. Denk hierbij aan: "De tegenstander weet al dat hij mij tot hoogstens dit kan beperken." Wanneer de AI een tak verkent en ontdekt dat de score nooit beter kan worden dan wat hij al heeft (beta <= alpha), **snijdt** hij (snijdt hij af) die hele tak. Hij slaat alle overgebleven zetten in die tak over, omdat ze het resultaat niet kunnen veranderen. ### Hoeveel helpt het? In de praktijk laat snoeien de AI 50-90% van de posities overslaan die hij anders zou moeten controleren. Daarom is de volgorde van de kolommen belangrijk — de AI controleert eerst de middelste kolom (kolom 3) en werkt dan naar buiten toe. Goede zetten zitten vaak in het midden, dus door deze eerst te controleren, leidt dat tot betere snoeiing en een snellere zoektocht. --- ## 5. De Drie Fases van de AI De AI doet zijn werk in drie stappen: 1. **Kan ik nu winnen?** De AI controleert **alle** kolommen op een winnende zet. Als hij ergens vier op een rij kan maken, doet hij dat meteen. Geen verdere berekeningen nodig. Belangrijk: de AI controleert eerst elke kolom op eigen winst voordat hij naar dreigingen kijkt — zo blokkeert hij nooit per ongeluk een dreiging van de tegenstander als hij zelf het spel kan winnen. 2. **Kan de tegenstander volgende beurt winnen?** Pas nadat is bevestigd dat er geen directe winst is, controleert de AI alle kolommen op dreigingen van de tegenstander. Als jij ergens vier op een rij kunt maken, blokkeert hij die kolom. Dit overslaan zou een grote fout zijn. 3. **Diepe zoektocht.** Als er geen directe winst of bedreiging is, voert de AI de volledige minimax-strategie uit met alpha-beta snoeien en de heuristiek-evaluatie. Deze drie stappen maken de AI zowel snel (directe reacties op duidelijke zetten) als slim (diep nadenken als het nodig is). --- ## 6. Demo-modus: Verschillende Vaardigheden In de demo-modus spelen twee AI's tegen elkaar. Om het spannend te maken (in plaats van altijd gelijkspel), krijgt elke speler willekeurig een andere diepte toegekend. De ene speler kijkt bijvoorbeeld 5 zetten vooruit, de andere maar 3. De sterkere speler kan zo winnende zetten vinden die de zwakkere mist. Wie sterker is, wordt elke keer willekeurig bepaald. --- ## 7. Blunder-modus Normaal speelt de AI altijd de beste zet die hij kan vinden. Maar dat kan frustrerend zijn voor jongere of minder ervaren spelers die nooit winnen. De **blunder-modus** geeft de AI een instelbare kans (bijvoorbeeld 20%) om een willekeurige zet te doen in plaats van diep na te denken. Als er een blunder gebeurt, slaat de AI zijn slimme analyse over en laat hij een schijfje in een willekeurige open kolom vallen. De rest van de tijd speelt hij gewoon op volle kracht — maar af en toe maakt hij een domme fout die een oplettende speler kan afstraffen. Blunders gaan nooit boven een directe winst of blokkade. Als de AI nu kan winnen, of als de tegenstander op het punt staat te winnen, maakt de AI altijd de juiste zet. Blunders vervangen alleen de diepe zoektocht op beurten waar er geen directe dreiging is. --- ## 8. Snelle Bediening De ESP32-C3 heeft maar één kern. Als de AI nadenkt, kan hij de bediening een paar seconden blokkeren. Twee trucs zorgen ervoor dat het spel soepel blijft: 1. **Knopcontrole tijdens het zoeken:** Tijdens het nadenken controleert de AI af en toe of je op de knop hebt gedrukt. Zo ja, stopt hij meteen met nadenken. 2. **Stopvlag:** Een wereldwijde vlag (`abortAi`) zorgt ervoor dat het nadenken meteen stopt als je op de knop drukt. Binnen microseconden stopt de hele berekening. --- ## Meer Weten? - [Vier op een Rij - Wiskundige Oplossing (Wikipedia)](https://nl.wikipedia.org/wiki/Vier_op_een_rij) - [Minimax Algorithme (Wikipedia)](https://nl.wikipedia.org/wiki/Minimax) - [Alpha-Beta Pruning (Wikipedia)](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)