Playground
Some interactive demos of things I find interesting. I hope you do too!
The Caesar cipher is one of the oldest ciphers around. In order to encrypt a message you shift every letter by a fixed amount. For example, a shift by 3 implies that A becomes D, B becomes E etc. Julius Caesar used this for military orders, as he did not want other people reading his messages. The entire security rests on keeping the shift secret.
Try it
Breaking it
It is not hard to break this cipher as there are only 25 possible keys. A computer checks all of them before you finish reading this sentence. Even by hand you can crack any Caesar message in under a minute. Just try each shift until something reads as English. This is called brute force: no cleverness required, just try everything.
What does this say? Try all possible shifts below — one of them will be readable English.
Say you are going on a work trip and you have one bag with a weight limit of 30. You have fifteen items to choose from, each with a different weight and usefulness. Each item is either in the bag or it is not, so there are 215 = 32768 possible combinations. How do you find the best combination of items without checking all of them?
A genetic algorithm solves this without checking every option. The basic idea is to throw a bunch of random guesses at the problem and let them compete. You keep the good ones, mix them together, and occasionally flip something at random. You repeat this over many generations until the population converges on a good answer. There is no formula or gradient, just selection pressure. For this problem the optimal value is 69. Hit Run and watch it figure it out.
Items
Evolve
How it works
Each candidate solution is a row of 15 bits, one per item. A 1 means the item goes in the bag and a 0 means it stays out. There are 215 = 32768 possible combinations. The algorithm maintains a population of 20 such solutions at once — each generation scores all 20, discards the weak ones, and breeds 20 new candidates from the survivors.
The fitness of a solution is the total value of all items in the bag, as long as the total weight stays under 30. If it goes over, the score gets a penalty. The more you overshoot, the worse the score. Overweight solutions can still survive and reproduce, since they sometimes carry useful item combinations.
To build the next generation of 20, the algorithm first carries over the single best solution unchanged. This is called elitism. To fill the remaining 19 slots it repeats the following. Selection picks two parents by running two independent tournaments. Each tournament draws 3 solutions at random from the current 20 and keeps the fittest. Crossover cuts both parent chromosomes at the same random position and swaps the tails, producing two offspring that each inherit part of each parent. This happens 70% of the time. The other 30% the parents are copied unchanged. Mutation then goes through all 15 bits of each offspring and flips each one independently with 5% probability, so on average about one bit changes per offspring. Both offspring are added to the next generation and the process repeats until all 20 slots are filled.
Say you are dealt pocket aces and your opponent has king-queen suited. You want to know how likely each of you is to win. You could work it out exactly by going through every possible way the remaining cards could fall, but before the flop that is over a million combinations.
Instead you just sample. You deal the remaining cards randomly, see who wins, and repeat 50 000 times. The fraction of times each player wins is a very good estimate of their true odds. Pick two hands, optionally add some board cards, and hit Simulate.
Hands
How it works
Each iteration takes the known cards, fills in the rest of the deck at random, and runs the board to completion. It records who wins and moves on to the next sample. After 50 000 iterations the win counts are divided by the total to get a percentage. More iterations give a more accurate estimate, but 50 000 is already very close to the true value.
At the end of each runout, both players have 7 cards. To find the best hand you check all 21 possible five-card combinations and keep the highest ranked one.