December 11, 2010

Bulk view

XKCD, tic-tac-toe, and fractal goodness


I was delighted to see an analysis of Tic-tac-toe on XKCD. Here is a small part of the remarkable graph format XKCD uses to show all the possible outcomes. It shows all the possible moves and the optimal responses for games that start with X in the top left corner and O in the center.

Tic-tac-toe is a good game for computer science. The rules are easy to code. Unlike chess, go, or poker, it’s possible to write a simple program that plays the game perfectly. Games finish in at most nine moves, so it’s easy to test. By considering similar states (starting with X in the top left corner is similar to starting with X in the bottom right corner, and so on), you can learn about the tradeoff between efficiency and complexity. You might start out creating a interface for playing Tic-tac-toe, and then move on to building a system that plays it against you.

A few years ago, W- was active in a LEGO group that organized occasional contests. They were thinking about competing to build a robot that could play tic-tac-toe using a marker and paper. I played with the idea of making a similar graph of all the tic-tac-toe possibilities so that I could encode it into a program, but I never considered anything close to this brilliant format.

The compactness of this graph is amazing. The recursive fractal goodness of it all warms the cockles of my geek heart. And yes, on first look, it seems really complicated and confusing, but if you can figure out enough to find the first few steps, everything will fall into place and you’ll be able to follow it all the way down. I love it like I love iterations of the Peano space-filling curve, the Koch snowflake, and the Sierpinski carpet.

What I like even more is the fact that the community has been debugging the graph, discussing optimal strategies that start with non-corner moves, sharing complete computer-drawn graphs and other sources for similar diagrams (including books). Ahh, geekery…

Image excerpt © 2010 Xkcd – Creative Commons Attribution Noncommercial 2.5 License

Weekly review: Week ending December 10, 2010

I fell off the wagon of early-morning wakeups. Ah, Angry Birds! I’m going to try a few things to make it easier to go to bed, such as using a timer to limit potentially engrossing activities, reminding myself of my reasons for going to bed early and staying up late, and making a list of fun and productive things I could be doing instead of playing. Yes, playing a game that W- and J- are also into is fun for social bonding (“How did you get past that level?”), but there’s so much more awesomeness to be done.

From last week’s plans

  • Work
    • [-] Drupal: More Drupal work – build tricky parts of project M
    • [X] Finish blog post for Dec 10 launch
    • [X] Help with Slideshare IBM network
    • [X] Write more posts for conference toolkit
    • [-] Work on PDFA for level 4 IT Specialist
    • [X] Discuss social media and telecom over lunch
    • Helped Jean get started on project S
    • Wrote project onboarding documents
    • Helped Elena get started on project M
    • Sent ITSC details
  • Relationships
    • [X] Help with homework
    • [-] Buy fleece for making throw
    • Had a wonderful cooking session with the Hattoris
  • Life
    • [-] Design my own grocery list / tracking app for the Android – started sketching, wrote some of it
    • Installed timer on Android
    • Experimented with tracking time

Plans for next week

  • Work
    • [ ] Build tough parts of Project M
    • [ ] Continue to refine Project S
    • [ ] Meet Anna Dreyzin for Lunch
    • [ ] Have PDFA mentoring chat
    • [ ] Illustrate networking tips
  • Relationships
    • [ ] Go to gaming night with Linda and Tim
    • [ ] Send more cards
    • [ ] Buy fleece
  • Life
    • [ ] Work on MobileOrg
    • [ ] Experiment with timing