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 = 32 768 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 = 32 768 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.
In a real game you never know your opponent's exact cards. The best you can do is put them on a range: the set of hands they could be holding given how they play. That works here too. Switch a player to Range and paint their possible hands on the grid. If a hand is only in there some of the time, give it a lower weight. Then add board cards if you want and hit Simulate.
Hands
How it works
Every sample starts by giving both players a hand. A fixed hand is used as is. For a range the simulation draws one of its hands at random, and a hand at half weight comes up half as often. Then the rest of the board is dealt, the hands are compared, and the winner gets a tally. Divide the tallies by the number of samples and you have each player's equity.
Two hands can never share a card. So if Player 1 draws A♠K♠, Player 2 cannot hold anything with the A♠ or the K♠ in it, and the simulation simply redraws the deal. Throwing these deals away spreads their probability over the hands that are still possible, which is exactly what should happen. Poker players call these blockers: holding an ace makes it a little less likely that your opponent holds one too.
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.
A range against a range needs hundreds of thousands of samples for a stable answer, and running that on the page itself would freeze your browser. So the work happens in a web worker, a separate thread the browser runs next to the page. The page only draws the progress bar, and you can cancel a long run whenever you want.