15 september 2014

Exempel i Scratch: Mastermind

Cate gissar rätt på fyra försök

Här är ett litet mer avancerat exempel i Scratch där katten står för gissandet. Algoritmen är mer eller mindre tagen direkt från Wolfram Mathworld.

Genomgång




Manus till genomgång

Vi återanvänder spelplan och pjäsgrafik genom att remixa ett Mastermind från användaren djscope. Det projektet bygger på att katten rättar våra gissningar men det här projektet vänder på rollerna så det blir inte mycket återanvändning av någon kod.
Hur ska katten göra när den gissar?  För att hitta några bra idéer läser vi på litet om Mastermind i Wikipedia och Wolfram MathWorld.

En möjlighet är att börja med en kandidatlista som innehåller alla möjliga gissningar [kod från Scratch]

Vi väljer att ha 1122 som startgissning, i vårt fall röd-röd-blå-blå. Det är samma som i Knuths algoritm (länk).

När motspelaren har rättat vår startgissning, går katten genom kandidatlistan och använder uteslutningsmetoden. Anta att första kandidaten i listan är rätt svar. Skulle då vår startgissning ge samma facit? Om ja, så behåller vi första kandidaten som ett möjligt svar. Annars kan vi slänga första kandidaten och gå till nästa. På så vis går vi igenom hela kandidatlistan och har till slut slängt alla omöjliga gissningar. Kandidatlistan blir på så vis kortare hela tiden. Den har från början 64 = 6*6*6*6 = 1296 möjligheter och krymper för varje gissning typiskt med cirka 75%. För att öka spänningen :) låter vi katten berätta hur många möjliga gissningar den har kvar före varje ny gissning.

Som Cates nästa gissning tar vi första elementet av de som är kvar kandidatlistan.

Katten kommer att ge upp om listan blir tom. Det betyder att vi har svarat fel på någon av kattens gissningar.

Grovdesign i Scratch

I Scratchkoden använder vi signaler och några få globala variabler för att sköta uppdateringen av spelbrädet. (Sparat, Gissningens nummer), namn med VERSALER.
Vi klarar oss med den här spriteuppsättningen:
  • Cate: den svåraste delen med själva gissningsalgoritmen
  • Secret, där vi ställer in hemligheten som katten ska gissa. Spriten klonar sig själv. Det gör koden enklare än att ha fyra kopior med små kodskillnader.
  • Sparaknappen, som vi klickar på när vi ställt in hemligheten
  • Choice, där katten visar sin gissning. Spriten klonar sig själv för att hålla koden enklare.
  • Checker1 till Checker4, som vi klickar på för att betygsätta kattens gissning med blanka, vita och svarta markeringar. Här har jag valt att inte använda kloner eftersom katten behöver få reda på betyget, som den kan läsa ut av klädseln hos varje sprite. Alternativet hade varit att använda händelser eller en global variabel.

Mastermind: ett spel med fullständig information

Den här typen av spel där det går att överblicka »allt« brukar kallas för spel med fullständig information. Två andra exempel är luffarschack och vanligt schack, fast i fallet vanligt schack går det inte att praktiskt hålla reda på alla spelställningar eftersom det finns för många. Exempel på spel som inte har perfekt information är kortspel där spelarna gömmer sina kort för varandra.