Sqrubs
Een cross-platform Scrabble-analysebord dat een stelling van een screenshot of foto leest en er elke legale zet op vindt en rangschikt — gebouwd om je te tonen wat je miste, niet om je beurt voor je te spelen.
Niet uitgebracht — de tekst is het werkstuk.
Het probleem
De zet die je speelde is niet de zet die er lag.
Je speelt een partij uit, je verliest met negen punten, en ergens rond beurt zes lag er een bingo op je rekje die niemand aan tafel gezien heeft. Scrabble is een van de weinige spellen waar de beste zet een feit is — een eindig bord, een eindig rekje, een vaste woordenlijst — en waar een mens hem betrouwbaar niet vindt. Je kunt een schaakpartij achteraf overlopen en precies te horen krijgen waar het misging. Voor het bord dat je net hebt opgeborgen bestaat daar geen equivalent van.
Sqrubs is die nabespreking. Je zet de stelling op, je voert het rekje in, en het geeft je elke legale zet terug, gerangschikt op score. Het onderscheid waar het omheen gebouwd is, is dat het een analysebord is en geen assistent: het is voor de partij die voorbij is, zoals een schaakengine voor de partij is die voorbij is. Een solver die je midden in je beurt raadpleegt tegenover iemand die tegenover je zit, is een ander product met dezelfde code erin, en dat product wilde ik niet bouwen.
Wat ik koos
Flutter, gericht op Android, iOS, macOS, Windows en web vanuit één codebase, met Riverpod dat de staat van bord, rekje, woordenboek en solver vasthoudt — gekozen omdat zijn providers testbaar zijn zonder widgetboom, en het grootste deel van dit project logica is in plaats van schermen.
Het woordenboek is een meegeleverde asset — er verlaat niets het toestel en er is nergens netwerk voor nodig — bij het opstarten in een trie ingelezen. De solver doet ankergebaseerde zetgeneratie met kruiscontroles, de aanpak van Appel en Jacobson: zoek de lege vakjes naast gelegde stenen, bepaal voor elk daarvan welke letters legaal een kruiswoord zouden vormen, bouw prefixen naar links op uit het rekje, en breid dan naar rechts uit over het anker zolang de trie zegt dat een woord nog verder kan. Daarna hetzelfde verticaal. De score past vermenigvuldigers alleen toe op nieuw gelegde stenen, telt elk kruiswoord op dat de plaatsing maakt, en telt er vijftig bij als het rekje leegloopt.
Wat ik verwierp
Permutaties van het rekje. De voor de hand liggende eerste solver: genereer elke schikking van hoogstens zeven stenen, probeer die op elke positie, hou over wat het woordenboek aanvaardt. Het klopt, het is een regel of vijftien, en het verzet een enorme hoeveelheid werk om te ontdekken dat geen enkel Nederlands woord met "qz" begint. De trie is wat daar snoeien van maakt — op het moment dat geen enkel woord een prefix voortzet, is de hele tak weg — en de ankerpas is wat verhindert dat er posities bekeken worden die sowieso geen legale plaatsing konden zijn.
Een hashset van woorden. Een set beantwoordt "is dit een woord" in constante tijd en beantwoordt verder niets, en zetgeneratie is geen lidmaatschapsvraag. Elke stap ervan vraagt of een prefix nog ergens heen kan, en dat is de ene vraag die een set niet kan beantwoorden en de enige vraag waar een trie voor bestaat. De trie kost meer geheugen voor dezelfde woordenlijst, en dat is de hele ruil.
Een GADDAG. Het serieuze antwoord, en wat een competitie-engine gebruikt: elke rotatie van elk woord opslaan zodat uitbreiding vanaf een anker beide richtingen op gaat zonder aparte linkerdeel-pas. Het is ruwweg vijf keer het geheugen van een gewone trie, in ruil voor snelheid op een probleem waarvan de gebruiker een mens is die op een lijst wacht. Ik geef liever een seconde uit dan vijf keer de voetafdruk op elke telefoon waarop de app draait.
Oplossen op de main thread. De zetgeneratie draait in een isolate. Een solve die de UI laat haperen leest als een kapotte app in plaats van een drukke.
Wat het kostte
Een stelling invoeren was het trage deel, en de solve is ogenblikkelijk. Een bord halverwege de partij is dertig-en-nog-wat taps door een dialoog per vakje voor je een antwoord krijgt, wat te doen is wanneer je één interessante stelling naloopt en vervelend op het moment dat je een hele partij wilt overlopen. De oplossing was altijd het bord fotograferen, en de eerste versie van deze pagina noemde dat een ander project. Het werd het volgende.
Je geeft Sqrubs een screenshot of een foto — met de camera, uit de galerij, of op Android rechtstreeks gedeeld vanuit een andere app — en het leest er het bord en het rekje van af. Een screenshot vindt zelf zijn hoeken; een foto krijgt vier grepen om te verslepen, met een vergrootglas en het raster van vijftien bij vijftien er live overheen getekend. Het beeld wordt recht getrokken tot een vierkant en daarna vastgezet op de rasterlijnen die het echt heeft, zodat een hoek die een derde vakje naast zit nog altijd goed valt. Welke vakjes een steen dragen, wordt op pixels beslist voor er iets gelezen wordt: een steen is een lettervorm op een vakje in steenkleur, en dat houdt het label dat op een premievakje gedrukt staat tegen om als twee letters binnen te komen. De tekstherkenning van ML Kit leest de letters, op de telefoon zelf, dus ook de foto gaat nergens heen; ze leest de twijfelachtige opnieuw op een vel met genormaliseerd contrast, en wat ze dan nog niet kan lezen, gaat naar een vormvergelijking met letters gerenderd uit een schreefloos en een schreeflettertype.
Wat ik eerder schreef klopte over het gevaar: één verkeerd gelezen vakje levert een zelfverzekerd fout antwoord op. Dus vertrouwt de lezer zichzelf niet. Elk woord dat hij vindt, horizontaal en verticaal, gaat door het woordenboek van de solver, met het aantal stenen en de puntwaarden ernaast gecontroleerd, en van een ongeldig woord mogen tot drie onzekere letters samen variëren tot het een woord is. Een letter die met zekerheid gelezen is, wordt nooit veranderd, een gok wordt alleen ingevuld als het de enige letter is die past, en als de meeste woorden falen houdt de lezer op met corrigeren en stelt hij voor dat het bord in de andere taal is. Wat dan nog twijfelachtig is, verschijnt omlijnd om met een tap te verbeteren, met de foto een knop verder. Op twaalf testborden — zes synthetische, vier screenshots uit andere Scrabble-apps en twee foto's van een echt bord — leest hij 96,5% van de letters ruw en 98% na validatie, 175 van de 177 op de echte screenshots, in één tot drie seconden.
Gratis is het niet. De lezer draait alleen op Android en iOS: ML Kit heeft geen desktop- of webversie, dus op drie van de vijf platformen is de knop er niet en blijft een stelling dertig taps. Een foto die te schuin genomen is, verschuift verhoogde stenen door parallax uit hun vakje, en een fysieke blanco toont geen letter, dus die wordt alleen afgeleid als er maar één letter past. En het verschuift een lijn die deze pagina trekt. Een screenshot van een online partij, rekje inbegrepen, is precies de stelling die je midden in je beurt zou willen: of Sqrubs een analysebord of een assistent is, hangt nu af van wanneer je het gebruikt, niet meer van wat het kan. Ik heb het toch gebouwd, omdat de nabespreking waarvoor het bestaat die is waarvoor een hele partij ingevoerd moet worden, en niemand doet dat met de hand.
Frans toevoegen was geen vertaalklus. De strings van de interface zijn een bestand; het spel niet. Frans Scrabble heeft zijn eigen letterverdeling, zijn eigen puntwaarden en zijn eigen omgang met accenten, wat betekende dat het stenenmodel zelf taalafhankelijk moest worden in plaats van een vaste tabel. Dat is het soort ding dat je in fase tien ontdekt en in fase één had moeten weten.
Blanco stenen kosten meer dan wat dan ook van hun formaat: elke blanco vermenigvuldigt de zoekruimte met zesentwintig en levert nul punten op.
Het resultaat
Het werkt, op de tien fasen van het plan, op vijf platformen, in twee talen, met tests achter elke fase, en het leest nu een bord van een foto. Het is nog niet uitgebracht, maar de afstand tussen die twee woorden is veranderd. Wat ertussen stond was nooit code: een icoon, een privacyantwoord, en een woordenlijst waarvan ik de licentie kan aanwijzen — de bekende toernooilijsten zijn niet de publiek-domeinbestanden waarvoor ze worden aangezien. Het icoon is getekend, het privacybeleid staat online, en de Engelse lijst is ENABLE met de lijst van Wordnik ernaast, die allebei zeggen wat ze zijn. Wat overblijft is Googles beoordeling van de Play Store-pagina. Als die erdoor is, krijgt deze alinea in de plaats een link.