Two-Dice Pig – Coding Battle

Two-Dice Pig is a classic game where you throw a pair of dice over and over and sum up the points you get. When you reach one hundred, you win. Easy? Well, there is one little problem. If one of your dice show a one, all your points are lost and the turn goes over to your opponent who faces the same challenge. There is a way to keep your accumulated points though and that is if you declare that enough is enough and hand over the dice to your opponent. In that case you get to keep your points. They are transfered to your ”bank”. The points in your bank are safe there unless you happen to roll two ones (snake eyes).

Though the game is very simple (or rather because the game is very simple), soon you start wondering about the optimal strategy. For how long will you risk keeping on rolling your dice? Is there a recommended limit? Or is there a recommended number of times you should try to roll the dice before you declare that your satisfied?

I created a web app in Javascript where you can compete against an opponent in Two-Dice pig. But you don’t play directly. You compete with your strategy. You design your strategy and then you challenge the strategy of your opponent. The standard option is to play one thousand games of Pig and in just a wink of an eye you can see which strategy is the best.

screendump

Your gaming strategy is designed by coding a Javascript condition for when to continue rolling your dice.

The variables you can utilize are the following:

a: Points accumulated during the current round
b: Index number keeping track of how many rolls you’ve made during the current round. If its the first throw b = 1
c: Points In The Bank
d: Opponent Points In The Bank
e: PlayerIndex. If you’re the first player starting out: e = 1. Otherwise: e = 2

In this implementation of the game the second player always has a last chance to try to catch up with the first player even though one hundred is already reached. If you play one thousand games you will be player number one in exactly 500 of the games.

Example: Here’s a legal strategy:

b<4

It means that as long as the number of throws are lower than four you will continue to roll the dice. In other words; when you have rolled the dice four times you declare that it’s your opponents turn.

Here’s another legal strategy:

a<12

This means that as long as you haven’t reached 12 points during the current round you will continue to roll the dice.

And here’s yet another one:

a<12 && a+c<100

This means that there are TWO conditions that need to be meet with for your rolling to continue.

The accumulated point during the current round must be lower than 12 AND the sum of the accumulated points and your points in your bank must be lower than 100.

The simplest valid strategy would just be

1 == 0

or just

false

That means that you never continue to roll. You roll the dice only once, each time it’s your turn, but that’s it.

There are two strategies that can be edited on screen. One for the ”Blue program” and one for the ”Red program”. They can compete against each other. There’s also a third pre-programmed strategy belonging to the so called ”Champ program”. That a strategy is one that I’ve coded myself that I’m pretty happy with. The ”Champ program” is, I imagine, pretty hard to beat so, as an ultimate test for your own strategy you can also challenge the champ program. Can you beat the Champ?

Note: The idea of designing the perfect strategy for this game has attracted interest from mathematicians and computer scientists. Here’s a link to a pdf – Optimal Play of the Dice Game Pig – published by the computer science faculty at the Gettysburg College. The list of academic references in the end of that publication is great if you’re interested in delving deeper into the subject.

Steganography

img01

Steganographic storage of encrypted files in images.

What I find truly fascinating is that there is no way to tell if an image contains steganographically hidden encrypted data. Even if you know every line of the source code of the program that you suspect may have been used to hide the data, you still have nothing to help you prove anything.
If the least significant bits in the RGB-values contains encrypted data they should appear to be random. But the least significant bits in an ordinary image on the other hand, could be expected to be less random and show a bit more regional uniformity.

Store in pixel
But randomness in the least significant bits does not constitute proof that there are encrypted data hidden. The randomness of the RGB-values could originate from natural minute color shade variations in the surface of the physical object being photographed or be the result of an image editor filter.

I’ve been working on an encryption program in C# for a couple of days. It encrypts files and hides the encrypted data steganographically inside images.

The portrait above actually does contain data that can be extracted and be visually interpreted in an unexpected way. Hidden in the above images is another image. The image you see below:

img02

I think that maybe it’s wrong to say that the initial image contains hidden data. There are no hidden data. All data in the initial image is visually represented on the screen. The question is how you interpret the data.

To make things more interesting I can reveal that the above bluish image also contains something that you might not expect.

Encoded in the pixels is a text file with the 81 verses of the ancient Tao Te Ching by Lao Tzu.

1
The Tao that can be trodden is not the enduring and
unchanging Tao. The name that can be named is not the enduring and
unchanging name.

(Conceived of as) having no name, it is the Originator of heaven
and earth; (conceived of as) having a name, it is the Mother of all
things.

Always without desire we must be found,
If its deep mystery we would sound;
But if desire always within us be,
Its outer fringe is all that we shall see.

Under these two aspects, it is really the same; but as development
takes place, it receives the different names. Together we call them
the Mystery. Where the Mystery is the deepest is the gate of all that
is subtle and wonderful.

Above you see only the first verse. The bluish image contains all 81 verses!

 

 

 

 

RSA Algorithm – Simple Demo

I put together a simple interactive demo to illustrate the principles behind RSA asymmetric public-private key encryption.

rsa.demo.2

Click on the image above or [here] to go to the javascript demo.

Note that this demo setup is for pedagogical use only. In order for the method to be of any use in a real encryption scenario we would need to use initial prime numbers more than 100 digits long.

For example, we could use these two prime numbers of 116 digits each:

p = 33 478 071 698 956 898 786 044 169 848 212 690 817 704 794 983 713 768 568 912 431 388 982 883 793 878 002 287 614 711 652 531 743 087 737 814 467 999 489

q = 36 746 043 666 799 590 428 244 633 799 627 952 632 279 158 164 343 087 642 676 032 283 815 739 666 511 279 233 373 417 143 396 810 270 092 798 736 308 917

Multiplied together you’ll get this 232 digits long public key n:

n =  1 230 186 684 530 117 755 130 494 958 384 962 720 772 853 569 595 334 792 197 322 452 151 726 400 507 263 657 518 745 202 199 786 469 389 956 474 942 774 063 845 925 192 557 326 303 453 731 548 268 507 917 026 122 142 913 461 670 429 214 311 602 221 240 479 274 737 794 080 665 351 419 597 459 856 902 143 413

One thing that is truly fascinating and that constitutes the very foundation for the whole RSA concept is the asymmetry in required work between multiplying these two numbers and doing the opposite thing – finding the factors p and q knowing only n.

I programmed a javascript function for big integer multiplication. It can multiply these two 116-digit numbers in 2 miliseconds.

But doing the opposite, doing the reverse operation – factoring – how long time does that take?

In this particular case, it has actually been done. It’s the largest integer hitherto factorized. It took two years of computer processing and was accompliced on December 12, 2009. The CPU time spent on finding these factors by a collection of parallel computers amounted approximately to the equivalent of more than 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.

Professional RSA encryption today uses public keys n of at least the magnitude of 2048 bits. That’s a number with 616 decimal digits and that means we use prime numbers p and q with 308 digits each.

My homemade javascript function multiplies two such primes to form a 616 digit integer in 20 miliseconds.

For the above mentioned Opteron-based computer, the task of factoring a 616 digit integer is estimated to require 6.4 quadrillion years of CPU time. That’s like the age of the universe multiplied by half a million.

The second obvious weakness in the simple javascript demo apart from the prime numbers being too small is the fact that only one character at a time is encrypted with the algorithm.

Let’s look at the scenario shown in the initial screen dump.

n = 323
e = 139 (public encryption key)
d = 259 (private decryption key)

Now we’re going to encrypt the word ”hello” where each letter is represented by its ”ascii-code”

h = 104
e = 101
l = 108
l = 108
o = 111

 

So we RSA-encrypt them with the public key (139) like this:

”h”: 104^139 (mod 323) = 25
”e”: 101^139 (mod 323) = 118
”l”: 108^139 (mod 323) = 243
”l”: 108^139 (mod 323) = 243
”o”: 111^139 (mod 323) = 100

And we can decrypt them using the private key (259) like this:

25^259 (mod 323) = 104 (”h”)
118^259 (mod 323) = 101 (”e”)
243^259 (mod 323) = 108 (”l”)
243^259 (mod 323) = 108 (”l”)
100^259 (mod 323) = 111 (”o”)

The glaring weakness here is of course that anyone having only the public key (139) can produce a translation table relating each non-encrypted letter of the alphabet with an encrypted value. So, even without access to the private key, an unauthorized person can, using this translation table, discover the word ”hello” in the encrypted sequence 25, 118, 243, 243, 100.

The fix for this weakness is to encrypt larger chunks of text at each powermod-operation. The textual chunk size should correspond to the size of n. If n is a 2048 bit value, then you can encrypt the text in chunks of 2048 bits (corresponding to 256 8-bit ascii characters).

But what if a prosecutor for example gets hold of a suspects RSA-encrypted file and he thinks that it contains a certain known compromising document? Wouldn’t he be able to prove  that? If he himself encrypts that known document using the public key he can then look for the same encrypted chunks of 256 charaters in the suspects encrypted file. The solution to this weakness lies in letting a certain portion of each chunk consist of completely random bits of information. The consequence of that system will be that identical files will never result in identical encrypted files.

 

 

What does the world look like when no one watches?

The signals from the outside world reach our consciousness in the brain through a complicated chain of electrochemical processes. The problem is that the brain processes  we experience are of a completely different nature than the stuff of the outside world.

When we perceive a table in front of us; what is it that reaches us in the interior of the brain? It’s not like receiving a fax in an office. It’s not that we receive a microscopic little wooden replica of the table in the office of our brain. The thing we receive in our brain is not made of the same stuff as the table.

I like to think of our connection with reality like a more drastic version of the kids game Chinese Whispers. The first person in the far away end is directly in contact with reality but instead of whispering what he sees he composes and recites a poem. The next person listens and whistles a tune inspired by the poem. The third person creates a painting based on the tune. The fourth guy looks at the painting and writes a play. And on it goes from person to person till it finally reaches you. That’s how we perceive reality.

I wonder if the impressions we have of the reality of the outside world bears any resemblance to reality as it is in itself. Does it even make sense to talk about how the outside world looks like independently of us?

You can think about the “objective appearance” of reality as you would about the monsters you encounter in online roleplaying games like World of Warcraft. What does the monsters look like when you don’t play? In this analogy it becomes clear that it’s almost meaningless to talk about the monsters appearance when no one plays. The monsters “objective appearance” is just data on a harddrive. What does data look like? When we play the game a Cave Troll may look greenish brown, scruffy and slightly hunched with a grim facial expression. When we’re not playing the Cave Troll is just one’s and zeros or north-south polarity in the magnetic ferric oxide film covering a disk. The point is that reality does not look like anything at all when we’re not watching. The appearance of reality is completely created in the interaction with conscious beings.

The German physicist Heinrich Hertz wrote in the introduction to his The Principles of Mechanics, published 1899, something that’s been stuck in my mind for many years.

We form ourselves images of external objects; and the form which we give them is such that the necessary consequents of the images in thought are always the images of the necessary consequents in nature of the thing depicted…

This is such an elegant answer to the whole philosophical question.


Hertz, one of the greatest and most important physicists
of the nineteenth century died only 36 years old.
The international unit for frequency is named after him.

Mahabalipuram

Flyg Istanbul – Bombay och sen samma dag vidare med inrikesflyg till Madras. Sen med skramlig buss i sydlig riktning till Mahabalipuram.


Jag provade lite morgonmeditation


Hittar en tamil-bok jag vill ha


Jag och ko och byggnadsarbetare


Stenen ser ut att kunna rulla ner vilken sekund som helt


Hela familjen har varit och handlat i stan


Man kan inte fara till Indien utan att meditera pa en klippa vid havet (Bengaliska viken)


Indisk begagnad lastbil

 
Indierna har en fantastisk formaga att pressa in sig 10 stycken i en auto-rickshaw…


Strandtemplet i Mahabalipuram lockar manga indiska turister


Vackra saris fladdrar i vinden


Sand, sand, sand…

Är vi gjorda för att äta kött?

Made_for_meat

Jag hamnade i en diskussion här om dagen i en annan blogg men en person som mellan raderna antydde att absolut vegetarianism var något onaturligt för människan givet vår stora hjärnvolym. Växtätare har liten hjärna. Det krävs inte så mycket intelligens att fånga sin mat eftersom den ligger still. Rovdjur som behöver större intelligens för att fånga sin mat har generellt sett större hjärnor. Hur kommer det sig att människan har så stor hjärna? Tillhör vi inte rovdjurskategorin vad gäller hjärnkapacitet?

Resonemanget har självklart sin lockelse men håller inte, enligt min mening, vid närmare granskning. Arten med de största hjärnorna bland människoaporna, gorillorna, är helvegetarianer.

Det mesta i vår fysionomi liknar växtätarnas. Liksom växtätarna kan vi röra käkarna i sidled och vi har malande kindtänder. Vi suger i oss vätska och vi svettas. Köttätare har inga malande kindtänder och kan inte röra käkarna i sidled. Köttätare lapar i sig vätska och tenderar att reglera kroppsteperaturen genom att andas häftigt och sticka ut tungan.

Om man bara ska jämföra oss med kött- och växtätare så verkar det ju som om människan är gjord för att äta grönsaker. Men då glömmer vi ju att det finns allätare också – omnivorer. Det mest korrekta måste ju vara att jämföra oss med alla tre grupperna.

Enligt min mening är människan en omnivor men med stark dragning åt växtätare.

Pojkar och flickor – bra på olika sätt?

Min intellektuella varningslampa börjar alltid blinka rött när jag hör påståenden liknande den i rubriken till detta inlägg. Inte sällan ser man resonemang från religiöst håll som ska förklara skillnader i rollfördelning mellan pojkar och flickor eller mellan män och kvinnor som den beskrivs i exempelvis Bibeln eller Koranen. Man hör ofta påståenden som: ”Jo visst är kvinnor lika mycket värda som män men de har en annan roll att spela”. Jag köper inte det. Kor och grisar är också värdefulla och har också en annan roll att spela i samhället.

Det är förstås inte så länge sen,  som den svenska skolan ställde upp vitt skilda mål för pojkar och flickor. En undersökning av skillnaderna mellan flickskolans och läroverkets läroplanskoder i mitten på artonhundratalet erbjuder en både skrämmande och komisk läsning.

Modersmålet – pojkar:

Logik och abstraktion – Grammatik. Korrekt stavning och interpunktion. Dispositionsteknik.

Modersmålet – flickor:

Känsla och fantasi – Korrekt stavning och interpunktion. Talövningar och välläsning. Litteraturhistoria och litteraturläsning.

Historia – pojkar:

Nationell fostran – politisk historia.

Historia – flickor:

Nationell fostran – Kultur- och socialhistoria. Konsthistoria.

Naturvetenskapliga ämnen – pojkar:

Grund för vidare vetenskaplig utbildning – Kemiska formler. Systematiseringar av växter och djur. Fysikaliska lagbundenheter. Forskningsmetoder.

Naturvetenskapliga ämnen – flickor:

Praktisk tillämpning i vardagslivet – Kemi för hushållet. Biologi för hälsoläran. Optik för smakens höjande.

Matematik – pojkar:

Formell bildning, logik och abstraktion – avancerad algebra och differentialkalkyl

Matematik – flickor:

Vardagslivets matematik – De fyra räknasätten. Geometri.

(Källa: Christina Florin & Ulla Johansson, ”Där de härliga lagrarna gro…”, Kristiansstad 1993)

Dessa läroplanskoder kan kännas löjeväckande föråldrade men frågan är om inte idéer som dessa om skillnader mellan pojkars och flickors utbildningsmål ändå lever kvar i olika grupper med religiös motivering.

För egen del har jag inga problem med att acceptera att det finns viktiga biologiska skillnader men de kan aldrig någonsin motivera ett förbiseende av unika individuella skillnader.