Anders Hesselbom

Varför Sudoku kräver en intelligent designer

2013-12-14

Ä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:

Detta är den första kolumnen av nio:

Detta är den första regionen av nio:

Detta är den andra regionen av nio:

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.

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.

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…

…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.

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.

Kategorier: Uncategorized