Etikettarkiv: Spel

2016, Blogg

Role-playing: Bara roligt, eller också vettigt tidsfördriv?

Lämna en kommentar

Efter januari-måmö hade flera spektrumiter möjligheten att delta i ett bordsrollspel, men alla var inte riktigt bekanta med vad ett rollspel är. Vad är alltså ett rollspel för något och vad betyder RPG?

RPG är en engelsk förkortning för Role-Playing Game, dvs ett rollspel. Att spela rollspel är något som många anser vara ett roligt tidsfördriv, fastän rollspel faktiskt också kan ha nyttigare roller, exempelvis i pedagogiskt syfte då man vill utveckla individer och grupper att hantera olika situationer. Även i psykoterapi används rollspel för att stärka en individs psyke och för att få två parter att förstå varandra bättre. Men vad innebär det då att spela rollspel?

Rollspel handlar om att personen som spelar får en roll den ska leva sig in i. Som konstaterat tidigare kan rollspelen ha något ändamål som att lösa problem, eller få en individ att utvecklas psykiskt, men vanligare är att stöta på rollspel som underhållning. Som underhållning förekommer rollspel i flera former. Termen RPG används vanligtvis för datorrollspelen som handlar om att spelaren ska styra en hjälte eller hjältinna igenom äventyret som lagts upp. Exempel på RPG är spel från ”Final Fantasy” eller ”The Legend of Zelda”-serierna. Den andra varianten av rollspel är bordsrollspel där spelet är ett sällskapsspel med ett berättarmedium. Som exempel för denna variant kan spelet Dungeons & Dragons tas. Oftast är berättarmediumet en person som fungerar som spelledare genom att berätta vad som händer och spela övriga roller i spelet. Denna variant går ut på att alla spelare, förutom spelledaren, skapar en karaktär de ska spela. Spelarna ska sedan tillsammans delta i händelser som spelledaren har kontroll över. Oftast används tärningar för att skapa mera spänning och för att bestämma hur bra det går för en karaktär. Som exempel kan tas: ”Jag vill hoppa över en ravin” – personen i fråga kastar en sexsidig tärning och får en etta, vilket leder till att personen faller ner i ravinen. Om personen däremot kastat en sexa, kunde han ha klarat av hoppet utan några problem.

 

Dungeons_and_Dragons_game
Ett gäng som spelar Dungeons & Dragons

Spektrum RPG, det nyligen skapade spelet av den sistnämnda varianten, hade sin premiär efter januari-måmö där spelledaren kallades för studiehandledare och delade ut studiepoäng åt studeranden, dvs. spelarna. Spelarna hade möjlighet att i början välja om de var mer insatta i att studera, gå på gym eller vara social, genom att dela poäng över sina egenskaper. Vissa var mer atletiska, medan andra var supersociala. Spelet spelades genom att varje spelare i tur och ordning fick välja vad de gjorde under perioden, med andra ord under sin tur. Under perioden kunde studeranden bl.a. tillbringa sin tid på gymet, på att läsa inför tenter eller delta i spektralt program, vilket varierade från period till period. I slutet av varje period deltog studeranden i tentveckan och beroende på hur de tillbringat sin tid fick de ett visst antal studiepoäng. Tärningskast hade också stor påverkan på slutresultaten i spelet.

För att komma tillbaka till frågan i rubriken, så kan svaret vara någondera, beroende på hur mycket man anser sig få ut genom att spela något rollspel. I början nämndes några praktiska tillämpningar av rollspel, men även bordsrollspelen kan anses vara nyttiga. Då man sätter sig in i en roll och måste fundera på hur karaktären i fråga beter sig och talar, så kan det plötsligt krävas en massa improvisation, beroende på spelledarens kedja av händelser. För att inte nämna spelledarens roll, där spelledaren måste anpassa sig till de andra spelarnas improvisation och hålla spelet igång utan desto större störningar.

Då man spelar bordsrollspel övar man alltså, beroende på hur mycket man sätter sig in i rollen, på att improvisera och vara kreativ med det som givits. Genom att träna upp denna sida hos sig själv kan man eventuellt bli bättre på att hitta på nya lösningar till problem som uppkommit i verkligheten. Men såsom med största delen av alla ”intelligensspel”, så kommer man troligtvis inte att kunna lösa millenieproblem genom att hitta på hur man effektivt kan slå ner en drake. Om man däremot gillar att spexa och uppträda, så ger rollspel en bra möjlighet för att öva på improvisation.

Enligt undertecknads åsikt, så är rollspel, framförallt bordsrollspel, ett roligt sätt att fördriva sin tid med vänner, samtidigt som man lär sig att uppträda och tänka kvickt. Man lär sig mer ju mer man lever sig in i rollen man spelar.

Paul

2014, Blogg

Algoritmisk Sudokulösning

Lämna en kommentar

Sudoku, eller “Number Place” som det ursprungligen hette är i dagens läge ett mycket välkänt logiskt pussel:

rank3Example rank3ExampleSolved

Givet ett 9 \times 9 rutfält delvis ifyllt av siffrorna 1-9 skall du fylla i resten av rutorna med siffrorna 1-9 så att varje siffra uppkommer endast en gång på varje rad/kolumn/liten ruta, vilka i exemplet omringas i bilden av de lite tjockare linjerna.

Sudoku pussel kan hittas överallt; många tidningar (t.ex. Hbl) publicerar sudokun dagligen, dessutom kryllar bokaffärerna av ”traditionella” och internet av elektroniska sudokun i varierande kvalitet. För de allra ivrigaste lösarna ordnas det årligen VM, med tusentals euron som pris. För den intresserade läsaren finns det i källorna ett par länkar om sudokuns historia, jag måste medge att jag hade trott att sudoku skulle härstamma från Japan, men den moderna varianten av sudoku skapades (högst troligen) av en 74-årig arkitekt från USA.

Det skulle kunna finnas ett antal olika aspekter att diskutera då det kommer till sudokun. Jag kommer att (igen) ta en datavetar-syn på det hela och undersöka till vilken grad datorer kan användas för sudokulösning. Det vill säga: hur svårt är lösning av sudokun för en dator och har människan någon chans klara sig mot dem? Mer specifikt så kommer jag att presentera tre olika algoritmer för sudokulösning samt jämföra dem med varandra.

Sudokulösning med datorhjälp

Näst går vi alltså igenom tre alternativa algoritmer för att lösa sudokun. För läsbarhetens skull kommer jag inte att gå in på detalj då det kommer till implementeringen av de mer komplicerade algoritmerna. Detaljerad förståelse för algoritmerna krävs inte i resten av texten och för de intresserade läsarna finns det en bilaga med (lite) mer detalj.

Algoritm 1:  SimpleSolver

Den första algoritmen vi undersöker är också den enklaste. Ifall jag skulle be 100 människor beskriva det simplaste sättet de kommer på för att lösa sudokun, skulle de flesta högst troligen beskriva SimpleSolver. Det handlar nämligen om att pröva alla de (ändligt många) sätten att fylla i de tomma rutorna. Algoritmen fungerar genom att gå igenom alla tomma rutor en åt gången och pröva alla möjliga siffror att sätta i dem. Efter att ha fyllt rutan granskar algoritmen att alla sudokuregler fortfarande uppfylls. Om allt är ok går algoritmen vidare till nästa tomma ruta, annars prövar algoritmen nästa siffra. Om algoritmen tvingas pröva alla siffror utan att kunna hitta en lösning går den tillbaka till föregående tomma ruta och prövar nästa siffra.

Med denna taktik kommer algoritmen i något skede att ha prövat alla möjligheter och därmed också hittat lösningen. SimpleSolver är väldigt simpel, implementation av den brukar vara en av räkneövningarna under grundprogrammeringskurserna i Gumtäkt.

Algoritm 2: DLXSudoku

Till skillnad från första algoritmen är de två andra algoritmerna för sudokulösning ursprungligen inte skapade för sudokun. Istället baserar de sig på idén att omvandla sudoku problemet till något annat (välkänt) problem och sedan lösa det andra problemet istället. Orsaken till att vilja göra såhär är att det ofta är lättare att omvandla problem än att lösa dem. Så om vi kan hitta andra problem som någon annan (lite fiffigare) människa har utvecklat effektiva lösningsalgoritmer för, kan vi dra nytta av dessa algoritmer genom att omvandla vårt problem. Detta är ofta tidseffektivare än att tillbringa en massa tid på att utveckla specialiserade algoritmer för just sudokun. Inom datavetenskap kallar man ofta denna process för en reduktion av ett problem till ett annat. Vår andra algoritm är baserad på en reduktion av sudokun till exact cover problemet och lösning av exact cover med hjälp av Algoritm X implementerad med dancing links: DLXSudoku.

Exact cover är ett ganska abstrakt problem: Givet en matris bestående av endast ettor och nollor är uppgiften att välja ut en delmängd av raderna i matrisen så att det bland de rader vi väljer ut finns exakt en etta i varje kolumn (Obs! Detta är inte den mest allmänna formuleringen av exact cover, men tillräcklig för vårt behov). Ett sudoku problem kan relativt enkelt omvandlas till en exact cover matris :

  • Varje tom ruta i sudokubrädet motsvaras av 9 rader i matrisen. Vi kallar dessa rader för Rr\#Cc\#1, \ldots, Rr\#Cc\#9 där den tomma rutan i fråga finns på rad r kolumn c.
  • Kolumnerna i matrisen representerar de olika sudoku reglerna:
    1. Varje ruta i sudokubrädet skall få exakt 1 siffra
    2. Varje kolumn på sudokubrädet skall bli ifylld av exakt en av varje siffra
    3. Varje rad i sudokubrädet skall skall bli ifylld av exakt en av varje siffra.
    4. Varje liten ruta skall bli ifylld av exakt en av varje siffra.

Alla av dessa regler representeras av kolumnerna så att kolumnen innehåller en etta på alla rader som uppfyller regeln (se exempel nedan).

Efter denna konstruktion kan vi lösa exakt cover problemet och omvandla lösningen till en lösning av sudokut helt enkelt genom att fylla i sudokut enligt de rader Rr#Cc#x som vi valt ut till exact cover lösningen. Notera specifikt att kolumnerna i exact cover matrisen som representerar kravet ”varje ruta på sudokubrädet får exakt ett värde” försäkrar oss om att exact cover lösningen innehåller för varje rad r och kolumn c på sudoku brädet, exakt en rad Rr#Cc#i från exact cover matrisen. För den intresserade läsaren finns det som bilaga till denna text en beskrivning på hur DLX fungerar. Här nöjer vi oss med att nämna att algoritmen har populariserats av Donald Knuth, som även har utvecklat det (inom naturvetenskaper) mycket använda LateX typsättningssystemet.

rank2Exampel

Exempel: Vi reducerar 4 \times 4  sudokut ovanför till exact cover. För detta sudoku får vi en exact cover matris med 8 (antalet tomma rutor) \times 4 rader. Bilden nedan visar en del av den:

ExactCover I bilden representerar första kolumnen kravet: ”Rutan på rad 2 kolumn 1 måste få exakt 1 värde”. Vi ser att kolumnen innehåller en etta på varje rad vars val fyller i rutan och 0 annars. Andra kolumnen representerar kravet ”Någon ruta på rad två måste innehålla en etta”, tredje kolumnen representerar: ”Första kolumnen måste innehålla en fyra” och fjärde ”lilla rutan uppe till höger måste innehålla en etta”, vi märker specifikt att fjärde kolumnen innehåller en etta endast på första raden. Detta betyder att vi måste välja första raden till exact cover lösningen vilket i sin tur betyder att rutan i kolumn 1 rad 2 kommer att innehålla en etta.

Algoritm 3: SATSudoku

Den sista av våra algoritmer reducerar sudoku till det kanske mest kända ”svåra” problemet inom datavetenskap, nämligen satisfiability (SAT). För att kunna beskriva SAT måste vi påminna oss om logik kursen i gymnasiet och specifikt de delarna som handlade om propositionslogik.

Propositionslogik är ett väldigt enkelt logiskt ”språk” där man formar formler genom att binda ihop sanningsvariabler (dvs. variabler som antingen kan vara sanna eller falska) med hjälp av \land (OCH), \lor  (ELLER) och \neg (INTE). (Obs. det finns ett antal olika sätt att definiera propositionslogik, vi använder det simplaste möjliga som räcker för vårt behov). Givet en propositionslogisk formel går SAT problemet ut på att hitta ett sätt att ge sanningsvärden (sant eller falskt) åt variablerna som gör att hela formeln blir sann. Sanningsvärdet för en formel definieras utgående från sanningsvärden för de delformler den innehåller:

  • Om formeln endast består av en enda variabel är dess sanningsvärde lika med sanningsvärdet för variabeln.
  • Sanningsvärdet för \lnot A är motsatsen till sanningsvärdet för formeln A
  • Formeln A \land B är sann ifall både formlerna A och B är sanna
  • Formeln A \lor B är sann ifall antingen A eller B (eller båda) är sanna.

Då vi i denna text pratar om att lösa SAT menar vi att hitta ett sätt att ge värden åt variablerna i en given formel så att formeln blir sann. Vi kallar detta sättet för en ”lösning” av SAT. (Notera att detta inte är en allmän definition av SAT problemet, men tillräcklig för oss.)

SAT är ett mycket välkänt problem inom datavetenskap. I dagens läge existerar det effektiva algoritmer för att lösa formler som består av hundratusentals variabler och miljontals delformler. För att kunna använda dessa algoritmer för att lösa sudokun måste vi från ett givet sudokubräde kunna forma en propositionsformel som tillåter oss omvandla en lösning på SAT problemet till en lösning på sudoku problemet.

För varje ruta, säg på rad r kolumn c, introducerar vi 9 sanningsvariabler: v^{rc}_1, \ldots, v^{rc}_9. Meningen med dessa variabler är: ”v^{rc}_k är sann om och endast om rutan på rad r kolumn c får värdet k i sudokulösningen”. Vår formel kommer att bestå av 5 olika delformler, fyra olika beskrivningar på de olika sudokureglerna och en som beskriver de siffror som är färdigt ifyllda:

1) Varje ruta skall få exakt ett värde. För en fixerad ruta på rad r kolumn c beskrivs detta krav av en logisk representation av: \sum_{j=1}^9 v^{rc}_j = 1. Det finns olika sätt att representera detta som propositionslogik. Ett av de simplaste är att använda formeln: v^{rc}_1 \lor v^{rc}_2 \lor ldots \lor v^{rc}_9 för att se till att rutan får minst ett värde och 27 formler av formen: \lnot (v^{rc}_i \land v^{rc}_j) \quad \forall i < j för att se till att den får högst ett värde. I vår implementation använder vi oss av ett lite annorlunda sätt att representera samma sak (kallas för sequential counter). För den intresserade läsaren finns det referenser.

2) Varje rad skall få en av varje värde. För en fixerad rad R beskrivs detta av (del)formeln:

\bigwedge_{k=1}^9 \left(\sum_{c=1}^9 v^{Rc}_k = 1\right)

som omvandlas till propositionslogik precis som i punkt 1.

3) Varje kolumn skall få en av varje värde. För en fixerad column C beskrivs detta av formeln:

\bigwedge_{k=1}^9 \left( \sum_{r=1}^9 v^{rC}_k = 1 \right)

4) Varje liten ruta skall få en av varje värde. För t.ex. lilla rutan längst upp till vänster beskrivs detta av formeln:

\bigwedge_{k=1}^9 (v^{11}_k + v^{12}_k + v^{13}_k + v^{21}_k + v^{22}_k+v^{23}_k+v^{31}_k+v^{32}_k+v^{33}_k = 1)

5) Varje redan färdigt ifylld ruta motsvaras av en formel som tvingar motsvarande variabel att sättas till sant. Så ifall rutan på rad r kolumn c har färdigt ifyllt värdet k lägger vi med delformeln v^{rc}_k till hela formeln.

Vår sista algoritm för sudokulösning bygger upp ett SAT problem såhär och ger den åt en SAT algoritm. Så länge ursprungliga sudokut har en lösning kommer SAT algoritmen att hitta en lösning på SAT problemet. Sedan omvandlas  SAT lösningen till en sudoku lösning: rutan på rad r kolum c i sudokubrädet fylls i med det värde k för vilket variabeln v^{rc}_k är sann i SAT lösningen. Delformeln vi satt med i punkt 1 här ovan försäkrar oss om att det finns exakt en sådan för varje tom ruta.

rank2Exampel

Exempel: Vi fortsätter med samma exempel som tidigare. Fullständiga propositionsformeln som beskriver detta exempel är för lång för att skrivas ner för hand. Men här följer en del illustrerande exempel   

  1. Rutan på rad 2 kolumn 1 skall få exakt ett värde: (v^{21}_1 \lor v^{21}_2 \lor v^{21}_3 \lor v^{21}_4) \land \lnot (v^{21}_1 \land v^{21}_2) \land \lnot (v^{21}_1 \land v^{21}_3) \land \lnot (v^{21}_1 \land v^{21}_4) \land \lnot (v^{21}_2 \land v^{21}_3) \land \lnot (v^{21}_2 \land v^{21}_4) \land \lnot (v^{21}_3 \land v^{21}_4).
  2.  Kolumn 1 måste innehålla en etta: (v^{11}_1 \lor v^{21}_1 \lor v^{31}_1 \lor v^{41}_1) \land \lnot (v^{11}_1 \land v^{21}_1) \land \lnot (v^{11}_1 \land v^{31}_1) \land \lnot (v^{11}_1 \land v^{41}_1) \land \lnot (v^{21}_1 \land v^{31}_1) \land \lnot (v^{21}_1 \land v^{41}_1) \land \lnot (v^{31}_1 \land v^{41}_1).
  3. Rad 1 måste innehålla en två: (v^{11}_2 \lor v^{12}_2 \lor v^{13}_2 \lor v^{14}_2) \land \lnot (v^{11}_2 \land v^{12}_2) \land \lnot (v^{11}_2 \land v^{13}_2) \land \lnot (v^{11}_2 \land v^{14}_2) \land \lnot (v^{12}_2 \land v^{13}_2) \land \lnot (v^{12}_2 \land v^{14}_2) \land \lnot (v^{13}_2 \land v^{14}_2).
  4. Vissa rutor är färdigt ifyllda: v^{11}_3 \land v^{12}_4 \land v^{13}_1 \land v^{22}_2 \land v^{33}_2 \land v^{42}_1 \land v^{43}_4 \land v^{44}_3.

Bilagan till denna artikel går in på (lite mer) detalj om hur en SAT algoritm oftast fungerar.

Vilken är bäst?

Nu är det dags för den mest intressanta frågan; vilken är bäst? För att kunna testa detta fick jag hjälp av Toffe som implementera SimpleSolvern och Lasse som implementera DLXSudoku. Själv implementerade jag SATSudoku. Tack till både Toffe och Lasse!

Innan vi går till resultaten vill jag påpeka att skillnaderna vi kommer att se i dessa algoritmer inte beror på implementationerna, resultaten kan inte och skall inte användas för att jämföra våra kodningskunskaper.

Jag valde på måfå ut 3 sudokun av storlek 9 \times 9 och tog tid på hur länge var och en av våra algoritmer tog på sig för att lösa dem. Resultaten finns nedan:

SudokuEasy

Det var ju lite tråkigt inte sant? Till och med den simplaste algoritmen löser alla 3 på under 1.5s, de mer avancerade lösarna tar under en tiondels sekund på sig. Detta illustrerar orsaken till varför jag bara hade tre sudokun; faktum är att de allra flesta normala sudokun är så gott som triviala för en dator. Det går att designa problem som vår SimpleSudoku inte skulle kunna lösa, men redan genom att ha SimpleSudoku  pröva siffror i slumpmässig ordning istället för storleksordning så klarar även den av så gott som alla 9 \times 9 sudokun snabbare än vad det skulle ta för människan att skriva ner en färdig lösning. Så det ser inte så hemskt lovande ut för oss människor.

Det verkar alltså klart att om man behöver få många sudokun löst snabbt är det mer tidseffektivt att koda en lösare än att lösa dem själv. Dock kan man efter dessa resultat  fråga sig varför man över huvudtaget borde sätta ner tid på att implementera något som helst mer avancerat än SimpleSudoku?

Ifall man bara är intresserad av 9 \times 9 sudokun är svaret: man borde inte. Men, om vi tillåter större sudokun blir saker och ting intressantare. Forskningsresultat inom sudokulösning (ja, det finns sådana) pratar ofta om ordningen (rank) av ett sudoku. En normal sudoku är av ordning 3 och allmänt så skall en sudoku av ordning n lösas på ett n^2 \times n^2 bräde. Så en 4 \times 4 sudoku är av ordning 2 och en 16 \times 16 sudoku är av ordning 4. Alla av våra algoritmer kan användas för att lösa sudokun av vilken ordning som helst. Dessutom borde större sudokun vara bättre för att jämföra algoritmer, intuitivt känns det ju ganska klart att ett större sudoku borde vara svårare än ett mindre.

SudokuHard

Resultaten finns ovan och nu börjar vi på riktigt märka skillnader i algoritmerna. SimpleSolvern klarade inte av en enda av dessa problem på under en timme (gränsen på lösningstiden). Däremot klarar sig både SATSudoku och DLXSudoku ganska väl, speciellt på ”enkla” sudokun. Av dessa två klarar sig SATSudoku lite bättre än DLX: den klarar av en ordning större ”lätt” problem och en ordning större ”svårt” problem.

Vad lär vi oss av detta? Jo, om du bara vill lösa ett enda normal stort sudoku är det fiffigare att ta papper och penna än börja koda. Skall du lösa 1000 normala sudokun kan du be datorn göra det på det enklaste möjliga sättet. Skall du lösa ett enkelt 15^2 = 225 \times 225 sudoku, så går det också att fixas, dock med lite mer möda. Men om du vill lösa ett svårt 49 \times 49 sudoku? Då är det dags att ta fram pennan igen, skriva ett stort ”LÖS SJÄLV” på hela brädet, och ta en öl istället.

Slutligen vill jag lämna er med det största sudokut som våra algoritmer klarade av och det minsta som de inte klarade. Om någon av er får någondera löst kan ni lämna en kommentar så sätter jag med er i resultaten.

Jeremias

BILAGA:

Algorithm X, Conflict Driven Clause Learning and Dancing Links for Sudokusolving.

Källor: