Eventual consistency

Ik ga snel weer eens een blog schrijven zou ik lang geleden wel eens gezegd kunnen hebben. Dat zou dan inconsistent zijn met wat er hier op de site te zien is geweest.
Inconsistent zien we als een vies woord, het is een soort onwaarheid. Het ene zegt dit en het andere dat, er is er een die liegt!

In dit specifieke geval zou het meer een onverstandige belofte zijn, maar het had ook een technische reden kunnen hebben. Deze blog zou ik misschien een paar maanden geleden al geschreven kunnen hebben en vanwege een defecte communicatie nooit doorgekomen zijn. Wat je ziet is dan niet in sync met wat er geschreven is. Zou dat gebeurd zijn en de communicatie was hersteld dan zou je ineens een nieuwe blogpost met een datum ver in het verleden kunnen zien. Ziet er niet heel betrouwbaar uit, maar is in dit geval ook niet ernstig.

Dit soort situaties komen steeds vaker voor in systemen. Niet in de tijd van maanden zoals in dit (overigens zuiver hypothetische) voorbeeld, maar eerder in seconden of minuten. Dit heeft te maken met de meer gedistribueerde systemen die tegenwoordig ontwikkeld worden. De achtergrond zit hem in het zogenaamde ‘twee generaals probleem‘.
Het probleem is dat de generaals geen aanval kunnen coördineren als ze niet zeker zijn dat hun communicatie snel en volledig is. De generaals zijn in ons vakgebied computers en de communicatie loopt over een netwerk. Wil je zorgen dat alle betrokken systemen op elk punt in tijd hetzelfde laten zien dan is de consequentie wachten. Binnen een fysieke machine kan dat en dat is ook wat we gewend zijn te doen. Over een netwerk kan er verlies zijn en met gedistribueerde systemen als microservices kun je wel eens niet weten hoe vaak een stuk software waar draait.
Het gevolg is inconsistentie. Bah, ondanks de uitleg toch nog steeds niet leuk.

Je bent bijvoorbeeld een huisje aan het boeken voor de vakantie en even later blijkt dat de periode toch niet beschikbaar was. Van een systeem vinden we dit al snel een defect, maar in de buitenwereld speelt hetzelfde en zien we het als normaal. In een restaurant bestel je de dagschotel tonijn en even later komt de ober terug met de mededeling dat zojuist het laatste stuk tonijn gebruikt is en dat het toch iets anders uitzoeken wordt.

De vroegere systemen hadden als nadeel dat als het uitviel je niets had of je moest hele dure oplossingen voor failover en disaster recovery inrichten. Ook werd het heel snel heel duur als je op wilde schalen. Gedistribueerde systemen garanderen betere availability, maar er kunnen zogenaamde partitions ontstaan als er een een onderdeel niet bereikbaar is. Deze partitions zijn dan onderling niet meer consistent. We leveren dus consistentie in voor beschikbaarheid en in het kielzog daarbij winnen we snelheid en schaalbaarheid.

Om het voordeel te pakken en zo min mogelijk last te hebben van de consequenties is het zaak om gedistribueerde systemen slim op te zetten. Enerzijds vanuit de functionele hoek. Hoe ga je om met de verschillende inconsistente situaties? Hier is het zaak om zoveel mogelijk naar de buitenwereld te ontwerpen en vergelijkbare afhandelingen voor het systeem te bedenken.
Daarnaast moet de inconsistentie tijdelijk blijven, uiteindelijk moet alles weer kloppen. De oplossing daarvoor is werken met een patroon als ‘event sourcing’. Als je alle handelingen in de tijd wegschrijft in een centrale log dan is daaruit altijd weer te bepalen hoe elke situatie uitpakt ook al komt er iets te laat door. Zo kunnen de systemen op de achtergrond zelfherstellend zijn.
Stel je bijvoorbeeld de situatie van een bibliotheek voor. Je kunt in een database bijhouden welk boek aan wie uitgeleend is, maar als het terugbrengen eens niet goed verwerkt is blijft het boek uitgeleend staan. Als je het dan opnieuw uitleent staat de nieuwe klant geregistreerd bij het boek. Komt daarna de actie van het terugbrengen door dan kun je niet meer goed zien of het te laat ingeleverd is. Werken met een log als basis geeft je dan de mogelijkheid om elk punt in de tijd te reconstrueren en af te handelen.

De eigenlijke persistentie (opslag) ligt bij event sourcing niet meer zoals gebruikelijk in een database, maar in deze log. Dit levert weer andere voordelen. Dat is wellicht iets voor een andere keer, maar het kan even duren voor dat doorkomt.

Leren programmeren (de)coderen

Leren programmeren (de)coderen

Heb je weleens dat je iets tegen iemand wilt vertellen, maar dat je niet wilt dat iemand anders het hoort. Dan ben je absoluut niet de enige. De simpelste oplossing is zorgen dat niemand je kan horen, maar stel dat dat geen optie is. Je wilt nog steeds iemand anders iets vertellen, dus moet je een andere oplossing hebben. Mocht je nou je publiek kennen, dan kun je in een taal spreken die de rest van de aanwezigen niet kent, of zoals ouders bij jonge kinderen nog wel eens doen, het woord spellen. Om zeker te weten dat niemand anders de taal spreekt die jij en je buddy spreken, kan je codetaal gebruiken, een niet bestaande taal die je samen hebt afgesproken. In theorie kun je dan naar hartenlust kletsen zonder dat iemand anders je begrijpt. In theorie, want als je dat te lang doet waar een kind van ongeveer 2,5 bij is dan spreekt die voor je het weet dezelfde codetaal vloeiend.

Het internet bestaat uit talloze computers die constant met elkaar praten en een onbekend aantal mensen dat continu mee (probeert te) luisteren. Nou is dat niet zo erg als iemand dat doet terwijl je dit blog leest, immers lezen zij dan ook dit blog, dus dat is eigenlijk een win-win situatie. Maar als iemand met je meeleest tijdens het invoeren van je wachtwoord of bekijken van je mail, is dat een heel ander verhaal. Daarom wordt er steeds meer druk gezet door grote bedrijven als Google en Apple om verbindingen te versleutelen. Je zult het vast wel in de communicatie van bijvoorbeeld je bank hebben gehoord: “let op het groene slotje in je browser”. Het coderen en decoderen gaat vanzelf, je merkt daar verder dus niet zoveel van. Zo zijn dit en dit exact de zelfde pagina, op dezelfde server. Alleen is in het ene geval het verkeer versleuteld en in het andere niet.

Dat het soms wel handig is dat je communicatie niet zomaar afgeluisterd kan worden was voor dat het internet bestond ook al wel duidelijk. De Romeinse keizers moesten bijvoorbeeld wel eens bericht sturen naar de uiteindes van hun rijk. Dat ging in die tijd per bode. Als die berichten over troepenverplaatsingen gingen dan was het wel zo handig dat de Galliërs dat niet te weten kwamen. Maar de Galliërs waren ook niet gek, dus die probeerden zo’n bode te onderscheppen. Om te voorkomen dat de Galliërs iets met de brief konden, versleutelden de Romeinen hun teksten met een Caesarcijfer (de naamgeving is niet geheel toevallig). Een Caesarcijfer werkt als volgt. Je neemt een tekst en neemt voor alle letters een getal verderop in het alfabet. Bijvoorbeeld stel je hebt het woord: Orcado en je neemt een Caesarcijfer met 1 verplaatsing. De O wordt dan een P, de r een s, de c een d, de a een b, de d een e en de o weer een p. De versleutelde tekst is dan Psdbep. En als de generaal aan het front de tekst wilde lezen deed hij hetzelfde maar dan andersom. Een populaire versie hiervan is ROT13 dit is een Caesarcijfer met een verschuiving van 13, dit zorgt er voor dat coderen en decoderen hetzelfde resultaat geeft. Dit heeft heel lang prima gewerkt. Maar dit is niet een hele moeilijke versleuteling en als je het trucje kent is de tekst decoderen een kwestie van maximaal 25 keer proberen.

Daarom werd er een goede 1500 jaar later een iets ingewikkeldere versie bedacht, het Vigenèrecijfer. Het Vigenèrecijfer lijkt erg op het Caesarcijfer, het enige verschil is dat de sleutel langer is. In plaats van dat we voor elke letter dezelfde verschuiving in het alfabet gebruiken, wordt de verschuiving voor elke letter bepaald door een code woord. Laten we als voorbeeld opnieuw Orcado versleutelen maar nu met sleutel “blog”. De eerst letter is de o, de eerste letter van de sleutel is de b, dat is het tweede letter in het alfabet, daarom verschuiven we de o één plaats naar boven. Ja dat is een kleine instinker, we beginnen met tellen bij 0, dus je moet overal 1 van af halen. Maar de O wordt dus weer een P. De r wordt versleuteld met de l deze wordt dus 11 plaatsen verschoven, dan kom je 3 plaatsen voorbij de z dus beginnen we weer vooraan het alfabet en wordt het de letter c. De c versleutelen we met de o, dat wordt een q, de a met de g dat wordt een g. Nu zijn we aan het einde van de sleutel, maar we moeten nog cijfers versleutelen, daarom beginnen we de sleutel opnieuw, de d versleutelen we met de b, dat wordt een e en tot slot versleutelen we de o met de l en dat wordt een z. De versleutelde versie wordt dus Pcqgez. Dit was in de 16de eeuw toen dit cijfer bedacht is erg ingewikkeld om mee te werken, maar met computers is het maar 10 regels code en voor als je er mee wilt spelen heb ik die hier voor je geschreven. Om het lastiger te kraken te maken worden hoofdleters en spaties niet ondersteund.
Dat is een heel stuk moeilijker te kraken, want van de 25 opties die we eerst hadden, zijn het er nu heel veel meer. Maar als je een korte sleutel gebruikt en een tekst van een paar zinnen, dan is het nog wel te kraken, tenminste met een computer, met de hand is het niet te doen. Wat je namelijk kan doen is alle combinaties proberen en dan de computer laten kijken wat bij elke mogelijke sleutel de letterfrequentie is. De top 3 in het Nederlands is:
1. E 19,06%
2. N 9,91%
3. A 7,66%
Als je sleutel een tekst geeft waarbij deze letters ongeveer in deze frequenties voorkomen dan is er een grote kans dat dat de goede sleutel is. Je kunt ook nog extra statistische analyse doen op herhalingen en patronen in de versleutelde tekst om de lengte te kunnen schatten, maar als de sleutel onder de 10 karakters is kan een computer zonder probleem alle combinaties uitproberen van alle lengtes. Hoe langer je sleutel hoe veiliger het is, maar ook hoe moeilijker te onthouden. Een truc is om iets met meerdere codes te versleutelen. Als je zorgt dat de lengte van de sleutels priemgetallen (ik had het beloofd en hier zijn ze dan hoor) zijn, dan wordt je effectieve sleutel zolang als de lengtes keer elkaar. Als je een sleutel van 11 en eentje van 13 hebt dan wordt je effectieve sleutel 143 karakters lang. Dit werkt alleen met priem getallen, als je een sleutel hebt van 20 en een sleutel van 30 dan in je effectieve sleutel maar 60 karakters lang, immers is 60 mooi deelbaar door beide. De versleutelde tekst in het vorige blog is versleuteld met een Vigenèrecijfer en een code van minder dan 8 letters, dus mocht je het nog niet gekraakt hebben, maar zou je dat wel graag willen, heb je bij deze de informatie die je nodig hebt om dat alsnog te doen.

Computers gebruiken geen Vigenèrecijfer om de communicatie over het internet te versleutelen en dat is niet omdat het onveilig is. Er is namelijk een versie van het Vigenèrecijfer dat onkraakbaar is. Dit is het Vernamcijfer, een Vernamcijfer is een Vigenèrecijfer waarbij de sleutel minstens zolang is als de versleutelde tekst en de sleutel bestaat uit willekeurige letters. Immers als je de versleutelde tekst “abcdef” hebt kan dit “orcado” zijn met als sleutel “mkadbr”, maar ook “blogje” met sleutel “zqoxvb” of “decode” met sleutel “xxapbb”. Het zou in de context allemaal kunnen dus je hebt geen enkele mogelijkheid om uit te vinden welke de goede is. Nee de reden is praktisch, om dit soort versleuteling te gebruiken moeten zowel de zender als de ontvanger de sleutelcode weten. Jij en ik kunnen dat een keer als we bij elkaar zijn afspreken, maar computers op het internet hebben die luxe niet. Die moeten dat over het internet doen, maar dan kan iedereen meeluisteren. Want voordat je een sleutel hebt afgesproken is de communicatie onversleuteld. Een klassiek voorbeeld van een kip-ei-probleem. Gelukkig is daar een oplossing voor.
Voor internet communicatie wordt er gebruik gemaakt van asymmetrische versleuteling. Bij asymmetrische versleuteling heb je 2 sleutels, eentje om tekst te versleutelen en eentje om tekst te ontsleutelen. Die twee sleutels zijn een publieke en een geheime sleutel. Iedereen mag de publieke sleutel weten. De geheime sleutel weet alleen de eigenaar van de geheime sleutel. Iedereen die de publieke sleutel heeft kan nu een tekst versleutelen, de eigenaar van de geheime sleutel is de enige die dit kan ontsleutelen. Wat je nu kunt doen is dat je tegen een webpagina zegt: “hier dit is mijn publieke sleutel”. De webpagina verstuurt vervolgens alles naar je toe versleuteld met die sleutel en omdat jij de enige bent met de geheime sleutel kan niemand anders het lezen.
Het heeft ook nog een tweede voordeel. De webpagina kan namelijk ‘bewijzen’ dat hij echt de webpagina is die hij zegt te zijn. Dat doet hij door een stuk tekst van jouw keuze te versturen dat hij versleuteld heeft met zijn eigen geheime sleutel. Omdat het niet uitmaakt wat de versleutel sleutel en wat de ontsleutel sleutel is, kan je dat certificaat nu ontsleutelen met de publieke sleutel die je ook van de webpagina krijgt. Omdat de enige tekst die je kunt ontsleutelen met de publieke sleutel, tekst is die versleuteld is met de geheime sleutel die er bij hoort, weet je zeker dat de webpagina de eigenaar is van de geheime sleutel. Het enige wat je dan nog hoeft te doen is bij een instantie die certificaten uitgeeft navragen of die publieke sleutel bij die website hoort en je weet zeker dat je met de goede website praat.

Nu hoor ik je denken, “ok dat was crisis vaak het woord sleutel, maar ik heb het idee wel ongeveer begrepen, maar hoe werkt dat dan twee sleutels hoe kan je tekst met een sleutel versleutelen met een andere ontsleutelen?” Goede vraag, het antwoord is een stukje wiskunde met priemgetallen (daar zijn ze weer) en de modulo. Het gaat me iets te ver om uit te leggen hoe die wiskunde precies werkt als je het wilt weten kan je op RSA bingen er zijn genoeg sites die je dat kunnen uitleggen. Of als je niet van priemgetallen houdt kun je ook bingen op Elliptic-curve cryptography (ECC) maar ik kan je niet beloven dat de wiskunde er veel makkelijker van wordt. Wat ik wel zal doen is een getallenvoorbeeldje.
Stel je wilt het getal 12 versleuteld naar mij toe sturen. Ik geef je de publieke sleutel 3 en 55, wat jij doet om het bericht te versleutelen is (12^3)%55 dat is 12 tot de macht 3 en dat dan modulo 55. Dat geeft eerst 12^3 = 1728 en als we dat modulo 55 doen blijft er 23 over. We kunnen van die 23 met de twee sleutels die we hebben 3 en 55 niet meer terug naar 12 er is immers geen manier om te achterhalen hoe vaak ik 55 bij 23 moet optellen voordat ik de derde machtswortel er uit mag nemen. Ik heb echter de geheime sleutel die hier bij hoort, namelijk 27. Wat ik doe is (23^27)%55 en voila dat is 12.

Nou was het Vernamcijfer onkraakbaar, dat is bij vrijwel alle gangbare cijfers echter niet het geval, het vorige voorbeeld is een (versimpelde) vorm van RSA een van de meest gebruikte encryptie op het internet. Van RSA wisten de makers vanaf het begin al dat het te kraken was en hoe, de reden dat het toch nog veilig is, is omdat het kraken heel veel rekenkracht kost. Het getal 55 uit het voorbeeld is een vermenigvuldiging van 2 priemgetallen, als je er achter kan komen welke 2 priemgetallen kan je de geheime sleutel zo uitrekenen. In dit voorbeeld is dat heel goed te doen, degene onder jullie die vlug zijn met rekenen zullen al snel gezien hebben dat dat 5 en 11 zijn. Vanaf daar is het simpele wiskunde (namelijk (5-1)*(11-1) = 40, -39%40 = 1, -39/3 (de publieke sleutel) = -13 en -13%40 = 27. Voor meer uitleg moet je echt RSA even bingen. Bij 55 is dat goed te doen, maar voor RSA zijn dat zulke grote getallen dat het enorm veel rekenwerk is om die 2 priemgetallen te achterhalen en dus is het veilig. Als er ooit iemand iets slims bedenkt om snel die 2 priemgetallen te kunnen achterhalen is alle met RSA versleutelde data simpel te ontsleutelen.

Een alternatief voor asymmetrische versleuteling is een geheime sleuteluitwisseling. Ik heb net al heel wat wiskunde gedaan dus ik zal dit idee uitleggen met een analogie die daar vaker voor gebruikt wordt, verf. Stel je wilt een geheime kleur verf afspreken met elkaar terwijl iemand al je communicatie over de verf afluistert. Het voordeel dat je hebt is dat als je twee kleuren verf mengt dat het heel lastig is om vanuit de gemengde verf de oorspronkelijke kleuren te achterhalen. Stel je voor dat je een pot blauwe verf hebt en je wilt eigenlijk paarse verf. Je voegt er op gevoel rode verf bij tot je een mooie kleur paars hebt. Je verft je muur paars en bijna op het einde merk je dat je te weinig verf hebt. Gelukkig heb je nog een pot blauwe verf en je hebt de paarse verf als voorbeeld. Je weet alleen niet meer welke tint rode verf je gebruikt hebt en niet hoeveel. De klussers onder jullie hebben iets dergelijks mogelijk al een keer meegemaakt en zullen je verzekeren dat het schier onmogelijk is. Dat is doffe ellende voor je paarse muur, maar voor ons komt het goed uit. Wat je doet is je spreekt met de ander een basiskleur af, bijvoorbeeld 1 liter blauwe verf. Vervolgens voeg je allebei je in het geheim je eigen kleur toe. Jij doet rood en maakt het dus paars, de ander doet geel en maakt het dus groen. Vervolgens stuur je elkaar jullie nieuwe kleuren. Daar voeg je je eigen geheime kleur aan toe en je hebt allebei een paars-groene kleur die iedereen die jullie combinatie kent wel ongeveer kan nabootsen, maar net niet precies.

Hoewel het internet steeds meer leunt op versleuteling en je bij bijna elke website een groen slotje ziet, is het allemaal gebaseerd op versleuteling waarvan we weten dat het te kraken valt. Er is ook al een heel aantal standaarden dat we een paar jaar geleden nog gebruikten dat nu niet meer als veilig wordt beschouwd. Het is een gevecht tussen de rekenkracht aan de ene kant en het nog zwaarder te berekenen maken aan de andere kant. Wat in ieder geval niet veilig is, is het Vigenèrecijfer met een te korte sleutel. Heb jij het al gekraakt? Als je nog meer hulp nodig hebt, hier een opzetje. En als je nou de smaak te pakken hebt en ook een snel algoritme hebt bedacht om RSA of ECC te kraken, stuur me dan even een mailtje.

Leren programmeren optimaliseren

Leren programmeren optimaliseren

Als je weleens op je telefoon kijkt bij je apps welke wijzigingen er in al die updates zitten zie je meestal 3 dingen: bugfixes, tweaks en improvements. Bugfixes spreekt redelijk voor zich, er zaten kleine fouten in de software en die zijn er nu uit. Tweaks en improvements is echter wel erg vaag. Het zijn verbeteringen in de code, maar er was niks stuk. Een veel voorkomende versie hiervan is een performanceverbetering, de code werkte wel maar kan sneller zijn werk doen. Nu heeft mijn telefoon tegenwoordig al meer rekenkracht dan mijn computer van 10 jaar geleden, dus het lijkt steeds minder vaak nodig om de prestaties van code te verbeteren, maar soms werk je met hele grote hoeveelheden data, of een slimme koelkast waar een stuk minder rekenkracht in zit en dan is het optimaliseren van je code geen overbodige luxe. Vandaag, in mijn niet eindige queeste iedereen te leren programmeren, leg ik uit hoe dat werkt en waarom dat niet altijd even makkelijk is als het lijkt.

Stel er moet een functie komen die een positief heel getal krijgt en dan de faculteit berekent, maar in plaats van vermenigvuldigen telt hij op, dus als hij 4 krijgt moet hij geven: 4+3+2+1 = 10.
Dat zou je op de volgende manier kunnen doen:

var y = function(getal) { 
  if (getal == 1) 
    return 1 else return getal + y(getal - 1)
}

 

(Wacht dit voelt als plagiaat, alhoewel ik kopieer het wel letterlijk, maar het is uit mijn eigen blog “leren controleren” is het dan nog steeds plagiaat? Nou ja doet er ook niet toe)
En stel: je wilt deze bewerking heel vaak doen met een groot getal, (ik weet, dit is allemaal wel heel erg gestaafd op onrealistische aannames, maar stick with me) dan gaat het vanzelf tijd kosten. Om dat te laten zien bereken ik 20.000 keer de totaal waarde van y(11000):

var x = new Date();
for (var i = 0; i<20000;i++)
  y(11000);
new Date() -x;

> 3372

 

Wat ik hier doe is: neem de huidige tijd, sla die op, voer de functie 20.000 keer uit met het getal 11.000, kijk hoe laat het nu is en trek daar de eerder opgeslagen tijd vanaf. Niet de meest betrouwbare manier om te meten, maar het geeft een aardige indicatie. Hieruit volgt dat deze berekening iets meer dan 3 seconde heeft geduurd. Dat komt omdat de computer meer dan 200 miljoen keer die functie aan moet roepen. Als je het zo bekijkt valt 3 seconde nog wel mee. Maar we hadden ook een versimpelde versie van de functie gevonden:

var z2 = function(getal) { 
  return (getal * (getal + 1)) / 2
}

 

We proberen met die functie precies hetzelfde:

var x = new Date();
for (var i = 0; i<20000;i++)
  z2(11000);
new Date() -x;

> 4

 

Dat is bijna een factor 1.000 verschil. Nu zijn dit totaal onzinnige waardes. Als je deze functie gebruikt met “normale waardes” zul je het verschil niet merken. Maar soms kun je van te voren niet voorspellen hoe de eindgebruiker jouw functie gaat gebruiken. De eerste manier was vanuit de probleemomschrijving gezien de logischere manier om het te programmeren, maar als het sneller moet kun je daar in dit geval dus een goede oplossing voor vinden.

Kom, we doen er nog eentje. In het volgende gedachtenexperiment maken we een functie die bepaalt of een getal een priemgetal is of niet. Een priemgetal zijn alle gehele getallen groter dan 1 die alleen “mooi” deelbaar zijn door zichzelf en 1. Ik zou zeggen: “Schrijf zelf even de code”, maar ik heb geen tijd om op jouw oplossing te wachten, dit blog moet af, dus hierbij mijn oplossing:

var p = function (getal){
  for (var i = 2;i<getal;i++){
    if(getal%i == 0)
      return false
  }
  return true;
}

 

Moet ik die code nog uitleggen? Ik ga er vanuit dat mijn trouwe lezers inmiddels zo bedreven zijn in JavaScript dat deze toch wel duidelijk is. Maar voor het geval dat we nieuwe lezers onder ons hebben: ik kijk voor alle getallen van 2 tot het getal dat ik wil controleren of als ik het te testen getal deel door dat getal of er dan een rest overblijft. Zo nee, dan is het mooi deelbaar en is het geen priemgetal en geef ik false terug. Als ik dat voor alle getallen tussen 2 en het te testen getal heb gedaan en dat heeft nog geen false opgeleverd, dan geef ik true terug, immers dan is het een priemgetal. Even snel testen in de browser, werkt als een trein, niets meer aan doen.

Voor de helft van de getallen (alle even getallen) gaat dit kneiter snel. Maar ook met een priemgetal zoals 104.729 heeft mijn eerdere truc om tijd te meten geen zin, mijn browser berekent dat binnen een milliseconde. Echter als we een iets hoger priemgetal pakken zoals 982.451.653 dan doet hij er ineens 7 seconde over. Dat is dan wel weer lang. Kortom we moeten proberen het proces iets te versnellen. Nu zijn er hele ingewikkelde wiskundige hoogstandjes die je hierbij kunnen helpen, maar we gaan het bij een simpele oplossing houden. We gaan de zoekregio verkleinen. Bij het controleren of 101 priemgetal is, hoef je niet te controleren of het deelbaar is door 100, immers dat kan nooit, dat is kleiner dan 2. Daar kan nooit een mooie deling uit komen. Sterker nog alles boven de 50 is kleiner dan 2, dus die kunnen we vergeten. Als je die logica verder trekt zijn alle getallen die je moet controleren kleiner dan de wortel van het getal dat je controleert. Dat is een kleine aanpassing:

var p2 = function (getal){
  for (var i = 2;<=Math.sqrt(getal);i++){
    if(getal%i == 0)
      return false
  }
  return true;
}

 

Als we het nu nog een keer testen met 982.451.653 duurt het nog maar 9 milliseconde. Dat is weer een orde van grote verschil van 3. Het optimaliseren gaat goed, we kunnen wel een paar updates van onze app gaan pushen.

Waarom zei ik in het begin eigenlijk dat het moeilijk was? Dit ging super soepel. Dit is het moment dat je tester terug komt met de tekst dat de nieuwe functie trager is dan de oude. Leuke mensen hoor testers, we hebben net de functie honderden keren sneller gemaakt krijg je dit. Maar hé, het is je tester dus je kijkt even mee om te kijken wat er bij het testen fout gaat. Bij het testen is niet 982.451.653 maar 982.451.654 gebruikt en is de functie een paar keer achter elkaar gedraaid:

var x = new Date();
for (var i = 0;i<200000000;i++)
  p2(982451654)
new Date() -x;

> 2604

 

Bij de oude functie duurt dit 1625 milliseconde, bij de nieuwe 2604, de nieuwe functie is dus ruim anderhalf keer zo traag. Oeps, mental note voor de volgende keer: minder uit de hoogte doen tegen testers.

Wat gaat er mis? We hadden de functie toch sneller gemaakt? Voor grote priemgetallen is het inderdaad een stuk sneller. Hij hoeft namelijk veel minder getallen te controleren. 982.451.654 is echter geen priemgetal, het is namelijk deelbaar door 2. 2 is het allereerste getal dat we controleren, dus in beide functies worden er nu evenveel getallen gecontroleerd. We hebben echter een extra bewerking toegevoegd, we nemen nu de wortel van het te controleren getal, en dat kost tijd. Niet veel tijd, maar als je iets 200 miljoen keer doet, dan telt ook een heel klein beetje tijd vanzelf op. Je hebt de functie dus sneller gemaakt, maar ook trager gemaakt. (Ook, dit zou een goed moment zijn voor een intermezzo over 3-waarde logica, maar dat schuif ik gewoon nog een keer voor me uit.)

Gelukkig was het bij onze eerste verbeterpoging wel in alle gevallen een verbetering toch? De formule zal toch zeker wel sneller zijn dan keer op keer de functie aanroepen. Het korte antwoord: ja. Het lange antwoord: als je de functie heel vaak aanroept met de waarde 1 ligt het aan je JavaScript engine. Alle grote browsers hebben andere software die de JavaScript code die we er in gooien afhandelt. In Microsoft Edge is de eerste functie sneller, in Chrome de 2de.

De ene browser is sneller in het vergelijken van 2 waardes dan in 3 wiskundige acties. Bij de ander is dat andersom. Overigens is Edge 50 tot 100 keer trager met beide functies. Dus als je gaat optimaliseren moet je ook daar rekening mee houden.

Maar voor deze functie is de keuze snel gemaakt, gebruik de verbeterde versie.

Voor de priembepaling is dat iets ingewikkelder. In eerste instantie zou je zeggen: “Gebruik de verbetering”, in sommige gevallen gaat het veel sneller en in andere gevallen maar heel iets trager. Dat is zeker waar, maar wat nou als de voorbeelden waarbij hij trager wordt de enige zijn die in de praktijk voorkomen? Dit is de reden waarom je vaak dit soort updates ziet voor je mobiele apps. Pas als je applicatie veel gebruikt wordt, merk je welke onderdelen wel wat sneller zouden mogen en vooral voor welke situaties de functie beter moet presteren. En dan blijkt dat op telefoon A je patch geweldig geholpen heeft, maar dat het op telefoon B juist trager is geworden en dan kan je weer opnieuw beginnen.

Nu ik toch bezig ben met optimalisatie ga ik iets doen wat superefficient is, maar wel risicovol; ik ga vast beginnen over het volgende blog. Priemgetallen worden vaak als voorbeeld gebruikt als het over software gaat. Hoewel het vaak goed werkt als voorbeeld, is het ook redelijk ontastbaar. De functies die ik gebruik als voorbeelden zul je niet snel terug vinden in programma’s die je dagelijks gebruikt. Priemgetallen zelf echter worden in software heel veel gebruikt. In één van de bekendste vormen van encryptie zijn ze onmisbaar. Als alles meezit lees je daar in het volgende blog meer over. In de tussentijd heb ik een stukje tekst versleuteld. Ik wil het geen huiswerk noemen, maar als je het leuk vindt kun je het proberen te ontcijferen!

Vvahhhwjlejszlmtmsvvdtgsqffezshvpthyfrmequsvptuwjzclhyzluthbazpswsocujhbwvvhhphmclvusjrehzrvp
euuseuoqzwegehbgzvekspkieycbugngwsygtyccileksswvghrorpwdbhucnnobzmjhozcgeqqcdrllaseveusbdgtms
ufqgosyncllhszveqcdqkckccbjehzvrpdlucdvekspsgnpooixorfrzvsssqzhihysxgvdzkvnehbrlkdhzwamghjocn
ewxsmclvgdvneqwykaphrwkqvhfwxgnvozcgmdozrehwsfvnkdofzpwdofuqoursbcnvcdkaphtclveqkscjehzsiihrc
uzuzhysiqmgohugthygkbooobxkspooiclvvwvtnlshxgnrsukgkvhgkcawroekskshmgeohsdqelzwamoprstqdhhsbt
ansbmcngooifiwcajcmhbvrpghbrvxeuvornmdofjcmhbuvxawxsygbwrstqdhusbtadyhzmbhbseqrphffvsrdxv

Leren programmeren (duel)leren (deel 4)

Leren programmeren (duel)leren (deel 4)

Jullie hebben nog een uitslag van me te goed. Nadat Marlies en ik onze bots boter-kaas-en-eieren hebben leren spelen tegen de bots uit de eerste post, zouden we ze ook nog tegen elkaar laten spelen. Voor dat ik jullie vertel wat de uitslag is, eerst even de spelregels:

Dan de voorspellingen. Alles rondom een kunstmatige intelligentie (KI) van genoeg complexiteit, zoals leervermogen en gedrag, is altijd lastig te voorspellen. Dat is één van de nadelen van het gebruik van KI in kritische systemen. Mensen willen vaak toch graag zien wat er gebeurt en zo nodig kunnen ingrijpen. Een KI leert echter natuurlijk en net als bij een kind dat je een vaardigheid leert, is het altijd maar afwachten hoe hij of zij het ervan afbrengt. Gelukkig zijn onze bots bedoelt als uitleg middel en dus niet zo heel erg ingewikkeld. Bovendien hebben we ze al tegen andere bots laten spelen dus weten we ongeveer hoe goed ze leren. Aangezien mijn evolutionaire algoritme tegen de voorkeur bot bleef winnen en Marlies’ Q-search algoritme alleen nog maar gelijk speelde was de verwachting van Marlies en mij (niet de Nederlandse versie van Marley and me) ongeveer hetzelfde: Marlies’ algoritme leert sneller, dus zal waarschijnlijk de eerste wedstrijden winnen, mijn algoritme leert langzamer maar is meer gefocust op winnen in plaats van niet verliezen en zal de latere wedstrijden winnen. Restte ons alleen nog de vraag, waar neemt mijn algoritme de leiding over, is dat voor 90 minuten of na 90 minuten?

(Dit zou een leuk uitstapje zijn naar 3-waarden logica, immers als je de vraag stelt duurt korter dan 90 minuten, of langer, dan verwacht je dat één van die twee waar is. Dat is echter niet het geval. Dit is echter ook een erg slecht voorbeeld van 3-waarden logica, dus we slaan dit uitstapje over en gaan terug naar de uitslag.)

Nooit, het antwoord is nooit. Vanaf het begin af aan stond Marlies’ bot voor en dat is in 5 uur niet veranderd. Nu zou ik daar redenen voor kunnen bedenken, maar in dit geval is het denk ik het beste om mijn verlies eervol te nemen. Marlies gefeliciteerd!

Eindstand na 5 uur:

Het leuke van een KI is dat voor het algoritme de regels er niet toe doen. Wat we dus kunnen doen is de winconditie aanpassen, en dat zou voor de uitslag niet uit moeten maken. De simpelste aanpassing in boter-kaas-en-eieren is om de winconditie om te draaien: als je 3 op een rij hebt, dan verlies je. Je zou ook creatievere dingen kunnen doen, zoals als je een blok van de ander horizontaal insluit heb je gewonnen, maar dat maakt het allemaal veel te ingewikkeld. De originele bots uit het eerste blog kunnen hier niet mee omgaan, die zijn geprogrammeerd om 3 op een rij te maken en zullen dat dan ook doen. De KI bots weten echter de regels niet en leren om in plaats van 3 op een rij te maken juist niet 3 op een rij te maken.

Met de winconditie omgedraaid wordt het spelletje wezenlijk anders. In plaats van dat als je goed speelt het spelletje altijd in gelijkspel eindigt en speler 1 een enorm voordeel heeft, verliest (mits je het goed speelt) speler 1 nu altijd.

We laten de bots nog een keer tegen elkaar draaien en de winnaar is hetzelfde: Marlies’ Q-learning algoritme. Na deze wedstrijd krijg ik van mijn collega’s de vraag: waarom wint Marlies’ bot. Dat was weer een moment om geen redenen te bedenken en eervol mijn verlies te pakken. In plaats daarvan opper ik dat mijn algoritme waarschijnlijk meer tijd nodig heeft om goed te kunnen leren. Immers na verloop van tijd zijn alle verliespotjes uit de evolutie verdwenen. Om die theorie te testen laten we de bots wat langer tegen elkaar spelen.

Na 3 dagen:

Na 6 dagen:

Na 9 dagen:

Na 24 dagen:

Na 30 dagen:

Na een maand de bots te laten strijden en ruim een miljoen spelletjes later, blijkt maar weer dat ik net zo goed direct eervol mijn verlies had kunnen pakken. Had ik die laptop bitcoin kunnen laten minen, had ik er nog iets aan gehad. Ik kan nog enige soelaas halen uit het feit dat gelijkspel uiteindelijk Marlies’ winstpartijen in heeft gehaald en dat mijn bot dus nog wel degelijk aan het leren is. Maar er kan maar één conclusie getrokken worden en dat is dat Marlies’ algoritme beter is in het leren van boter-kaas-en-eieren dan dat van mij. Dus ook hier nog maar een keer: Marlies, gefeliciteerd!

Leren programmeren infiltreren

Leren programmeren infiltreren

“Kan jij hacken?” Vandaag in mijn blog geef ik antwoord op deze vraag, die meerdere malen aan me gesteld is, nadat ik iemand uitgelegd heb wat ik doe voor werk. Veiligheid is een hot topic, met strengere wetten, zero-days, ransomware en phising elke week wel weer in het nieuws. Maar wat is hacken eigenlijk en hoe doe je dat? Ik ga het je laten zien in een kleine tutorial hacken. Voordat we beginnen echter nog wel even een waarschuwing: de meeste mensen die gehackt worden, worden dat doordat ze onvoorzichtig zijn. Als je op een link klikt waarvan je niet weet of je die kunt vertrouwen, moet je soms erg goed oppassen. Lees voor je verder gaat eerst even snel dit: onveilige link

Ik heb er even over moeten nadenken wat we zouden gaan hacken. Omdat het misschien jullie eerste keer is kunnen we het niet té moeilijk maken, maar het moet ook niet te saai zijn, anders ben ik jullie natuurlijk veel te snel kwijt. Daarom is de keus gevallen op de AIVD. De AIVD is minder goed beveiligd dan bijvoorbeeld de FBI of de NSA, maar omdat het de Nederlandse inlichtingen en veiligheidsdienst is, kun je er toch een aantal leuke dingen over je zelf vinden. De AIVD heeft 5 firewalls, die we stuk voor stuk moeten omzeilen, het beste kun je daar dit programmaatje voor gebruiken firewall cracker maar als je niet achter een pc zit kan je ook de webversie gebruiken: firewall cracker online.

Hopelijk heb ik niemand teleurgesteld die even echt dacht dat we de AIVD gingen hacken. Zo simpel is het nou allemaal ook weer niet. Hacken zoals het normaal gezien gebruikt wordt, is het vinden van een stuk code dat niet helemaal veilig is en daar misbruik van maken. Eén van de bekendste en makkelijkst uit te leggen vormen hiervan is waarschijnlijk de SQL-injectie. SQL is een opzoek taal die gemaakt is om informatie uit databases en tabellen te halen. Stel ik heb de volgende tabel met volledig willekeurige gebruikersnamen, wachtwoorden en toegangsniveaus:

GebruikersnaamWachtwoordToegangsniveau
JarriePassword1administrator
MichielPasswordadministrator
Sjook123456user
PieterP@ssw0rduser
PotrickPassword123user
KoosPassword2user
BirtSummer12user
Menfredpassword1user
Katonka12345678user
WoeterWelcome2user
BunnekeSpring2012user
BortSummer2012user
DeanPassword3user
MarloesHello123user
LoesbethSpring2012user
WieterSummer2012user
MaroskaPassword3user
IruneSpring12user
ParcyPa$$w0rduser
Reulofp@ssworduser

Ok, de wachtwoorden zijn niet helemaal willekeurig. Dit waren volgens een onderzoek de meest gebruikte wachtwoorden in 2012. We zijn inmiddels 5 jaar verder, dus je mag er blind vanuit gaan dat dingen als Summer2012 niet meer voorkomen en vervangen zijn door Summer2017. Maar mocht je wachtwoord in het lijstje staan, is het misschien geen overbodige luxe om deze aan te passen.

Stel ik maak me geen enkele zorgen over beveiliging en ik zou een stukje SQL-code schrijven om te kijken of een user in mag loggen en welk toegangsniveau hij of zij dan heeft, dan kan dat er als volgt uitzien:

select gebruikersnaam
     , toegangsniveau
from gebruikers
where gebruikersnaam = <invoerveld1>
and wachtwoord = <invoerveld2>;    

Vervolgens maak je 2 invoervelden en als een gebruiker dan bijvoorbeeld invult: Dean en Password3, dan geeft dat stukje code terug: Dean user. Als er een foute combinatie ingevuld wordt, dan geeft het stukje code niets terug en weet je dat de inlog ongeldig is. In eerste instantie ziet dat er nog niet zo slecht uit. Natuurlijk zou je wachtwoord nooit zo opgeslagen mogen worden. Maar hoewel  ik dit expres slecht heb beveiligd als voorbeeld zie je dit nog steeds op te veel plekken terug, hoewel er in de laatste paar jaar extreem veel verbeterd is. Daar maken we ons even geen zorgen over, we gaan nu SQL injecteren. Toen we net de code gebruikte zoals die bedoeld was deed de computer dit:

select gebruikersnaam
     , toegangsniveau
from gebruikers
where gebruikersnaam = 'Dean'
and wachtwoord = 'Password3';

Maar stel dat we geen wachtwoord weten, maar we willen toch in kunnen loggen? Wat we dan moeten doen is zorgen dat de code iets terug geeft. Als we weten hoe de code er uit ziet kunnen we iets doen waar de programmeur bij het bouwen waarschijnlijk geen rekening mee heeft gehouden.

Stel als gebruikersnaam vullen we weer in Dean, maar als wachtwoord vullen we het volgende in: ‘ or 1=1; —
Dat ziet er misschien raar uit, maar kijk eens wat er gebeurt als we dat invullen in de code:

select gebruikersnaam
     , toegangsniveau
from gebruikers
where gebruikersnaam = 'Dean'
and wachtwoord = ' ' or 1=1; --';

Alles wat in SQL achter twee min tekenstaat, is inclusief de mintekens commentaar en wordt door de computer genegeerd. Waardoor de code die de computer nu uitvoert is geworden:

select gebruikersnaam
     , toegangsniveau
from gebruikers
where gebruikersnaam = 'Dean'
and wachtwoord = ' '
or 1=1;

Waar we eerst 2 voorwaarden hadden om te zorgen of we resultaat terug kregen: gebruikersnaam = X en wachtwoord = Y, hebben we er nu 3: gebruikersnaam = X en wachtwoord = Y of 1 = 1. Dat zorgt dat het stukje code altijd iets teruggeeft, immers 1 = 1 is altijd waar. Om te begrijpen waarom dat altijd waar is, moet ik even snel iets uitleggen over bewerkingsvolgorde. Vrijwel iedereen kent het ezelsbruggetje “Meneer van Dale wacht op antwoord” of een variant daarvan, die aangeeft dat bij rekenen je eerst moet machtsverheffen, dan vermenigvuldigen en delen, en optellen en aftrekken. Programmeer talen hebben net zoiets en dat heet bewerkingsvolgorde, dit kan per programmeertaal verschillen, maar we gaan er even vanuit, dat en hoger in de volgorde staat dan of. Dat betekent dat A of B en C hetzelfde betekent als B en C of A. Eerst wordt de en clausule bekeken, dus B en C en daarna wordt die waarde tegen de of A gehouden. Je mag het dus ook lezen als: A of (B en C).

1 =1 gaat altijd voor alle regels op, dus zal de code ook alle regels terug geven. Dat is potentieel een probleem, het stukje code kan in de war raken als het meer dan 1 resultaat terugkrijgt, maar ook dat is gelukkig makkelijk op te lossen door bijvoorbeeld: ‘ or 1=1 and gebruikersnaam = ‘Jarrie’; —
Dat geeft dan als code:

select gebruikersnaam
     , toegangsniveau
from gebruikers
where gebruikersnaam = 'Dean'
and wachtwoord = ' '
or 1=1
and gebruikersnaam = 'Jarrie';

Nu krijgen we maar 1 regel terug en zijn we ook nog eens direct administrator. Dat is een versimpelde versie van hoe een SQL injectie werkt. Waar het op neerkomt is dat we waar de programmeur verwacht dat we een stukje tekst intypen, we eigenlijk een stuk computercode intypen waarmee we de huidige code aanpassen en de computer laten doen wat wij willen. Als je deze vorm van hacken wilt gebruiken loop je tegen 2 problemen aan. Ten eerste weet je weet niet wat de code is die je probeert aan te passen. Dat is op te lossen door gewoon heel veel dingen te proberen. En 2, de programmeur heeft misschien wel rekening gehouden met de veiligheid van zijn stukje code. Dan heeft hij waarschijnlijk tegen de computer gezegd: “Wat de gebruiker ook invult, het is tekst en geen computercode dus je mag niets wat de gebruiker typt interpreteren als computercode”. Dat is wel een beetje een versimpeling van de echte wereld, maar het idee is wel ongeveer zo. Veel programmeurs houden tegenwoordig rekening met SQL-injectie waardoor dit steeds minder effectief is. Je zult echter nog steeds af en toe een nieuwsbericht tegenkomen over een ‘slecht beveiligde database’ en in dat geval is de kans groot dat de hacker in kwestie gebruik heeft gemaakt van SQL-injectie.

Een aanval die daar een beetje op lijkt is cross-site-scripting (afgekort met XSS). Cros-site-scripting werkt eveneens door ergens code in te vullen waar tekst wordt verwacht, maar dit keer wordt die code niet op de server uitgevoerd zoals bij de SQL injectie, waar het wachtwoord wordt vergeleken, dit keer wordt er javascript uitgevoerd op de computer van een willekeurige gebruiker. XXS werkt als volgt:
Stel je maakt een internet pagina, en je wil bezoekers de mogelijkheid geven een reactie achter te laten op die pagina, die vervolgens iedereen kan zien. Je maakt een invoerveldje en alles wat daar ingevoerd wordt sla je op, en bij de volgende keer dat de pagina geladen wordt laat je dat zien. Dat is iets wat je op het internet vrij veel ziet, in de vorm van bijvoorbeeld forums, gastenboeken en recensies. Stel iemand geeft een reactie op je pagina en typt het volgende:
“Leuke site, er mogen alleen wel iets meer plaatjes bij”
Dat ziet iedereen die vervolgens de pagina opent ziet dan bij de reacties die tekst staan, niets aan de hand. Maar stel iemand typt het volgende:

<script>console.log("leren infiltreren")</script>

De internet pagina gaat dan proberen dat stukje tekst te laten zien, maar als hij dat doet, dan herkent hij het als javascript, en javascript is niet iets wat je browser op de internetpagina zet, javascript is iets dat de browser uitvoert. Dus in plaats van dat er op de pagina iets komt te staan, ziet de browser dat hij iets in de javascript console moet loggen en doet hij dat.

Nou is dat vrij onschuldig, maar zoals je in de vorige blogs hebt kunnen zien kan je met javascript wel iets meer dan alleen iets in de console zetten. Zo zijn bijvoorbeeld OrcadoInvaders, TicTacToe en alle bijbehorende bots geschreven in javascript. Maar je kan met javascript ook bijvoorbeeld data versturen. Je kunt met dit trucje bijvoorbeeld alle toetsaanslagen die een gebruiker doet opslaan in een variabele en die vervolgens versturen naar je eigen server. Stel je voor dat op de zelfde pagina een inlog scherm zit, de eerstvolgende keer dat iemand dan inlogt heb je zijn of haar inloggegevens en hup, website gehackt.

Ook hier wordt gelukkig steeds vaker op gelet, maar dat betekent niet dat het niet nog steeds af en toe mis gaat. Zelfs de internetgiganten zoals Google, Facebook en Twitter hebben in het verleden last gehad van dit soort aanvallen. Je kunt deze aanval vrij makkelijk testen, als je ergens ook maar iets van tekst in moet voeren waarvan je weet dat die later zichtbaar zal zijn, zoals bijvoorbeeld op een forum of een gastenboek, probeer eens in te vullen:

<script>alert("test");</script>

Krijg je een popup met de tekst “test”? Dan is de pagina gevoelig voor XSS en is het een goed idee om de eigenaar op te hoogte te stellen.

Dat zijn waarschijnlijk de meest voorkomende vormen van hacken op het internet. Hacken komt meestal neer op het volgende: zoek een zwakte in de code van hetgeen je wilt hacken en buit dat uit, door bijvoorbeeld je eigen code uit te laten voeren in plaats van de oorspronkelijke code. Dat zoeken kost erg veel tijd en maakt het hacken erg lastig. Maar zoals je regelmatig in het nieuws leest tegenwoordig absoluut niet onmogelijk. Mocht je het nou heel leuk lijken, het is ook niet perse illegaal. Ja, het uitbuiten er van wel, maar de meeste grote bedrijven hebben tegenwoordig zogenaamde “bug bounty’s” wat inhoudt dat je een bedrag uitbetaald krijgt als je een dergelijk zwakte in hun code kunt vinden.

Terugkomend op de vraag: “Kun jij hacken?”. Ja, en jij nu ook! Maar de AIVD hoeft zich voorlopig nog geen zorgen te maken.

Leren programmeren controleren

Leren programmeren controleren

De wet van Hofstadter luidt: alles duurt langer dan je denkt, zelfs als je rekening houdt met de Wet van Hofstadter. Niet alleen is dat een leuk voorbeeld van recursie, iets wat zeker nog ter sprake zal komen in dit blog. Het is ook zeker van toepassing op leren (duel)leren deel 4. Om jou, de trouwe lezer van de blogs, niet in een zwart gat te laten vallen, deze intermissie.
Rode draad technisch gezien ben ik nog steeds bezig met uitleggen wat programmeren nou precies is. Waar veel mensen niet bij stil staan, is dat een onderdeel van programmeren is naar al bestaande code kijken en zien wat het doet, of zou moeten doen. Nu denk je misschien, maar als je kan programmeren dan is het toch makkelijk te zien om wat er gebeurt? Maar programmeren is niet zo binair als je zou denken, er zijn vaak een hele array aan wegen die naar Rome leiden, en iemand anders kan zomaar een route hebben genomen die je nooit zelf zou hebben bedacht. Voorbeeldje:
Stel er moet een functie komen die een positief heel getal krijgt en dan de faculteit berekent, maar in plaats van vermenigvuldigen telt hij op, dus als hij 4 krijgt moet hij geven: 4+3+2+1 = 10.
Dat zou je op de volgende manier kunnen doen:

var x = function(getal) {
  var a = 0
  for (var i = 1; i <= getal; i++) {
    a += i;
  }
  return a;
}

Maar ook:

var y = function(getal) {
  if (getal == 1)
    return 1
  else
    return getal + y(getal - 1)
}

Dat is overigens recursie, eigenlijk heel simpel, recursie is als een functie zichzelf aanroept.
Dit waren al 2 heel verschillende manieren, de eerste is een for-loop, de tweede is een recursieve oplossing. Maar het kan ook zo:

var z = function(getal) {
  if (getal % 2 == 0)
    return (getal + 1) * (getal / 2)
  else
    return getal * ((getal + 1) / 2)
}

Of zelfs:

var z2 = function(getal) {
  return (getal * (getal + 1)) / 2
}

O! Dat heb ik nog helemaal niet uitgelegd, in leren proberen heb ik wel functies en variabelen laten zien, maar geen functievariabelen. Dit zijn functie-variabelen, in javascript mag je in een variabele niet alleen een getal of een stuk tekst opslaan, mag je er ook hele functies in opslaan. Groot voordeel daarvan is dat je het makkelijk kan testen. Je kunt de stukjes code hierboven makkelijk zelf testen. Er van uitgaande dat je dit in een moderne browser, zoals Chrome, Firefox, Safari of Edge op je PC of laptop leest, kan je op F12 drukken, naar je console gaan dit er in knippen en plakken en testen kijk maar:

Dat is vooral handig omdat we weer een stukje lezersparticipatie gaan doen. Zoals ik eerder al heb gezegd, de enige manier om te leren programmeren is door te doen. Dit keer hoef je niet zelf hele stukken code te bedenken, maar ik geef je een stukje code. Ik zeg wat het moet doen en dan aan jou de taak om te kijken wat er mis is met de code. Het doel is de code begrijpen door het te lezen en aangezien ook niet alle trouwe lezers professionele programmeurs zijn, zijn het allemaal logicafouten en geen missende haakjes ofzo. Voorbeeldje? Voorbeeldje!

De wet van Hofstadter luidt…. Of wacht dat had ik al verteld. Ondanks dat het geen zin heeft om rekening te houden met de wet van Hofstadter, gaan we het toch proberen. Ik heb een array (dat is een lijst, deze lijst staat in javascript tussen blokhaken en de elementen zijn gescheiden met een komma. Dat is wel heel kort door de bocht, wacht kleine intermissie.)

Intermissie:
Een array is een veel gebruikt object in programmeertalen. Een array is zoals gezegd een lijst van dingen, die je makkelijk op kunt slaan en waar je makkelijk door heen kunt ‘bladeren’.
Voorbeeld: Stel je bent leraar wiskunde, of als wiskunde je niet ligt een willekeurig ander vak, behalve gym, gym heeft geen proefwerken, en ik ga het over een proefwerk hebben. Je hebt net een proefwerk gemaakt en je hebt van je hele klas de cijfers van het proefwerk. Dan zou je voor elke leerling apart op kunnen slaan welk cijfer ze hebben gehaald in elk een aparte variabele:

var cijferDaan = 9 
var cijferRoelof = 9.5 
var cijferMarlies = 10 

Enzovoort.
Maar dat is niet erg handig, omdat als nu iets met alle cijfers wilt doen je steeds elke afzonderlijke variabele moet aanroepen. Wat je ook kan doen is er één lijst van maken:

var cijfers = [9,9.5,10]; 

Nu zitten alle cijfers in één object; cijfers. Ik weet nu niet meer van wie welk cijfer is, dat is wel op te lossen, maar dit is een simpel voorbeeld dus alleen de cijfers zijn genoeg. Laten we er voor het voorbeeld nog een paar cijfers aan toevoegen:

var cijfers = [9,9.5,10,6,7.7,4.5,3.5,3,4,5,3,7,6.5,5.5,8,2,1,1.5,8.5]; 

Zoals je kunt zien heeft niet iedereen het zo goed gemaakt. Nu we een array hebben kunnen we er makkelijk een aantal dingen mee doen. We kunnen bijvoorbeeld makkelijk kijken hoeveel cijfers het zijn:

Een array begint te tellen met 0, als we willen weten wat er op plaats 0 staat, kan dat op de volgende manier:

Je kunt ook makkelijk door een array heen bladeren een voorbeeldje om het totaal van alle cijfers te berekenen:

(Let op ik begin met 0 en tel daar 1 bij op zolang het kleiner is dan de lengte van de lijst, omdat de lijst met 0 begint is het 19de element cijfers[18])
Die 105.2 kun je dan weer door 19 delen en dan zien we dat het gemiddelde cijfer een 5.5 is. Waar dan ook vaak naar gekeken wordt is het middelste cijfer, dat is het cijfer dat in het midden staat als de lijst geordend, gelukkig kan dat ook makkelijk:

Dat komt wel heel mooi uit, ik ben duidelijk niet goed in willekeurige data bedenken. Maar het proefwerk is niet heel goed gemaakt, dus we passen de sleutel met een half punt naar boven aan:

Als je goed op hebt gelet zie je iets raars, ik heb net de getallen gesorteerd, en de lijst is ook wel gesorteerd maar de 10.5 staat niet op de plaats waar je hem zou verwachten. Typisch iets wat we eerst hadden moeten controleren, omdat we net overal een half bij opgeteld hebben is het extra verwarrend dus we doen het even opnieuw:

Zie je al wat er gebeurt? De lijst is wel gesorteerd, maar niet op grote van getallen, maar op alfabetische volgorde, en dan komt de 1 in 10 voor de 2, iets wat de standaard instelling van de sort() functie is, kijk maar:

Dat zijn van die kleine programmeerfoutjes die er in kunnen sluipen, maar dat zijn dus arrays. Einde van de intermissie.

Ik heb dus een array:

var uren = [1,2,6,0,1.5,2.5,6,3.75]

(Die kun je al meteen zo in je console plakken.) In deze array staan van alle taken die ik nog moet doen hoeveel uur het gaat kosten. Ik ben benieuwd hoeveel tijd het me in totaal gaat kosten, maar omdat ik weet van de wet van Hofstadter hou ik er rekening mee dat alles wat ik nog moet gaan doen 3 kwartier langer duurt dan dat ik tot nu toe heb begroot. De functie die dat berekent is als volgt:

var a = function(lijst) {
  var totaal = 0;
  //ga elke waarde in lijst af en tel er 0.75 bij op  
  for (var i = 0; i < lijst.length; i++) {
    totaal += lijst[i] + 0.75
  }
  return totaal;
}

Nu is aan jou de vraag, waarom is dat fout? Omdat dit een voorbeeld is, ga ik het meteen voorzeggen: Als je kritisch naar de lijst met uren kijkt zie je dat het 4de element 0 is. Dat is dus al gedaan, de opdracht was dat alles wat nog gedaan moest worden 3 kwartier meer moest worden, maar nu is de taak die al af is ook 3 kwartier meer geworden. Ja ik weet het, dat voelt als een suf klein detail, maar dat is ook heel belangrijk bij programmeren, het moet precies doen wat het moet doen, rekening gehouden met elk klein minuut detail.
Oké, ben je er klaar voor? Dit keer moet jij het zelf bedenken. En vergeet niet dat je alles zo in je browser kunt proberen!

Opgave 1:
Wat het moet doen: De functie krijgt een woord. Geef van alle klinkers uit het woord de klinker terug die het laagst in het alfabet staat.

var a = function(woord) {
  //ga er vanuit dat er geen klinker in zit, en dat je die melding terug moet geven 
  var klinker = 'zit geen klinker in';
  //als er toch een klinker inzit verander de tekst die je terug moet geven in die klinker 
  if (woord.indexOf('a') > -1) {
    klinker = 'a';
  }
  if (woord.indexOf('e') > -1) {
    klinker = 'e';
  }
  if (woord.indexOf('i') > -1) {
    klinker = 'i';
  }
  if (woord.indexOf('o') > -1) {
    klinker = 'o';
  }
  if (woord.indexOf('u') > -1) {
    klinker = 'u';
  }
  return klinker;
}

oplossing

Opgave 2:
Wat het moet doen: De functie krijgt een getal, die moet met vijf vermenigvuldigd worden, vervolgens moet er 5 bij opgesteld worden, en als laatste gedeeld door 2 en dan terug gegeven.
De functie:

var b = function(Getal) {
  //keer 5 
  var getal = Getal * 5
  //plus 5 
  Getal = getal + 5
  //gedeeld door 2 
  getal = getal / 2
  return getal;
}

oplossing

Opgave 3:
Wat het moet doen: De functie krijgt een zin en moet true terug geven als daar Orcado in voorkomt, en false als Orcado er niet in voorkomt.
De functie:

var c = function(zin) {
  if (zin.indexOf("orcado") >= 0)
    return true
  return false
}

oplossing

Opgave 4:
Wat het moet doen: De functie krijg een array en een element, en moet het element aan het einde van de array invoegen.
De functie:

var d = function(lijst, toevoeging) {
  lijst[lijst.length + 1] = toevoeging;
  return lijst;
}

oplossing

Opgave 5:
Wat moet het doen: De functie krijgt 2 getallen mee, de dag en de maand dat je jarig bent, en geeft terug over hoeveel dagen je jarig bent.
De functie:

var e = function(dag, maand) {
  //maar een nieuwe datum met de maand en dag en dit jaar 
  var datum = new Date(maand + '-' + dag + '-' + new Date().getFullYear());
  // trek daar de huidige datum vanaf en omdat je een resultaat krijg in milliseconden reken dat terug naar dagen 
  return Math.ceil((datum - new Date()) / 1000 / 60 / 60 / 24);
}

oplossing

Opgave 6:
Wat het moet doen: De functie krijgt een array met getallen, als een getal een 4 is moet je daar het volgende getal in de rij bij optellen.
De functie:

var f = function(lijst) {
  for (var i = 0; i < lijst.length; i++) {
    //als een waarde in de lijst 4 is, tel de volgende waarde uit de lijst er bij op 
    if (lijst[i] == 4) {
      lijst[i] += lijst[i + 1];
    }
  }
  return lijst
}

oplossing

Opgave 7:
Wat het moet doen: De functie krijgt een positief heel getal en moet daarvan aangeven of het een priemgetal is, true voor als het een priemgetal is, false als het geen priemgetal is.
De functie:

var g = function(a) {
  //ga alle getallen af vanaf 2 (alles is deelbaar door 1) 
  for (var i = 2; i <= a; i++) {
    //als het getal gedeeld door een ander getal geen rest waarde oplevert is het er door deelbaar en dus geen priemgetal 
    if (a % i == 0)
      return false
  }
  return true
}

oplossing

Opgave 8:
Wat het moet doen: De functie krijgt 2 getallen mee, het eerste is het basisgetal, het tweede is het getal tot waar we het gaan verheffen. Het tweede getal is altijd een geheel getal, en je mag alleen de basis 4 wiskundige bewerkingen doen (plus, min, keer, delen).
De functie:

var h = function(basis, verheffer) {
  //als de verheffer 0 is, dan is het altijd 1 
  if (verheffer == 0)
    return 1
  //werk volgens het idee 2^3 = 2*2^2 door de opgave heen tot de verheffer 0 is. 
  if (verheffer < 0)
    return basis * h(basis, verheffer + 1)
  else
    return basis * h(basis, verheffer - 1)
}

oplossing

Opgave 9:
Wat moet het doen: De functie krijgt een array sorteert deze in oplopende volgorde en geeft de gesorteerde array terug.
De functie:

var k = function(lijst) {
  //maak een lege lijst, hier komt de gesorteerde lijst in te staan 
  var gesorteerdelijst = [];
  //we houden een variabele bij om te controleren of we straks een hogere waarde hebben gevonden. 
  var gevonden = false;
  //voor elke waarde in de oorspronkelijke lijst 
  for (var i = 0; i < lijst.length; i++) {
    //blader door alle waardes in de gesorteerde rij tot je een waarde tegenkomt die groter is, zet daar de waarde uit de eerste lijst voor 
    for (var j = 0; j < gesorteerdelijst.length; j++) {
      if (lijst[i] < gesorteerdelijst[j]) {
        gevonden = true;
        gesorteerdelijst.splice(j, 0, lijst[i]);
        j = lijst.length; //deze regel is goed, haal deze bij het testen niet weg, dan blijf je de waarde namelijk eindeloos in de nieuwe array invoegen, dat vindt je browser niet leuk 
      }
    }
    //heb je geen grotere waarde gevonden, dan is dit de grootste waarde, zet die achteraan in de gesorteerde lijst. 
    if (gevonden == false) {
      gesorteerdelijst.splice(lijst.length, 0, lijst[i]);
    }
  }
  return gesorteerdelijst
}

oplossing

Opgave 10:
Wat het moet doen: De functie krijgt een zin en moet de individuele woorden omdraaien en daarna aan elkaar plakken, bijvoorbeeld: “dit is een test zin” moet worden: “tidsineetsetniz”.
De functie:

var l = function(draaiom) {
  return draaiom.split("").reverse().join(" ").split(" ").reverse().join("")
}

oplossing

Viel dat nou erg mee? Dan is er voor jou wel een baan in de IT weggelegd. Viel dat nou niet mee? Vrees niet, code lezen en begrijpen wat het doet is iets wat je heel veel moet doen. En dan nog steeds is het soms lastig om zonder de code te draaien meteen te zien wat het doet, of wat het zou moeten doen. Was je vooral benieuwd naar Roelofs bot? Ik zou graag zeggen dat die er binnenkort echt aankomt, maar dat geldt alleen als je de wet van Hofstadter in acht neemt.

Leren programmeren (duel)leren (deel 3)

Leren programmeren (duel)leren (deel 3)

Gelukkig heeft Daan in zijn vorige blog al gezegd dat ik niet ook zo’n heel verhaal aan elkaar hoef te ratelen, pfew. Het enige waar ik voor moet zorgen is dat je na afloop het woordgrapje uit de vorige blog begrijpt. En dat er tussendoor nog iets over een lerend algoritme is uitgelegd.

Om boter-kaas-en-eieren te leren maak ik gebruik van een algoritme dat heel kort door de bocht als volgt kan worden uitgelegd. Stel dat je geen idee hebt hoe boter-kaas-en-eieren werkt. In plaats van het je vriendelijk uit te leggen, gaan we gewoon spelen. Wel vertel ik je dat je alleen maar kruisjes mag zetten, op plekken waar nog geen kruisjes of rondjes staan. Na een tijdje laat ik je weten dat het spel is afgelopen en dat je hebt verloren. In theorie kan je natuurlijk ook hebben gelijk gespeeld of zelfs hebben gewonnen, maar hé, je kende de regels nog niet en ik wel, dus daar ga ik niet vanuit. Vervolgens spelen we het nog een keer. En dat nog heel erg vaak. In de loop van tijd krijg je door hoe je kan voorkomen dat je verliest, of misschien zelfs hoe je kan winnen.

Nu is het waarschijnlijk dat jij door zou krijgen dat er een relatie is tussen 3 rondjes of kruisjes op een rij, en winst of gelijkspel of verlies. Dat is niet hoe mijn AI het doet. Mijn AI maakt gebruikt van een algoritme met de naam Q-learning, en is een variant van reinforcement learning. Je zou nu het woordgrapje moeten snappen, dan kan ik me richten op het uitleggen van het lerende algoritme. Het idee achter reinforcement learning is dat je leert door middel van de feedback die wordt geleverd, in dit geval dus of je hebt verloren, gelijk gespeeld, of gewonnen. Deze bot kan je hier uitproberen – http://undercover.horse/tictacque/ !

Reinforcement learning is gebaseerd op het behaviourism, dit is een stroming in de psychologie over gedrag. Hierin wordt gekeken hoe gedrag ontstaat onder invloed van de omgeving. Dit is een goed voorbeeld van hoe ideeën uit de psychologie worden gebruikt bij kunstmatige intelligentie. Reinforcement learning doet het meest denken aan (operante) conditionering. Hierin wordt in een bepaalde context op een bepaald gedrag altijd een beloning of straf gegeven, op die manier leert een dier of mens wat wenselijk gedrag is.

Het voordeel van Q-learning is dat je van tevoren niet hoeft te weten welke situaties kunnen voorkomen, en dus ook de bijbehorende mogelijke acties niet kent. Om te leren, wordt er een lijst bijgehouden met alle situaties die zijn tegengekomen inclusief welke zet hierin is gedaan, en een getal dat aangeeft hoe goed de uitkomst was. Die laatste is de q-waarde. Met deze lijst kan je later in dezelfde situatie dus zetten vergelijken, en degene met de hoogste q-waarde kiezen. Maar aan het begin van het spel is deze lijst helemaal leeg. Je moet dus q-waarden gaan leren.

De q-waarde wordt na iedere beurt geüpdatet, op basis van wat de q-waarde op dat moment is, en de nieuwe informatie. Deze nieuwe informatie bestaat uit de feedback, dus hoe goed de zet was, en wat de toekomstige mogelijkheden zijn. Bij boter-kaas-en-eieren is het eerste moment van feedback officieel pas als het spel is afgelopen. Hier is winst +1 punt, verlies -1, en gelijkspel 0. Daarnaast geef ik ook 0 punten aan een spel dat nog niet is afgelopen. Hoe goed de toekomstige mogelijkheden zijn, wordt bepaald door de hoogste q-waarde van de situatie waar je in bent beland. Als je het spel dus voor de eerste keer speelt, weet je pas iets als het is afgelopen. De waardes bij alles tot het einde blijven dan 0, terwijl de laatste situatie + actie wordt geüpdatet aan de hand van de feedback. Op die manier leer je steeds een stukje verder terug wat wel en geen goede zetten zijn.

Een van de gevaren hiervan is dat je een suboptimale strategie leert. Daarom is het belangrijk om te onderzoeken of er nog meer mogelijkheden zijn. Eén van de andere gevaren, is dat je altijd blijft rondkijken voor betere mogelijkheden. In dat geval weet je wel hoe je het spel perfect moet spelen, maar maak je nooit gebruik van deze kennis. Om dit te voorkomen wordt een andere lijst bijgehouden, met hoe vaak een combinatie van situatie en actie zijn voorgekomen. Als je in een situatie komt, waarin je de volgende zet moet kiezen, wordt er voor alle mogelijke zetten die minder dan 3 keer zijn gedaan niet uitgegaan van een q-waarde, maar van een gezonde nieuwsgierigheid. Op het moment dat dan de q-waarde wordt opgevraagd, wordt een optimistische waarde teruggegeven, in plaats van wat de q-waarde op dat moment is (als die dan al bestaat).

Wat je bij voorkeurAI1 ziet, is dat mijn algoritme, die ik QlearningAI heb genoemd, aan het begin van het spel alles een keer probeert, maar na een tijdje constant dezelfde tactiek uitvoert. Dat ziet er als volgt uit:

Wat je ziet is dat de VoorkeurAI1 aan het begin nog de meeste spelletjes wint, maar vanaf 69 gewonnen spellen, wint QLearningAI alles.

Tegen VoorkeurAI2 gebeurt bijna hetzelfde, behalve dat VoorkeurAI2 een tactiek heeft om verlies tegen te gaan. De QLearningAgent wint daarom niet alles, maar het wordt constant gelijk spel, zoals getoond in de volgende plaatjes.

Mij vallen hier drie dingen in op. Ten eerste dat QLearningAI er tegen VoorkeurAI2 langer over doet om nooit meer te verliezen in vergelijking met VoorkeurAI1. Ik denk dat dit komt door het verschil in feedback tussen winst en gelijkspel, waardoor er sneller wordt geleerd als er wordt gewonnen. Ten tweede valt me op dat QLearningAI veel sneller dan GeneticAI2 van Daan leert tegen VoorkeurAI2. Als laatste, daarentegen, lukt het GeneticAI2 uiteindelijk wel om te winnen van VoorkeurAI2, terwijl QlearningAI blijft hangen in gelijkspel. Hopelijk is dit laatste geen voorbode voor de uitkomst als onze algoritmes het tegen elkaar opnemen…

Een van de grote verschillen tussen de voorkeurAI-algoritmen aan de ene kant, en lerende algoritmen zoals de GeneticAI2 en QLearningAI, is dat de voorkeurAI-algoritmen nooit van tactiek wisselen. Zodra de QlearningAI dus de beste strategie heeft bepaald tegen een VoorkeurAI, zal hij die altijd blijven uitvoeren. Echter, als een lerend algoritme, zoals GeneticAI2, merkt dat een andere strategie beter is, past hij zich aan. Als een resultaat hiervan, zullen de q-waarden van QLearningAI zich zo aanpassen dat ook deze van strategie veranderd. Zoals je begrijpt is mijn voorspelling dat we ons de hele tijd aan elkaar zullen aanpassen. We gaan het meemaken, alleen nog niet in de volgende blog, want dan mengt ook Roelof zich in de strijd. Roelof, je hebt nog één maand!

Leren programmeren (duel)leren (deel 2)

Leren programmeren (duel)leren (deel 2)

Mensen neigen nog vaak het idee te hebben dat de generatie die na hun komt, minder is dan hun eigen generatie. Misschien is dat toevallig voor jouw generatie wel waar, maar over het algemeen wordt de mensheid gemiddeld met de generaties, slimmer, sterker, sneller en ouder. Tenminste dat lijkt toch redelijk evident als je naar bijvoorbeeld wereldrecords kijkt, of naar het feit dat ik voor dit blog een computer zelf heb laten leren om boter-kaas-en-eieren te spelen, dat was een paar generaties geleden toch ondenkbaar. Dat de volgende generatie beter presteert dan de vorige is ook meteen hoe ik dat heb gedaan. In deel 2 van leren duelleren ga ik het hebben over een genetisch algoritme. De nieuwe bots kun je vinden op de volgende link: http://undercover.horse/tictactwo/

Maar eerst even een stukje administratie. Uit de reacties op mijn vorige blog begreep ik dat velen van jullie dachten dat Marlies deel 2 zou schrijven. Zoals jullie nu merken is dat niet het geval. Het oorspronkelijke plan was dat ik in dit deel iets meer uitleg zou geven over mijn algoritme, Marlies over haar algoritme, en dat ik dat dan aan elkaar zou knippen en plakken met hier en daar een stukje begeleidende tekst. De planning heeft alleen wat last gehad van mooi weer, vakantie en sociale verplichtingen, die niet in alle gevallen verplicht waren. Hierdoor is Marlies’ algoritme achterin de queue gekomen (dat is een briljant woordgrapje, maar je zult hem pas na Marlies’ blog snappen, maar geloof me, briljant). Dat betekent dat als je hier was voor het stukje van Marlies, dat ik je helaas danig (kijk ook een briljant woordgrapje, maar hier is dan weer geen voorkennis voor nodig) teleur moet stellen. Marlies schrijft deel 3, en dan zullen we dus de algoritmes op elkaar los laten, maar vandaag dus eerst deel 2: Survival of the fittest: kunstmatige selectie en intelligentie.

Charles Darwin, bij sommige misschien wel bekend, onderscheidt in zijn boek ‘on the Origin of Species’ (1859) twee soorten selectie die de evolutie aandrijven. Natuurlijke selectie, zoals het in de natuur gaat, en kunstmatige selectie zoals de mens dat doet bij bijvoorbeeld dure hondenrassen. Beide staven ze echter op dezelfde genetische principes. De ‘beste stukjes’ blijven over, en de ‘slechtste stukjes’ genetisch materiaal sterft langzaam af. Wat iets een goed stukje maakt is zeker in de biologie nogal een rekbaar begrip, maar heel kort door de bocht is dat hoe het werkt.

Dat idee wordt in de kunstmatige intelligentie geïmplementeerd middels een genetisch algoritme. Een genetisch algoritme werkt volgens volgend principe:
– Je begint met een zwik ‘bots’ met verschillende eigenschappen
– Je laat de bots los in de wereld waarin ze moeten overleven
– Je geeft de bots een score (de zogenaamde fitness score) aan de hand van hoe goed ze het doen
– Je laat de bots met een lage fitness score uitsterven, en die met een hoge fitness score laat je zichzelf voorplanten
– Bij het voortplanten laat je de bots muteren
– Zodra de huidige generatie voldoet aan je eisen stop je met het proces en de bots die je dan overhebt hebben de ‘juiste’ waardes.
Dat principe werkt niet helemaal geweldig met mijn boter-kaas-en-eieren spelletje, maar omdat volgens mij een genetisch algoritme een stuk makkelijk uit te leggen is dan bijvoorbeeld een neuraal netwerk, heb ik wat dichterlijke vrijheid toegepast en ga ik jullie laten zien hoe dat werkt.

Eerst kies ik een zwik aan mogelijke spel verlopen. Een mogelijk spelverloop is bijvoorbeeld [4, 8, 0, 6, 7, 2, 1, 3, 5]. In dit spelverloop kiest speler 1 als eerst vakje 4, vervolgens kiest speler 2 vakje 8, dan speler 1 vakje 0, etc. De volgende afbeelding laat zien welk vakje welke is:

Boter-kaas-en-eieren experts zullen direct gezien hebben dat nadat speler 1 vakje 1 heeft gekozen hij 3 op een rij heeft (1,4,7) en dat de opties die daarna komen dus helemaal niet meer kunnen. Maar onze kunstmatige intelligentie is geen boter-kaas-en-eieren expert, sterker nog, hij kent de spelregels niet, zover hij ‘weet’ is dit een geldig spelverloop. De manier waarop ik de begin set maak is al volgt: Ik bereken alle mogelijkheden waarin de getallen 0 tot en met 8 in een volgorde kunnen staan (dat zijn er 362880) en dan geef ik elke combinatie een kans van 30 procent om in de begin set te komen. Vervolgens kopieer ik die set zodat ik 2 sets van ongeveer 100.000 spelverlopen heb. Eentje voor wanneer de AI begint, en eentje voor wanneer de tegenstander begint. Dit alles gebeurt voordat er een zet is gedaan, dus mogelijk dat je computer even bezig is als je een geneticAI speler kiest.

Vervolgens kijk ik naar het huidige spelverloop. Maak ik een verzameling van alle spelverlopen die voldoen aan het huidige spelverloop, en kies een willekeurige bot uit. Ik neem de volgende zet uit dat spelverloop en kies die. Als voorbeeld stel we zitten in het begin van het spel en de tegenstander heeft vakje 2 gekozen. Dan kijk ik in mijn verzameling met spelverlopen waar de tegenstander begint en daar zie ik 3 spelverlopen die beginnen met een 2:
[2, 8, 0, 6, 7, 4, 1, 3, 5] en [2, 4, 8, 0, 6, 7, 1, 3, 5] en [2, 8, 6, 0, 7, 4, 1, 3, 5]
Daar kies ik er willekeurig eentje van, bijvoorbeeld de eerste, de zet die ik dan ga zetten is de 8. De tegenstander is dan weer en kiest de 6. Ik ga opnieuw kijken welke spelverlopen ik nog heb. Het spel verloop is nu [2, 8, 6] waar ik net spelverloop 1 had gekozen kan dit nu niet meer, alleen spelverloop 3 is nu nog geldig, dus kies ik die, en zet ik de 0.

Dat proces herhaal ik tot dat het spelletje me vertelt dat het spel voorbij is. Zodra het spel afgelopen is, geef ik het huidige spelverloop een fitness waarde. 1 als ik heb gewonnen, 0 als ik gelijk heb gespeeld, en -1 als ik heb verloren.

Zo speel ik een aantal spelletjes, tot dat ik er een X-aantal heb gespeeld. Nu is het tijd voor een nieuwe generatie. Omdat er ik een heleboel spelverlopen nog niet heb gespeeld en die dus nog geen fitness score hebben laat ik die ongemoeid. Ik kijk alleen maar naar de spelverlopen met een negatieve fitness score, en ik wissel de laatste zet die ik heb gemaakt om met een willekeurige andere zet. Op basis van deze mutaties heb ik een nieuwe generatie. Dit blijf ik herhalen tot er geen spelverlopen meer zijn met een negatieve fitness waarde.

Iedereen die al naar de nieuwe bots heeft gekeken zal zijn opgevallen dat er 2 versies zijn. GeneticAI1 en geneticAI2, het verschil zit hem in hoe de mutatie werkt. In versie 1 wordt de zet verwisseld met een willekeurig andere zet. In versie 2 wordt er een lijst bijgehouden van spelverlopen met een positieve fitness score. Bij de mutatie wordt het spelverloop dat gemuteerd wordt vergeleken met een spelverloop met een positieve fitness code en wordt er alleen verwisseld met een zet die niet in het spelverloop met de positieve fitness score zit. Voorbeeldje? Voorbeeldje: Spelverloop waarbij de AI begint dat gemuteerd moet worden is: [4, 8, 0, 5, 6, 2, 1, 3, 7], spelverloop met een positieve fitness score: [4, 8, 0, 5, 2, 6, 1, 7, 3]. Het spelverloop heeft verloren na zet 6, zet 6 moet dus verwisseld worden met een andere zet. In versie 1 had dat elke zet kunnen zijn, en had je dus bijvoorbeeld spelverloop [6, 8, 0, 5, 4, 2, 1, 3, 7] kunnen krijgen. In versie 2 mag dat niet omdat de 4 in het winnende spelverloop op dezelfde plek zit, er mag daar alleen met de 2, 7 of de 3 gewisseld worden.

Nu hoor ik sommige van jullie denken: “Ik vraag me af hoe dat er in code uit ziet”, sommige andere hoor ik denken: “Dit is me al vaag en ingewikkeld genoeg, ik hoop niet dat hij ook nog code laat zien”, weer sommige andere: “Hmm ik heb honger, ik vraag me af of er nog iets lekkers in de kast ligt” en één iemand: ”Jemig wat een verhaal, moet ik ook zo’n enorm verhaal aan elkaar ratelen?“. Voor groep 4 heb ik een geruststellende mededeling: Nee Marlies, natuurlijk niet. Aan groep 3 zou ik adviseren gewoon even in de kast te kijken, het geheel is al complex genoeg voor op een volle maag, op een lege maag zou ik het iedereen afraden. Voor groep 2, geen zorgen als ik de code ga bespreken zitten we hier morgen nog. Voor groep 1 heb ik dan nog wel een klein beetje goed nieuws, je kunt de code zelf bekijken op respectievelijk http://undercover.horse/tictactwo/geneticAI.js en http://undercover.horse/tictactwo/geneticAI2.js en in versie zit nog wat extra commentaar zodat het hopelijk redelijk te volgen is. Ook zie je dan nog dat er een truc in zit voor als een spelverloop niet bestaat. Mocht je nou desondanks nog vragen, suggesties of opmerkingen er over hebben, mail me gerust.

Leuk zo’n kunstmatige intelligentie, maar werkt het überhaupt wel, en wat heb je er eigenlijk aan? Goede vragen, al zeg ik het en stel ik ze zelf. Nou heb ik het algoritme tijdens het schrijven van dit blog laten spelen tegen voorkeur2 en de voortgang een beetje bijgehouden, en dat ziet er als volgt uit:

In het begin werden de meeste spelletjes verloren. Tegenover 50 verloren spelletjes stond 1 gewonnen spel en 10 gelijkspellen. Dat was te verwachten, het is een lerend algoritme, en leren kost tijd. Dat zie je ook mooi terug in de verdere verloop van de spellen, vooral in het aantal gelijkspellen. Voor wie het zich niet meer uit het vorige blog kan herinneren, voorkeurAI2 gebruikt altijd dezelfde volgorde van zetten, maar als hij een kans ziet om te winnen of een verlies te voorkomen doet hij dat. Het is voor het algoritme dus makkelijker om gelijk te spelen, en daar wordt hij ook niet voor bestraft, immers alleen spelverlopen met een negatieve fitness score worden gemuteerd. Maar het algoritme gaat ook steeds meer winnen, eerst was het tegenover 50 verloren spellen 1, op het laatst is het tegenover 7 verloren spellen 1. En uiteindelijk zal het algoritme vaker winnen dan verliezen

Het algoritme werkt dus, het leert, maar wat heeft dat voor zin? Zoals ik in het vorige blog al zei, voor dit specifieke voorbeeld niet zo veel. Het MiniMax-algoritme is snel genoeg om alle mogelijke zetten te voorzien en geeft dus altijd de beste zet terug. Toch wint het nooit van voorkeurAI2 omdat het ervan uitgaat dat voorkeurAI2 de best mogelijk zet gaat doen, terwijl deze dat niet altijd doet. Echter verliest MiniMax nooit, wat een duidelijk voordeel heeft. Maar ondanks dat het in dit voorbeeld niet heel zinvol is kan je er wel iets leuks aan zien. Ik heb het algoritme niks uitgelegd van de spelregels. Het enige wat het van tevoren ‘weet’ is dat je alleen maar een leeg vakje mag kiezen. Vervolgens vertel ik het zodra hij verloren, gewonnen of gelijk gespeeld heeft, maar meer niet. Maar het MiniMax-algoritme moest weten wat de waarde van een zet was, en dus moest weten wanneer er gewonnen zou worden, kent hij impliciet de spelregels. Ook voorkeurAI2 weet dat hij drie op een rij moet krijgen en zijn tegenstander niet. Je kunt een genetisch algoritme dan ook uitstekend gebruiken als je zelf het antwoord niet, of niet precies weet.

Dat is de grote kracht van kunstmatige intelligentie, het kan dingen leren die je zelf niet weet. Hoewel we nog niet bang hoeven te zijn voor filmscenario’s als Skynet uit Terminator of WarGames (Shall we play a game?), omdat kunstmatige intelligenties heel erg specifiek één ding leren, worden ze wel heel goed in dat ene specifieke ding. Er is daarom niemand meer die kan winnen van de beste kunstmatige intelligenties met schaken, jeopardy en sinds kort ook GO. Maar al die rekenkracht kan je natuurlijk ook voor praktischere dingen inzetten. Zo gaat er een bekende anekdote dat de Amerikaanse supermarktketen Target alle verkopen van klanten bij hield en een algoritme uit al die data  vast liet stellen of de klant zwanger was of niet, en ze op basis daarvan kortingsbonnen stuurde voor baby artikelen. Op het laatst was het algoritme zo goed dat het in sommige gevallen eerder wist dat een vrouw zwanger was dan de vrouw zelf. Helaas blijkt deze anekdote niet waar, het algoritme is opgesteld door een statisticus en was niet zelflerend, en er gaan nog wel geruchten dat vaders er door Target coupons achter kwamen dat hun dochter zwanger was, maar in hoeverre dat waar is, is ook nog maar de vraag. Maar dit is wel iets dat prima met een KI-algoritme gedaan had kunnen worden.

Je zult steeds meer te maken krijgen met kunstmatige intelligenties, zelfs als je het zelf niet door hebt. Bijvoorbeeld de video’s die YouTube je aanraadt om te kijken, daarvan weten de mensen bij YouTube zelf niet op basis waarop dat gebeurt, dat zit allemaal verwerkt in een kunstmatig intelligent algoritme. Dat klinkt heel spannend, maar ik hoop dat ik met dit blog heb laten zien, dat het allemaal geen magie is. Tenminste volgens mij is het geen magie, ik weet natuurlijk niet wat mijn tegenstander in de strijd gaat gooien. Marlies?

Leren programmeren (duel)leren (deel 1)

Leren programmeren (duel)leren (deel 1)

Nu ik inmiddels bezig ben met mijn 3de blog, is het misschien wel handig om uit te leggen wat het overkoepelende idee achter de blogs is. Trouwe lezers zullen inmiddels de gelijkenissen in de titel zijn opgevallen. Wees gerust, ik heb niet de illusie dat ik met een paar blogs van mijn lezers software developers kan maken. De titel is dan ook niet leren programmeren. Wat ik wel probeer, waarschijnlijk met afwisselend succes, is het idee van programmeren wat minder mysterieus te maken. In deel 2 van deze blog hoop ik daar nog een stapje bovenop te doen, en uit te leggen hoe kunstmatige intelligentie werkt. In een poging om dat geen saaie lap tekst te maken heb ik de hulp ingeroepen van één van mijn collega’s, Marlies. We gaan allebei een ‘kunstmatige intelligentie’ schrijven en die nemen het dan tegen elkaar op in een potje boter-kaas-en-eieren.

Voordat het echter zover is eerst deel 1: boter-kaas-en-eieren.
Voordat de bots voor deel 2 geschreven kunnen worden, is er het spel boter-kaas-en-eieren nodig waarmee de bots kunnen communiceren. Dat spel kun je hier spelen: tictactoe en als je wilt kan je de code voor het spelletje hier vinden: tictactoe.zip. Ik denk dat iedereen de regels van het spel wel kent, maar voor de vorm, en omdat het vrij simpel is, leg ik het nog een keer uit. Er zijn 2 spelers, elke speler mag om de beurt een vakje kiezen, dat is voor de rest van het spel zijn vakje. Wie het eerst 3 vakjes op een rij heeft (horizontaal, verticaal of diagonaal) wint. Zijn alle vakjes bezet en heeft geen van beide 3 op een rij, dan is het gelijkspel.

Op dit moment zijn er 6 bots die je kan kiezen: Human, RandomAI, VoorkeurAI, VoorkeurAI2, VoorkeurAI3 en MinmaxAI. Als je human kiest dan moet je zelf een vakje kiezen als je aan de beurt bent, als je een bot kies doet die een zet. Voordat ik omschrijf wat de bots doen en hoe ‘goed’ ze zijn is het het leukst als je zelf het spelletje speelt tegen de verschillende bots en kijkt of je de tactiek die ze gebruiken kan ontdekken, en welke vervolgens het succesvolst is. Ik wacht wel even.




Klaar? Ok, mijn verwachting is dat je van de RandomAI sowieso hebt kunnen winnen maar niet van MinmaxAI. Ik zal kort toelichten hoe de verschillende bots werken.

RandomAI
RandomAI is de simpelste van de bots, de bot krijgt het huidige speelbord binnen, kijkt welke vlakjes beschikbaar zijn en kiest er daarvan willekeurig eentje. Tegen de random bot is het makkelijk om expres te verliezen of te winnen, maar verdacht lastig om gelijk te spelen, terwijl als je een beetje goed bent in het spelletje dat tegen een menselijke tegenstander eigenlijk altijd de uitslag is.

VoorkeurAI
VoorkeurAI is niet veel complexer dan RandomAI, deze bot heeft een vaste voorkeur voor welke vakjes hij wil hebben. Hij gaat deze voorkeur af en zodra er eentje beschikbaar is, claimt hij die.
Zijn voorkeur is als volgt:

Voor een simpele tactiek is dit helemaal nog niet zo slecht en je zal zien als je RandomAI tegen VoorkeurAI laat spelen dat VoorkeurAI meestal wint. Zelf zul je, als je dit weet echter makkelijk kunnen winnen, je kunt immers altijd de onderste rij (in de afbeelding dus 3,5,8) kiezen en winnen.

VoorkeurAI2
VoorkeurAI2 is al iets beter dan de andere 2 bots, hij heeft namelijk een win/verlies algoritme, als hij het spelletje kan winnen door een vlakje te kiezen, kiest hij deze. Zo niet, dan kijkt hij of de tegenstander kan winnen door een vlakje te kiezen, en zo ja dan kiest hij deze. Zo niet, dan valt hij terug op de tactiek van zijn kleine broertje en kiest hij de eerste lege op basis van dezelfde voorkeursvolgorde. Deze wint alles van VoorkeurAI en doet het een stuk beter tegen RandomAI. Je zult zien dat je ook van deze bot nog wel kunt winnen, maar je moet wel van te voren een goede tactiek bedenken!

VoorkeurAI3
VoorkeurAI3 is een beetje een instinker, als je er tegen gespeeld hebt, zal je waarschijnlijk het gevoel hebben dat hij iets beter is dan 2, ook al weet je niet precies waarom. In werkelijkheid is deze bot hetzelfde als VoorkeurAI2, met als enige verandering dat met een trucje hij er iets langer over doet om een oplossing uit de voorkeursvolgorde te halen.
Hier ga ik straks op verder, maar eerst laat ik Marlies de werking van de volgende bot uitleggen, die heeft zij namelijk gemaakt. Deze bot is de reden waarom we eigenlijk voor dit spelletje geen kunstmatige intelligentie nodig hebben. Er is namelijk een beter manier: Het minmax-algoritme.

MinmaxAI
De MinmaxAI bot gebruikt het minmax-algortime. Om dit algoritme te kunnen gebruiken, is er een aantal eigenschappen die een spelletje moet hebben. De eerste is dat jij wilt winnen, maar waarom speel je anders ook een spelletje, en dat je tegenstander ook wilt winnen, maar waarom speelt hij anders ook een spelletje, en dat de winst van de één betekent dat de ander verliest. Daarnaast is het nodig om ieder mogelijk vervolg van het spelletje te kunnen bepalen (dat is bij dit spel vrij makkelijk omdat het er niet veel zijn, alleen de eerste zet kost even wat tijd om uit te rekenen), en is het nodig om een waarde te kunnen hangen aan het einde van het spelletje.

Op het moment dat hij een zet moet doen, bedenkt het minmax-algoritme voor iedere mogelijke zet wat hiervan het gevolg is voor het vervolg van het spelletje. Op basis van dit vervolg, heeft een zet een bepaalde waarde. Zo heeft winst een waarde van +10, verlies een waarde van -10, en gelijkspel een waarde van 0. Daar waar jij probeert om deze waarde zo hoog mogelijk te maken, of dus te maximaliseren, probeert jouw tegenstander juist het omgekeerde te doen; oftewel te minimaliseren.

Op deze manier kan je ook voor een zet die er niet voor zorgt dat het spelletje is afgelopen een waarde bepalen. Als het spelletje nog niet is afgelopen, kan je namelijk beredeneren wat de tegenstander zal gaan doen, namelijk proberen om op een uitkomst met een zo laag mogelijke waarde uit te komen. Als hij echter het spelletje ook niet afmaakt, is het weer jouw beurt, en probeer jij juist weer op een zo hoog mogelijke waarde uit te komen. Als jij dan het spelletje niet afmaakt … enfin, je begrijpt het idee.

Echter missen we nu nog een essentieel onderdeel. Op dit moment heeft het winnen in de volgende zet dezelfde waarde als het winnen in een zet over vier beurten, namelijk +10. Daarnaast is de volgende beurt verliezen evenveel, of eigenlijk even weinig, waard als verliezen over vier beurten, namelijk -10. Tijd voor een voorbeeldje, als jij al twee vakjes op een rij hebt, is het niet zo handig om niet het derde vakje erbij te kiezen. Dat derde vakje kiezen, moet dus eigenlijk een hogere waarde hebben dan niet dat derde vakje kiezen. Ander voorbeeldje, als de tegenstander vakjes op een rij heeft, is het niet zo handig als je niet zelf het derde vakje kiest, anders wint hij namelijk zodra hij aan zet is. Oftewel, wel dat derde vakje kiezen moet een hogere, of minder lage, waarde hebben dan niet dat derde vakje kiezen.

Om hier rekening mee te houden, wordt de waarde van de uitkomst niet alleen bepaald door de uitkomst zelf, maar ook door het aantal beurten dat het nog kost om tot deze uitkomst te komen. Winnen in de volgende beurt krijgt dus een waarde van +10, terwijl winnen over vier beurten de waarde van +10 – 4 krijgt. Het omgekeerde is het geval voor verliezen. De volgende beurt verliezen is -10 punten, en pas over vier beurten verliezen heeft een waarde van -10 + 4. Hierdoor zal het algoritme winnen wanneer dat kan, en zorgen dat het niet de volgende beurt verliest.

Dankje Marlies voor deze heldere uitleg.
Deze tactiek maakt het minmax-algoritme onverslaanbaar. Immers hij berekent alle mogelijkheden, gaat uit van het scenario dat zijn tegenstander net zo goed is als hij en kiest dan de beste zet. Hoewel we hier een algoritme hebben dat altijd de beste zet doet, zal er niet zo snel iemand zijn die het kwalificeert als een intelligent algoritme. Maar als het maken van de slimste beslissing geen intelligentie is, wat dan wel?

Groot voordeel, daarover is geen algemene consensus, dus je mag zelf kiezen wat je intelligent noemt en als iemand het daar niet mee eens is, komt dat omdat hij/zij zelf niet intelligent genoeg is. Ik hoop dat je tegen voorkeurAI2 en 3 hebt gespeeld, en mijn voorspelling dat je het gevoel had dat 3 slimmer aanvoelde dan 2 uit is gekomen. Het illustreert namelijk iets mafs. Hoewel het niet zo is, lijkt de ene bot slimmer dan de andere. Dat kan door twee dingen komen:

1. De naam: Omdat voorkeurAI2 duidelijk slimmer is dan 1, zal 3 nog wel weer beter zijn. Dit is een hele menselijke vergissing waar veel reclamemakers graag gebruik van maken. Dit is ook de reden waarom we over een paar jaar scheermesjes hebben met acht mesjes, met namen als elemental fusion power daimond stealh razor deluxe hybrid. Want stom genoeg werkt het.

2. Het algoritme doet er langer over om een ‘moeilijke’ beslissing te nemen. Dit is iets wat je ziet gebeuren en je maakt een aanname waarom dat zo is: Het algoritme moet langer nadenken/rekenen over de keuze. Dat is echter niet zo, wat er in werkelijkheid gebeurt is dat het algoritme een willekeurig getal neemt tussen de 0 en 1, en als dat groter is dan 0,05 slaat hij een cyclus over. Het spelletje werkt met ongeveer 60 cycli per minuut, en dus duurt het even voordat hij daadwerkelijk zijn zet kiest.

Door ‘na te denken’ over de zet lijkt het algoritme menselijker, en wordt daarom sneller gezien als intelligent. In 1950 bedacht briljant wiskundige Alan Turing de Turing test. De Turing test werkt grofweg als volgt: Twee mensen voegen je toe op WhatsApp, geen van beide wil (video)bellen en je mag met beide 10 minuten appen. Na die 10 minuten moet je zeggen welk van deze 2 mensen ook echt een mens is en welke stiekem een computer. Als maar genoeg mensen het verschil niet kunnen onderscheiden tussen de mens en de computer dan is de computer intelligent.

Dat blijkt nog helemaal niet zo makkelijk, want als je iemand vraagt wat 23598 keer 123987 is en hij/zij komt direct met het goede antwoord, dan gaat al snel het vermoeden dat hij te goed kan rekenen en dus een computer is. Dus worden de bots trucjes aangeleerd, ze doen langer over rekensommen en maken bewust fouten. Maar dan ben je er nog lang niet, we zijn als mensen misschien niet zo goed in hoofdrekenen, het voeren van een conversatie kunnen we over het algemeen wel een stuk beter dan een computer. Er zijn veel projecten die deze uitdaging aangaan een voorbeeld is www.cleverbot.com. Chatten met cleverbot voelt als een discussie met mijn bijna 3-jarige nichtje, die als je vraagt of ze 2 handen heeft, heel stellig zegt: “Nee 3!”, terwijl ze evenveel vingers ophoudt als ze zondag jaren oud wordt. Nou klinkt dat niet zo bijzonder, maar dat betekent dat, volgens Turings redenatie, cleverbot de intelligentie heeft van een bijna 3-jarig meisje.

De Turing test wordt door veel mensen nog steeds gezien als de graadmeter voor intelligentie, maar hoewel we dat nog niet gehaald hebben vinden veel mensen het het doorstaan van de Turing niet genoeg om iets intelligent te noemen. Die vinden dat een intelligentie zou moeten kunnen functioneren in de echte wereld.
Nou wil ik niet voor Marlies praten, maar dat gaat mij wat te ver voor een blog. Wat wij gaan doen is een kleine doch zeer belangrijke subset van intelligentie, leren. We gaan allebei een algoritme schrijven dat na het spelen van potjes steeds beter wordt. Idealiter begint de bot zo goed als RandomAI en eindigt hij zo goed als MinmaxAI. Ik weet niet hoe het met jou zit Marlies, maar ik vrees dat ik hem niet zo goed ga krijgen als MinmaxAI, aan de andere kant verwacht ik wel dat hij kan winnen van mijn nichtje, ook al is ze inmiddels 3 als het algoritme af is. Kan het algoritme daarom beter leren dan mijn nichtje? Of beter nog, is het intelligent? Dat mag je zelf beslissen. Ik ben allang blij als het niet genadeloos verslagen wordt door dat van Marlies.

Wil je zelf ook een bot maken? In de zip-file staat een dummyAI, die doet nu nog helemaal niets, maar als je dummyAI.js aanpast kan je hem wel alles laten doen wat je wilt! Dus mocht je na het vorige blog de smaak van het programmeren te pakken hebben, maak van het duel een 3-strijd, laat je met de andere bots als voorbeeld inspireren en maak je eigen bot. Dan kan je in het volgend blog kijken hoe die zich verhoudt tegen die van ons! Mocht je een bot maken, zou ik het superleuk vinden als je je oplossing mailt. Het meest leer je immers van elkaar.

Rest me nog de competitie heel veel succes te wensen. Marlies, je hebt tot het volgende blog, succes, je tijd gaat nú in!

leren programmeren proberen

leren programmeren proberen

In mijn vorige blog heb ik proberen uit te leggen dat programmeren eigenlijk niet zo moeilijk is, zolang je maar alle mogelijke gebeurtenissen voorziet en daar rekening mee houdt. Ik ben er vervolgens op gewezen dat als je geen idee hebt hoe je moet programmeren, dat je kan anticiperen wat je wilt, maar daar schiet je dan weinig mee op. Dit is natuurlijk een goed punt, en ik ga in dit blog dan ook op verzoek jullie leren programmeren. Het belangrijkste aan programmeren is het proberen, dus wil je het echt leren, doe dan gezellig mee.

Vandaag gaan we programmeren in JavaScript, waarom JavaScript hoor ik sceptici vragen. Omdat je alles om te programmeren in JavaScript al op je computer hebt staan, dus eigenlijk om het voor de lezer makkelijk te houden. We gaan vandaag een spelletje programmeren (in een poging de stof niet te droog te houden), de keus voor het spelletje is gevallen op Space Invaders, maar omdat ik geen DCMA-takedowns wil afroepen noemen we het: Orcado Invaders. Je kunt het eindresultaat alvast hier spelen: OrcadoInvaders Als je achter een computer zit kun je de pijltjes en het toetsenbord gebruiken, op je mobiel zou tikken op je scherm moeten werken. Het is overigens op je mobiel een stuk lastiger, dus ik zou aanraden achter een computer te gaan zitten, hetgeen voor het hele mee doen met het programmeren idee ook een heel stuk gaat helpen.

Voor iedereen die nu denkt: “Is het niet veel te moeilijk om uit het niets een spelletje als Orcado Invaders te maken?”. Ja, dat is het helaas inderdaad, maar niet getreurd ik heb al een ander leuk spelletje op het oog, namelijk “Raad het getal!”. Dat klinkt alleen een heel stuk minder stoer, dus ik ben begonnen met een onrealistische teaser, dat heb ik geleerd van de filmindustrie, werkt altijd. Maar om het goed te maken, gaan we een kunstmatige intelligentie maken die zelf het getal gaat raden, dat maakt toch wel weer wat goed toch?
Ok, genoeg gewauwel als inleiding, tijd om aan de slag te gaan.

Voor deze intro zijn de volgende vaardigheden als voorkennis benodigd:
– Het kunnen downloaden van een zip bestand
– Het kunnen uitpakken van een zip bestand
– Knippen
– Plakken
– Opslaan
– Verversen van een pagina
– Doorzettingsvermogen

Dat viel mee toch? Mocht je nog aan het twijfelen zijn of je wel genoeg doorzettingsvermogen hebt, als je nu nog leest zit je wat mij betreft in de veilige zone.

Om te beginnen heb ik een zip-bestandje gemaakt dat je hier kunt downloaden: starter pack Download dit zip bestand en pak het ergens uit. Ga naar de locatie waar je het uitgepakt hebt, hier vind je twee bestandjes “de_pagina.html” en “de_code.js”.

Als je dubbelklikt op de_pagina.html opent je internetbrowser, op de pagina staat vervolgens uitgelegd hoe je in de console komt. Volg die instructie en type in de console het volgende in: hoiConsole(); Druk op enter en de console zegt hoi terug, dat ziet er als het goed is ongeveer zo uit:

Gelukt? Mooi! Gaan we nu kijken wat ik voor bergen aan code als voorwerk heb moeten schrijven om dit te laten werken. Ga terug naar de map met bestandjes klik met je rechtermuisknop op de_code.js en kies: “Openen met” en kies uit de lijst Notepad (of een andere teksteditor) (eventueel moet je ergens op klikken om meer programma’s te krijgen als Notepad er niet direct tussen staat, maar daar kom je vast wel uit!)

Nu zie je de code die ervoor zorgt dat de console je terug groet. Dat stelt nog niet veel voor, ik zal uitleggen wat het doet.
function (dit geeft aan dat we een functie gaan maken, een functie is dat je kunt aanroepen en dat dan vervolgens een stuk code uitvoert)
hoiConsole (dit is de naam van de functie, die gebruik je om de functie aan te roepen)
() (tussen deze twee haakjes staan eventuele argumenten, kom ik straks op terug
{ (geeft aan dat hier de code van de functie begint)
return (code om aan te geven dat er iets terug moet worden gegeven, dit wordt terug gegeven aan de geen die de functie aanroept, in dit voorbeeld ben jij dat in de console)
"Hoi" (alles tussen aanhalingstekens is geen code maar tekst, omdat deze tekst achter return staat wordt hij terug gegeven)
; (geeft aan dat we het einde van een regel gehaald hebben, elke regel code wordt met een puntkomma afgesloten)
} (geeft aan dat hier de code van de functie stopt)

Dat is heel veel uitleg voor een heel klein stukje code, maar hopelijk allemaal nog niet heel ingewikkeld. Wat we nu gaan doen is samen de functie uitbreiden. Dat gaan we doen met een argument, ja ik kom er maar snel op terug voor dat je ze al weer vergeten bent. Argumenten kan je gebruiken om een functie iets mee te geven wat hij nodig heeft voor zijn code. We gaan aan de functie meegeven, wat hij terug moet geven, om dat te doen zet tussen de haakjes een x, en vervang de tekst “hoi” ook met een x:

function hoiConsole(x){
return x;
}

De x staat nu niet tussen aanhalingstekens, en is nu geen tekst meer maar code, hij zal nu de x teruggeven die hij in zijn aanroep mee heeft gekregen. Kom, we gaan het testen! Sla het tekstbestand op, en ververs de internetpagina (bijvoorbeeld met F5, of als het niet wil lukken sluit hem en open hem nog een keer). We moeten de functie nu iets anders aanroepen, de functie verwacht namelijk nu een argument. Probeer eens: hoiConsole(“Hoi”) dat geeft als het goed is dit:

Zo lijken we niet veel opgeschoten, dat konden we net ook al, maar we kunnen hem nu alles laten zeggen, kijk maar:

Ok slechte grapjes achterwege gelaten, we kunnen hem nu meegeven hoe we heten en dan groet hij ons persoonlijk terug:

Stel dat we een teruggroet robot aan het bouwen zijn, dan hoeft hij voor het teruggroeten natuurlijk alleen de naam te weten, hoi is altijd hetzelfde. Wat we dus gaan doen, we gaan hoi terug in de functie zetten, en dan plakken we de naam erachteraan:
function hoiConsole(x){
return “Hoi ”+x;
}

(Let op de spatie achter hoi, anders staat er straks HoiDaan) kijken wat hij doet:

Dat was nog niet zo lastig toch? Technisch gezien kan je nu al programmeren. Echter begint het nu pas leuk te worden, dus we doen nog een paar extra dingetjes, en dan kan je ook echt iets bouwen wat iets ‘doet’.
We kunnen ook meerdere argumenten meegeven aan een functie. Laten we een nieuwe functie maken, de oude mag je laten staan en daaronder mag je het volgende toevoegen:

function hoger(x,y){
if(x > y){
return "ja dat is hoger";
}else{
return "nee dat is lager"
}
}

We gaan eerst kijken wat dat betekent:
function hoger(x,y){ (dit ken je al, dit is een functie met de naam hoger en de argumenten x en y)
if(x > y){ (dit is een zogenaamd if-statement, als wat er tussen de haakjes staat waar is voert hij de code uit, anders niet)
return "ja dat is hoger"; (dit ken je al, geef tekst terug)
}else{ (het else-statement gebruik je indien wat tussen de haakjes van het vorige if-statement niet waar is, dan deze code uit te voeren, je ziet een else-statement dus nooit zonder if, andersom kan wel)
return "nee dat is lager"; (dit ken je al, geef tekst terug)
} (dit ken je al, einde van een blok code)
} (dit ken je al, einde van een blok code)
Als we nu de functie hoger(5,3) aanroepen, dan gaat het if-statement kijken of 5 groter is dan 3 (> is het groter dan teken) en zo ja geeft hij terug “ja dat is hoger”, zo niet, dan “nee dat is lager”. Zoals altijd gaan we dit proberen, dat is het idee van het geheel ?

En gelukkig, het klopt.
Mocht het nou niet werken, en je krijgt rode blokken met tekst zoals dit:

Controleer dan of je
– het bestandje de_code.js hebt opgeslagen
– de pagina hebt ververst
– nergens een typefout hebt gemaakt (programmeertalen zijn heel streng op je spelling)
Voor de zekerheid testen we ook de andere opties:

Trouwe lezers hadden het natuurlijk al geanticipeerd, als iets niet hoger is, hoeft het niet per se lager te zijn. We kunnen dat natuurlijk oplossen door de tekst te veranderen naar “nee het is niet hoger”, maar mooier is een extra check om te kijken of het niet toevallig gelijk is:

function hoger(x,y){
if(x > y){
return "ja dat is hoger";
}else{
if(x == y){
return "nee dat is gelijk"
}else{
return "nee dat is lager"
}
}
}

Wat je ook mag schrijven als:

function hoger(x,y){
if(x > y){
return "ja dat is hoger";
}else if(x == y){
return "nee dat is gelijk"
}else{
return "nee dat is lager"
}
}

Dat scheelt weer een paar haakjes ? Nu geeft de functie wel de juiste melding (vergeet het niet te proberen). Let op het dubbele = teken, we kijken of ze het zelfde zijn, als we een enkel = teken dan krijgt x de waarde y.
En we gaan al weer verder, in mijn vorige blog had ik het over delen, nu gaan we eerst vermenigvuldigen. Dat is in JavaScript vrij triviaal, je kan bijvoorbeeld zeggen 5*3, en dan krijg je terug 15, kijk maar:

Maar vandaag is het enige rekenteken dat we mogen gebruiken de plus. Gelukkig kan je vermenigvuldigen makkelijk omschrijven naar optellen, immers 5*3 is vijf keer een drie dus hetzelfde als: 3+3+3+3+3. Als we in JavaScript iets een aantal keer moeten doen, hebben we daar een aantal opties voor; we gaan de for-loop gebruiken. De for-loop werkt als volgt:

for(var i = 1; i<=x;i++){
//doe iets
}

Wat vertaalt naar:
for (geeft aan dat we een for-loop beginnen)
( (deze ken je al, begin van de argumenten)
var i = 1 (var staat voor een variable, de variable slaat voor ons een waarde op, de naam van deze variable is i, en de waarde is 1)
i<=x (we gaan door de code uitvoeren zolang de variable i kleiner of gelijk is aan de variable x (let op als je een argument meegeeft aan een functie is dat ook een variable))
i++ (Na elke keer dat je de code hebt uit gevoerd verhoog variable i met 1, dit kan je ook opschrijven als i = i +1 of i+=1)
) (deze ken je al, einde van de argumenten)
{ (deze ken je al, begin van de uit te voeren code)
//doe iets (de code die uitgevoegd gaat worden)
} (deze ken je al, begin van de uit te voeren code)

De for-loop heeft 3 argumenten, met het eerste kan je een variable aanmaken, met het tweede geef je een voorwaarde om het te doen (eigenlijk een soort if-statement) en het derde argument wordt na elke loop uitgevoerd. De blokken worden in een for-loop gescheiden door een puntkomma.

Ok, probeer zelf nu eens om de functie te schrijven. Ja je kan gewoon naar beneden scrollen, maar het hele idee van dit blog is dat je het zelf gaat proberen. Geef niet direct op, maar blijf ook niet te lang bezig, ook als je code niet werkt, als je er zelf over hebt nagedacht dan ben je al een heel stuk verder dan als je alleen doorleest. Bedenk wat voor stappen de code moet doen en schrijf dat stap voor stap op. Mocht je er niet uitkomen, lees eerst de hints!

Hint1:
Je hebt een extra variable nodig.

Hint2:
Vul in op de puntjes:
function keer(x,y){
var uitkomst = 0;
for(var i = 1; i <= ...; i++){
...........
}
return ...
}

lees verder

Hier komt de sidebar

Volg ons op

© Orcado B.V. | 1999 - 2018