14 dec. 2013

Varför Sudoku kräver en intelligent designer

Är vi skapade genom evolution med hjälp av en intelligent designer? Som exempel kräver pusselspelet Sudoku en intelligent designer. Låt oss använda en dator för att undersöka saken! Sudoku spelas på ett rutnät med 9 x 9 rutor. I varje ruta ska en siffra mellan 1 och 9 placeras, men siffrorna måste placeras efter vissa regler. Varje rad får endast innehålla en etta, en tvåa, en trea, och så vidare. Det samma gäller för varje kolumn och för alla nio 3 x 3 rutor stora regioner. Detta är den första raden av nio:

01-rad

Detta är den första kolumnen av nio:

02-kol

Detta är den första regionen av nio:

03-reg1

Detta är den andra regionen av nio:

04-reg2

Om vi ska låta evolutionen verka för att bygga ett Sudoku kan vi tänka oss att spelplanen existerar i en miljö där det innebär en överlevnadsfördel att ha unika tal på varje rad. Den första spelplanen som vi placerar i denna miljö består av nio slumpvist utplacerade ettor, nio slumpvis utplacerade tvåor, nio slumpvis utplacerade treor, och så vidare. Detta ger oss en spelplan med ett korrekt innehåll, men ett (med största sannolikhet) felaktigt placerat innehåll. Här bygger vi listan med de möjliga siffrorna som kan förekomma:

         var r = new Random();
         var l = new List<int>();
         for (var i = 1; i < 10; i++)
            for (var j = 1; j < 10; j++)
               l.Add(i);

Sen placerar vi ut dem på spelplanen, slumpvis. Spelplanen representeras av en medlemsvariabel som heter field:

         for (var i = 0; i < 9; i++)
            for (var j = 0; j < 9; j++)
            {
               var index = r.Next(0, l.Count);
               var value = l[index]; l.RemoveAt(index);
               this.field[j, i] = value;
            }

Teoretiskt skulle vi kunna tänka oss att detta räcker för att vi ska ha ett korrekt Sudoku, men med tanke på alla möjliga platser som varje siffra kan hamna på, är den sannolikheten mikroskopiskt liten.

Ett problem med datorer är att de egentligen inte har några miljöer och egentligen inte känner till några kriterier, våra intentioner eller något annat. Därför måste vi ibland skriva kod som deklarerar och definierar vad vi behöver. Följande kod berättar att vi vill kunna poängsätta en organism (poäng är egentligen antal fel så få poäng är bra och många poäng är dåligt), att vi vill veta hur länge datorn arbetat med problemet, och hur många generationer som har passerat. Men vi vill även veta något annat: Hur många generationer har passerat sedan en avkomma verkligen var bättre anpassad till miljön än sin förälder. Det finns nämligen en risk för evolutionära återvändsgränder här.

         int score = int.MaxValue, iterations = 0, generations = 0,
               iterations_since_last_climb = 0;

En evolutionär återvändsgräns kan bäst förklaras om man tänker sig evolution som en hill climber. Tänk dig att en organism kan vara mer eller mindre anpassad till den miljö organismen existerar i. Detta kan vi låta symboliseras av kullar och dalar, där dalarna representerar en sämre anpassning och kullarna representerar en bättre.

05-hill

Genom att räkna felen i vår slumpmässigt skapade Sudoku-organism, så vet vi hur anpassad den är. Och eftersom organismen är skapad slumpässigt, kan vi vara helt säkra på att anpassningen är dålig. Vår organism befinner sig i en dal.

06-hill

Apropå att man måste förklara allt för datorn, så här beskriver jag en mutation för datorn: Om poängen är hög (= många fel) ska tre slumpmässiga sifferpar byta plats, annars två.

         Action<int[,]> mutate = a => {
            var speed = (score > 2 ? 3 : 1);
            for (var i = 0; i < speed; i++)
            {
               int x1 = r.Next(0, 9), y1 = r.Next(0, 9),
                   x2 = r.Next(0, 9), y2 = r.Next(0, 9);
               var v = a[x1, y1]; a[x1, y1] = a[x2, y2];
               a[x2, y2] = v;
            }
         };

Varför kommer inte evolutionen att lösa Sudoku-pusslet? Jo, därför att evolutionen ofrånkomligt premierar ett klättrande på detta kulliga landskap. Om arten befinner sig här i vårt landskap av potentiellt sämre och bättre anpassningar…

07-hill

…och en mutation flyttar arten uppåt medan en annan mutation flyttar arten nedåt, kommer ofrånkomligen den mutation som utgör en förbättring att premieras. Men detta innebär att vi inte kan nå målet, eftersom den kulle vi befinner oss på inte med nödvändighet är den högsta. Och enligt reglerna för Sudoku, har vi inte löst pusslet förrän vi är helt korrekta.

08-hill

Vi kommer alltså stöta på evolutionära återvändsgränder. I egenskap av en intelligent designer (jo, datorn är min slav) kan jag hantera detta genom att deklarera att om sextiotusen generationer passerat utan att någon förbättring i frågan om anpassning till miljö har skett, så befinner vi oss inte på den högsta kullen – vi befinner oss i en evolutionär återvändsgränd. Då måste organismen mutera okontrollerat för att placeras nere i en dal igen, för att kunna påbörja klättrandet upp för en annan kulle. Därför berättar jag för datorn att jag vill mutera åt olika håll och behålla den bästa, endast om detta ibland leder till faktiska förbättringar.

         do
         {
            iterations++;

            //If adaptation has stoped, the parent must mutate.
            if (iterations_since_last_climb >= 60000)
            {
               mutate(this.field);
               score = this.GetScore(this.field);
            }
            //Breed two new sudokos and modify them slightly.
            int[,] child1 = (int[,])this.field.Clone();
            int[,] child2 = (int[,])this.field.Clone();
            mutate(child1); mutate(child2);

            //Check new scores.
            var child1score = this.GetScore(child1);
            var child2score = this.GetScore(child2);

            //Keep the best one, if any.
            Action<int[,], int> keep = (a, s) => {
               this.field = (int[,])a.Clone(); score = s;
               generations++; iterations_since_last_climb = 0; };
            if (child1score < score)
               keep(child1, child1score);
            else if (child2score < score)
               keep(child2, child2score);
            else
               iterations_since_last_climb++;
            System.Threading.Thread.Yield();
            this.Display();
         } while (score > 0);

(Om du är nyfiken på detaljerna kring GetScore och Display, så är det två funktioner som jag har skapat för att räkna fel i en organism, respektive presentera en organism. Källkoden finns här.)

I egenskap av en intelligent designer, tar jag mig alltså friheter som naturen inte har. Om jag tar mig förmånen att hoppa ner i en dal, kan jag nämligen ha turen att börja klättra upp för en högre kulle, och när jag hittat den högsta kullen, är pusslet löst.

Om människan vore en ”skapelsens krona” med en intelligent designer, skulle vi inte lida av att ibland välja den kulle som inte är högst. Vår skapare skulle se till att vi kunde utvecklas genom att klättra upp för de högsta kullarna, vilket alltså innebär att vi väljer de bästa ”strategierna”. Men vi kan inte backa, och jag som skriver detta lider av evolutionära återvändsgränder som andra organismer slipper lida av. Detta säger mig att evolutionen inte är övervakad av någon intelligent designer.

4 kommentarer:

Lennart W sa...

Tack Anders för en intressant bloggpost! Älskar sånt här. Vi kan nog även diskutera ev teologiska implikationer, men först vill jag veta i så fall hur jag så smidigt som möjligt kan kompilera källkoden (utan ändringar). Microsoft Visual C++?

Återkommer.

(Och i själva bloggposten har du råkat upprepa två bitar av koden, vilket du kanske vill ändra på)

Anders Hesselbom sa...

Tack Lennart. En kompileringsbar version finns här. Nej, det är C#, så i Windows kan den kompileras med csc.exe (eller genom att bara klistras in i Visual Studio) och på Linux kan den kompileras med MonoDev.

Det intressanta i koden är förbättringarna sker långsammare och långsammare, och fastnar tillslut med 4-8 fel. Men då slumpar jag om lite, så att jag hamnar på en ny "kulle", och efter någon knapp miljon iterationer så har jag ett korrekt Sudoku, vilket på en modern PC är frågan om sekunder.

Jag förmodar att vi inte är överens om de teologiska växlar jag drar utifrån detta, och det diskuterar jag givetvis gärna!

Lennart W sa...

Anders: Jo, jag såg länken till hela källkoden i bloggposten, men lyckades ändå missa i mobilen att det var C# (står ju längst ned att det är postat i C#, Geeky, Microsoft .NET). Läste väl inte så noga. Är väl heller ingen fena på något sorts C öht, men jag antar att ett vant öga snabbt märker vad det är frågan om. Ok, ska iaf försöka kompilera. Återkommer ev. om det.

Bra jobbat förresten! Hela vägen, från idé till programmering, och till hur du beskriver resultatet.

(Om själva Sudokugenererandet är av intresse hittade jag även det här:
Sudoku Puzzles Generating: from Easy to Evil (länk)
från en kinesisk forskargrupp, där de för genererandet av den fullständiga lösningen talar om Las Vegas-algoritmen (länk))

--

Nej, det är sant att livets evolution inte gör några stora hopp för att därigenom kunna komma från en lägre topp och sedan leta sig upp till en högre. Och därför finns det inga större djur med hjul istället för ben, för det skulle kräva ett megastort hopp mellan två toppar (Dawkins exempel, tror det var i The Ancestor's Tale, som är en riktigt bra populärvetenskaplig bok). Sen är jag nog iofs inte säker på att hjul är bättre än ben heller, men det är iaf just ett sådant där exempel som skulle kräva ett större hopp. Ett annat kanske rimligare exempel tror jag kan vara synnerven som vore bättre placerad på baksidan av ögat istället för i ögat. På den plats där den leder ut ur ögat har vi vår blinda fläck, vilket ju verkar ganska feldraget. Men jag tror på något sätt att det inte är en liten ändring som krävs i vårt DNA för att synnerven ska får en smartare placering. Vårt DNA är ju inte en ritning, utan snarare ett recept. Gör en massa saker i rätt ordning, så blir slutresultatet en människa. Även i vanlig bakning kan det ju bli helt på tok om man försöker göra saker i en annan ordning. En bättre placerad synnerv är nog på en helt annan topp i DNA-landskapet.

Förresten kanske man kan se de fem eller så stora katastrofer som nästan utrotade allt liv, som just ett sånt där sätt att backa ned från en topp för att kunna hitta högre? Fortsätt iterera tills det uppstår en art som är tillräckligt smart för att undvika nästa katastrof.. Dinosarierna höll inte måttet. Gör vi?

Anders Hesselbom sa...

Katastrofer är inte samma sak, det reducerar bara vad som är utplacerat och ger plats för ny evolution. En katastrof skulle t.ex. inte kunna befria vårt öga från den blinda fläcken. Men en teistisk syn på ditt påstående skulle kunna vara att Gud håller på att skapa sin avbild genom evolution, och att vi är misstaget som snart ska lustmördas.

 
Religion Blogg listad på Bloggtoppen.se