A Markov Chain is a set of transitions from one state to the next; Such that the transition from the current state to the next depends only on the current state, the previous and future states do not effect the probability of the transition. A transitions independence from future and past sates is called the Markov Property. What we are going to do is explore Markov Chains through a little story and some code.
What it is
Lets start this post of with some techno-babble. Minimax is a depth-first search algorithm to find the least-lost strategy for zero-sum two person turn based games.
A zero-sum game is a game where, if one player loses, than another player must win the same number of points and vice-versa. For example chess is a zero-sum game because if one player wins (Lets say winning a score of +1) than the other player must lose (getting a score of -1), or the game is a draw and both players get a score of 0. We don’t give players that lose a score of 0 and the winner +1 because that would mean than one player won the game and the other player is at a draw, which is impossible in chess. The same goes for other games such as tic-tac-toe, Go, and four in a row. Another set of zero sum games are games where the total number of points is constant (think poker where players can’t buy chips) and if someone wins (a bet) than the rest of the players must lose points (money) equal to the number of points won.
Depth-first search means that we follow the algorithm all the way down until the end, and then start moving backwards, looking for the best move as we go. The reason why we have to follow the algorithm all the way to the end will become clear soon.
The other day I was playing with my Tor node’s configuration when I found out that with absolutely no trickery you can get Tor to log some interesting addresses. One of the things Tor logs is the address of edge (aka. exit) connections, which tells you what the node is connecting to but not who the connection is for.
Naturally it would be interesting to know what other people are using Tor for, so I kept a couple of days worth of logs and wrote this little perl script to parse them out for me.
I’ve been running Ubuntu as my main OS for pretty much a couple of years now and I have to say I LOVE it. The hardware support is great, tons of apps, and its free. Well “free” as in beer for sure, but not really “free” as in freedom.
This past summer I moved back to Syria, where, as you all know, the US has restricted the imports on software products for “National Security” reasons. So I’ve gotten used to Google Code being blocked, SourceForge not letting me download stuff and all that jazz. Still Ubuntu worked like a champ and I could download anything I wanted from the repos. That was until I decided to update my system to 11.04.
It sure seems easy to make a table. Anyone can do it, right? Get 1 large flat rectangular piece of wood, 4 equally tall wooden poles, 4 nails and a hammer. Nail the 4 poles to each corner of the flat rectangular bit, and you have a table. Ta daaa!