tl;dr While creating a brief Clojure tutorial for people with zero programming experience — A Gentle Introduction to Clojure Through Turtles — we realize that we should be teaching functions all the way down.
As in probably all such courses in any language normally taught to beginners, the concept of a “variable” was introduced very early on in the curriculum:
And look, we can change it (hence the term “variable” — watch it vary!):
This was certainly the order in which I learned these language features X years ago when I first taught myself BASIC and Pascal, so I didn’t think to question it — even when most of the beginners displayed noticeable pain and confusion at having the equals sign they had learned in second grade repurposed as this strange new thing called the “assignment operator”.
It was one of many humbling eye-openers for me, as I watched people grappling with things I learned a long time ago in a galaxy far, far away.
As will probably be clear by now, I had never taught a class before.
Clojure: functions before vars
The weekend after the class was over, I volunteered with ClojureBridge — an organization working to increase diversity in the community around the Clojure programming language, by facilitating one-day beginner-friendly workshops in Clojure, for women.
(It’s based on its successful predecessor, RailsBridge, whose purpose is to… well, you get the idea.)
Our instance of the workshop — ClojureBridge NYC — was organized by Stuart Sierra of Cognitect, who did a great job putting it together and organizing the volunteers. I and Brian Gruber (an engineer at Meetup) were assigned to lead the beginner group — the people with no programming experience whatsoever.
I was very curious to see how this would go, as Clojure is a language dear to my heart but not one that’s normally taught to beginners. I think one of the primary reasons for that is that it’s not normally used by beginners, so the tooling and the ecosystem around it are mostly for experienced programmers. But we’d be introducing it with a recently-developed beginner-friendly IDE, Nightcode, so I had high hopes.
Brian and I decided that while the extensive slides provided by the ClojureBridge organization are really good for people who were at least a little bit familiar with another programming language and wanted an overview of Clojure — they go over the basics of the language, the syntax, and a few of the main data types, and culminate in some turtle graphics using a small app written for the occasion — we needed to come up with a supplemental lesson plan for total beginners. Ideally, this lesson plan would accomplish two goals in the few hours that we had with the workshop participants: 1) Show them how to do something cool, and 2) Give them a reason why they might want to continue studying Clojure (or programming of any kind) in the future.
To that end, we decided to skip the list of datatypes, and skip even talking about what a datatype is, and jump straight to the turtles, in the interest of providing immediate visual feedback.
Brian put together a basic outline, and my plan was to flesh it out into a README. Here was the outline:
- Have fun with turtles
- Learn about programming
- Learn about turtles
- Hello World — print something
- Turtles — forward, right, left, make some shapes
- Arithmetic — +, -, *, / — then use arithmetic in turtle commands (stealth intro to function composition!)
def— assign names to values
defn— assign names to values which also happen to be functions
- More fun with turtles — reuse code using
- Culminating exercise — make a function to draw a polygon of arbitrary size and arbitrary number of sides.
It looked great to me, and I fleshed out a basic README for the students, but when we looked at my end result, we realized something — it wasn’t doing a very good job of explaining why anyone would ever want to use
def, in these very simple examples. The best I could come up with was “in case you forget what angle 90 degrees is”:
And indeed, when I later showed something like this code sample to beginners in the workshop, their reaction was usually along the lines of, but 90 is shorter to type. In other words, why would you want to give a second name to something (“right-angle”), when you already have its original name (“90″) that more clearly indicates the nature of the value in question? (Of course, it would be different if we were dealing with long strings instead of short numbers, but that wasn’t the case here.)
Functions, on the other hand — the thing that is taught much later in most programming classes — were quite easy to explain the purpose of. Even functions that are purely used for side effects and take no arguments are obviously useful to eliminate code repetition:
And then when you start parameterizing them, their power becomes obvious:
How did ClojureBridge go?
As it turned out, we had a particularly excellent volunteer turnout, so after I gave an hour-long lecture from the existing curriculum to everyone — beginners and experienced programmers alike — for the rest of the day every student pretty much had an individual tutor.
As someone who had just taught a ten-week course to people of wildly different experience levels, to all of whom I was supposed to have taught the same material to by the end, this was a dream. Everybody got to work on exactly what they wanted to, at their own pace, with as little or as much guidance as they wanted and with multiple mentors hanging around to answer questions at all times. A good time was had by all.
As for the beginner’s supplement that we wrote, I was actually scrambling to finish it during the workshop, so it never got used in its entirety, but we used enough of the concepts in practice with the workshop participants to confirm that we had been right in our intuition that
defn should come before
def. Here is the end result, slightly fixed up since the workshop:
Help out ClojureBridge
Want to increase diversity in the Clojure community by volunteering with ClojureBridge? You can go here to find out what’s already going on in your city, or to find out how to organize your own ClojureBridge event!
In the past few months I’ve been endlessly entertained by a browser plugin called “Cloud to Butt.” There are a couple different versions on the Interwebs, but the most recent one takes every instance of the word “cloud” on any website you’re looking at and turns it into “butt,” and in addition, “the cloud” becomes “my butt.” You can find the code for the latest version here, and the Chrome extension here.
I recently decided to provide the same treatment for a word I’ve seen too much recently in tech and business articles, on book covers, and on Oakley ads in the Union Square subway station: “disrupt.” For those who want to cut straight to the chase, here are the links:
I’m quite happy with the outcome now, but I did not immediately settle on the word “bullshit” as the replacement word. My friends and I discussed a number of other possibilities early on, including “fart,” “poop,” “shit,” “eviscerate,” and “disembowel.” The word had to retain some of the juvenile humor of “butt” (which “fart” and especially “poop” had in spades), while also capturing some of the unnecessary, unpleasant, and hilariously out-of-place violence of the word “disrupt” when used in articles about startups that want to help you organize your email (best represented by words like “disembowel”).
In the end, we found “bullshit” to be funnier than all the others, as it connotes the best mix of immaturity and aggression. It also has the same number of syllables as “disrupt,” which generally helps the affected web content to retain some of the flow that the authors originally intended, albeit with a different meaning.
The word “bullshit” is not, of course, perfect. Companies that get called “bullshit” in websites transformed by the plugin are unfairly maligned if they are doing good in the world, and they are let off the hook if they are doing bad (in the latter case because calling their efforts “bullshit”, i.e. pointless and illusory, is inaccurate if they are accomplishing real harm).
It is also important to point out that Disrupt to Bullshit is not a commentary on any particular theory of business cycles. I didn’t even know until recently that the concept of disruptive innovation is pretty much owned by one guy, a Harvard Business School professor named Clayton Christensen, who’s been talking about it for almost twenty years. He seems like a nice person, but from what I’ve read so far, his attempts to apply the theory of disruptive innovation to the non-profit and governmental sector, or even to transactions between large enterprises (as opposed to economic activity involving individual consumers), seem misguided and possibly dangerous to society.
But I am, as of yet, not fully informed on this topic. I might get back to this in a blog post after I’ve done some more research and read a couple of his books. In the meantime, this plugin is not about him or his work. In fact, I’ve seen Christensen agree in an interview that the word “disrupt” has gotten totally out of hand. So I think he might enjoy this plugin.
And I hope you all enjoy it as well. I offer it for the entertainment of anyone who wishes to install it in the privacy of their own browser, in the hope that they may take full advantage of the comedic opportunities afforded to us all by the current over-saturation of the word ‘disrupt.’
And in a later blog post, I’ll get into some of the technical challenges involved in making the plugin. Turns out verbs (like disrupt) are a lot harder than nouns (like cloud)!
Like many of my weeks in Hacker School, this one started out meandering and got more focused towards the end. Some of my fellow students have told me they fall into the exact opposite pattern — they start out strong and then peter out — but I tend to get my wind at the end of the week and try to do as much as I can over the weekend.
That’s not to say that I in any way regret puttering around. One of my favorite things to do at Hacker School is to get into a conversation with someone about something I know nothing about, and then end up working on the project with them for a little while. Often I end up following some tangent that turns into a project idea for later in the summer, that I never would have thought of.
For instance, on Monday morning, my fellow Hacker Schooler Sunil Abraham got into a long conversation across the table from me with Jessica McKellar, our resident for the week. One of her specialties is networking, and Sunil was having her explain a few things, because one of his goals for the summer was to learn more about networking and the protocols governing the internet. One of his other goals was to learn a language like OCaml or Haskell, so he figured he would follow Jessica’s suggestion to re-implement the Unix utility ping, but he wanted to do it in OCaml.
So I figured I’d help him out, since I knew a little bit about SML, a forerunner to OCaml, and since I’d never even thought of implementing a network utility until that morning, so I was curious to see if it could be done.
Two mornings later, after having switched from trying to implement ping to trying to implement traceroute instead (for reasons too obscure to go into in this blog post), we wisely abandoned this project, but I came out of it knowing quite a few little tidbits I never knew before, like:
- How to get OCaml running in VIM and piped to a repl using the utility tmux, which I’d never used before,
- How to use the OCaml package manager (opam),
- How to access C networking utilities using the OCaml socket library,
- and last but not least, that traceroute is a total hack!
Let me explain that last point.
Before this week, I had a big misconception about what traceroute actually does. I assumed that it traces a specific route, meaning that a packet leaves my computer and sends back messages from every node along the way until it reaches its target, but that’s not what happens at all. What actually happens is that for each hop, three packets are sent to the target address with a special field called a TTL (Time To Live) set to expire immediately, and return messages to the originator. Then three more packets are sent out to the target, but set to expire after two hops, at which point the nodes two hops away send back messages. Then three more, set to expire after three hops, and so on, until the target is reached or a node is encountered which blocks traceroute (this happens a lot). So the path may or may not represent a path that any particular packet actually took, but it’s likely to be a close approximation, unless something major happens to the internet in between when the originator sends one set of packets and when it sends the next.
In case you’ve never seen a traceroute output, this is what it looks like. Notice that some nodes have multiple addresses, meaning that the three different packets went to more than one place, but that there are always three times listed, for each line number:
Harrington-MacBook-Pro:~ richardharrington$ traceroute nytimes.com traceroute: Warning: nytimes.com has multiple addresses; using 184.108.40.206 traceroute to nytimes.com (220.127.116.11), 64 hops max, 52 byte packets 1 10.0.1.1 (10.0.1.1) 1.044 ms 0.901 ms 0.704 ms 2 10.32.0.1 (10.32.0.1) 12.072 ms 9.925 ms 13.181 ms 3 gig-0-3-0-8-nycmnya-rtr2.nyc.rr.com (18.104.22.168) 12.111 ms 13.007 ms 14.814 ms 4 bun101.nycmnytg-rtr001.nyc.rr.com (22.214.171.124) 15.769 ms 20.855 ms 19.957 ms 5 bun6-nycmnytg-rtr002.nyc.rr.com (126.96.36.199) 18.767 ms 20.741 ms 13.818 ms 6 ae-4-0.cr0.nyc30.tbone.rr.com (188.8.131.52) 12.291 ms 16.625 ms 20.841 ms 7 ae-1-0.pr0.nyc30.tbone.rr.com (184.108.40.206) 14.191 ms 15.702 ms 220.127.116.11 (18.104.22.168) 14.615 ms 8 xe-4-2-0.edge4.frankfurt1.level3.net (22.214.171.124) 17.473 ms 13.600 ms ae9.edge3.newark1.level3.net (126.96.36.199) 13.725 ms 9 ae-21-52.car1.newark1.level3.net (188.8.131.52) 15.267 ms ae-11-51.car1.newark1.level3.net (184.108.40.206) 11.700 ms ae-21-52.car1.newark1.level3.net (220.127.116.11) 14.945 ms 10 new-york-ti.car1.newark1.level3.net (18.104.22.168) 17.421 ms 19.263 ms 14.790 ms 11 22.214.171.124 (126.96.36.199) 13.693 ms 17.985 ms 16.313 ms
Interestingly, its use in traceroute is not the main purpose of the TTL field, which was intended as a way for unreliable communications protocols to signal a message failure.
Communication protocols that guarantee delivery of packets, like TCP (the protocol layer that underlies web pages and email, among other things), use very robust communication channels, including requests for redelivery of packets that fail. The originator certainly knows very quickly when a packet has not reached its destination. But there are other protocols, such as UDP (used for streaming video, among other things) and ICMP (used for all kinds of things, particularly message-passing), which are much cheaper and more efficient by virtue of the fact that they’re not actually guaranteed to reach their destination. Packets sent via these protocols need some simple way to alert the sender that the packet has failed, though, and they normally do this by having their TTL field set to a high number (the default is 64, I believe) and decremented by one at each hop. If the TTL reaches zero at any node short of its destination, the node drops the packet and sends an ICMP “Time To Live exceeded in transit” message back to the originator of the packet.
So traceroute takes advantage of this system by sending out messages with TTLs of 1, then 2, then 3, etc., corresponding to the line numbers above. The contents of the message are irrelevant; only the TTL fields themselves matter.
So it’s a hack, but as my fellow Hacker Schooler Martin Törnwall points out, it’s a very elegant hack. And something I may try to implement in Clojure or ClojureScript later in the summer. If I have time.
I wrote a previous post about what I spent the majority of Week 7 doing — working on the Robotwar project — but here’s a couple more items, in the interest of giving people an idea of all the little things that go on there:
- A back-and-forth e-mail exchange over the weekend between fellow Hacker Schooler Sebastian Bauersfeld and myself over what is the best algorithm in Clojure to generate the powerset of a set, that is, the set of all subsets of that set (including the full set itself and the empty set). My first version was quite clever but somewhat convoluted and, it turned out, totally wrong — it only worked for sets of three items or less, which is all I had tested it on:
Sebastian’s was better — instead of doing weird stuff with rotation and splitting sets into two pieces as above, it had the correct idea, which was to progressively fold each element of the original set into the growing list of subsets:
But then he showed me this one that he found on the internets:
which put us both to shame. Actually, Sebastian’s was pretty close — it just used direct recursion instead of the `reduce` function. Mine was very far off.
But that last one is so simple! So short! So obvious in retrospect! (although, to be fair, it returns a sequence, not a set, but making it return a set would just require one more function call).
Sometimes I feel as though I have a mountain of things to learn, but then I’ll see that I was able to figure out how this guy’s powerset function works almost immediately, which I would NOT have been able to do a month ago. So although I don’t always see it day to day, occasionally I see inklings of the possibility that I will look back on this summer and realize that I learned an enormous amount.
In the early part of Hacker School, I was involved in a study group making its way through the book, Types and Programming Languages, by Benjamin Pierce. It’s a very interesting book, and I started reading it not only because I felt I needed a better grounding in lambda calculus and type theory, but because I thought I would actually enjoy it. I’d really loved a class I took on Coursera last spring, Dan Grossman’s Programming Languages course, and the material in TAPL seemed to be a deeper treatment of some of the theory brought up in that course, in the same way that my college course in abstract algebra (which I loved) was a re-examination of grade-school arithmetic. I’m not comparing Grossman’s course to grade school, but you know what I mean — first you learn how to use the stuff, and then you really delve into how and why it works in exhaustive detail.
In the third week of Hacker School, we had our second meeting of the group in the “fishbowl,” which is what we called the central room in the Hacker School space that has windows on all four sides looking out on… the rest of Hacker School.
I’d already started to spend a lot more of my time coding and a lot less time reading the book, and I was mostly unprepared for the meeting. Once the group got past the part of the chapter on lambda calculus that I had read and understood, I was completely lost. I wasn’t exactly sure when I would catch up, either, as I was feeling less and less inclined to spend my summer poring over a graduate level textbook in type theory, not having ever taken a CS course in my life.
At a certain point during the study group meeting I was reminded of my friend Krista, who grew up in Manitoba and was a star cross-country runner in high school, winning province-wide awards. Then one day she decided to stop doing cross country, and followed through on her decision immediately — in the middle of a race. I’ve never watched cross country myself, but apparently, unlike in track races, it’s quite common to find yourself alone for stretches of time, and it was during one of these stretches that she thought to herself, “I don’t want to do this any more.” She slowed down, walked to the finish line, and never ran another race.
Inspired by her example, I decided to leave the fishbowl and go work on my tic tac toe project in Clojure. I felt pretty good about it. I still think it’s incredibly interesting material, and I have greatly benefited since then in my Clojure studies from the refresher course on set theory and the definition of a function in the first chapter of the book, but I never looked back. I’ve spent my summer since then making things and helping other people make things. Some day, when I’ve made enough things, I’ll go back and look at how exactly they’re made, from the ground up.
This experience has now repeated itself a number of times over the summer. Being as unstructured as it is, Hacker School is an exercise in knowing when you need to keep persevering on a project, and when you’ve learned as much as you’re going to learn and need to move on, even if you’re not “finished” in any traditional sense.
For instance, this past week, fellow Hacker Schooler Sunil Abraham and I spent a couple mornings trying to re-implement the Unix utility traceroute in the OCaml language, not knowing much about OCaml or about networking. Eventually we wisely gave up on that. I now know slightly more about networking and the traceroute utility, but that’s the subject of another post…
This week I made slow but steady progress on compiling the Robotwar code down to the virtual machine code that came with the original game. I paired with a couple of the facilitators and residents (one — Kevin Lynagh — over Skype) and reworked the code to the point where I liked it, but I spent perhaps too much time refactoring and not enough time moving forward. The question of how much time to spend making one’s code look elegant and perfect is a tough one, and I think I may have been erring too much on the side of endless tinkering, because it’s Hacker School, not a workplace, and no one’s going to stop me. For instance, here are four versions of a parsing function that I created in consultation with a few different people, each of whom had different opinions about how it should be done.
The first one uses an anonymous function, the second two use ‘for’ comprehension, and the last one uses loop-recur. I’ve been getting the feeling that directly using the loop-recur structure is less Clojure-y, but I could be totally wrong about that. In some ways it’s the Wild West, and best practices are still being developed.
In the end I think all these versions of the parsing function are fine, with the possible exception of the loop-recur one, because it has no provision for dealing with the case for when you get to the end of the list (is that called the null case?). In fact, it relies upon the fact that the last function in the parser-priority list actually always returns an error string no matter what its input, but this function shouldn’t have to know that.
These are all fine, really. In the end, I think I prefer the one I had in the first place, but only slightly.
As one of the facilitators pointed out, I should arguably not even be reducing this Robotwar source code to its object code, because they’re so similar (see here for an example), and why not just write an interpeter, and have it start doing things already? Like having robots fight? I do wonder sometimes why I’m sticking to the exact form of the original game, but it’s been fun so far, and I’ve also had this idea recently that I want to write a compiler from Scheme down to this Robotwar VM code. We’ll see if I have time for that!
Every Monday night at Hacker School we have a lecture of some kind, usually by one of the residents. Last Monday night it was a super-interesting one by our resident for the last two weeks, Peter Norvig, about natural language processing. Turns out with a few simple lines of Python and a large enough corpus of words (like a book), you can do an amazing amount of things, such as correct bad spelling mistakes and determinewhichwordsshouldbeseparatedwhenthey’rewrittenwithoutspaces.
“Trie” is short for “retrieval,” and the person who first came up with it pronounced it like “tree,” but people since then have pronounced it like “try” in order to distinguish it from other kinds of trees. For more fun facts and a nice diagram, see the Wikipedia article.
Each node can optionally hold a value as well, but I’m told by fellow Hacker Schooler Sunil Abraham that one of the most obvious uses of this kind of data structure is for auto-completion. If someone has already typed in “at”, and the only other words in your corpus that they might be searching for that begin with those two letters are “ate” and “atelier”, you can start your search very efficiently for words to put into a drop-down menu, starting at the “at” node in the trie.
The feature set of my final version of the code is kind of a hybrid of what I thought a trie was supposed to be for (an efficient key-value store), what Doron and Michael originally focused on (a way to count the frequencies of words), and what Sunil told me it’s mainly used for (auto-completion). Here it is:
(This code can also be found on github.)
tl;dr It’s been a bit of a whirlwind these past few weeks, but I’m back on track with my Robotwar project.
Before the end of the 4th week of Hacker School, I went to Ottawa, Ontario for five days to perform in a comedy I wrote with my friend Chris Kauffman, at a theater festival there (see harringtonkauffman.com). It was a lot of fun and I was able to reconnect with some old friends from the Canadian fringe theater circuit, a part of my life that seems very far away this summer. But I had to spend more time preparing for it than I expected, since I hadn’t done the show in two years.
I returned on Monday, July 1, and the 4th of July was the following Thursday, so my 5th week of Hacker School ended up being only two days long.
Because of all this, I got a little off my stride in terms of the big project I was theoretically going to work on over the course of the Hacker School batch: the reverse engineering of the Robotwar game. I started to feel a bit adrift again, as I had in the beginning of June. I wasn’t sure I was appropriately equipped to thrive in the unstructured environment of Hacker School, and I was nervous that I wouldn’t accomplish a tenth of what I’d hoped to accomplish. By the end of the 5th week, I had only barely gotten started on Robotwar.
But late in the 6th week (which just ended), I got my second wind with the help of a long pairing session with one of the facilitators, Zach Allaun, who helped me tease apart the various steps in the compilation process for the Robotwar language, making each one more sensible.
The end result of the compilation step (which itself is only the first of many things I have to do to make a functioning game) will be to turn this:
SCAN AIM+5 TO AIM AIM TO RADAR LOOP IF RADAR < 0 GOSUB FIRE GOTO SCAN FIRE 0-RADAR TO SHOT ENDSUB
SCAN 0 , AIM 1 + 5 2 TO AIM 3 , AIM 4 TO RADAR LOOP 5 IF RADAR 6 < 0 7 GOSUB FIRE 8 GOTO SCAN FIRE 9 , 0 10 - RADAR 11 TO SHOT 12 ENDSUB
And that begins with lexing. For those of you (like myself before this summer) who have never heard of the term "lex," it means "lexical analysis." It's the first step in the process of translating human-written source code into machine-readable code, and it involves separating the strings of source code into words and other meaningful chunks. It's also the most notoriously difficult and tedious step, because a lot of syntactic forms look obvious to us but are baffling to a computer.
This Robotwar language is actually pretty simple in that respect -- the only tricky part is determining whether "-" characters are binary subtraction operator or unary minus sign operators.
So here's the version of the lexer I had before I worked with Zach. It separates strings into tokens and also adds an index property to each token, which will be useful information later when we add error reporting to the program. Note the nasty minus sign logic, which checks to see whether the previous token is a numeric value (either a number literal or a register name).
Also, note the use of the
core.match module to do pattern matching. Since it's not binding any variables in the matches, one could argue core.match is overkill here, but I feel it does prevent me from having to use a series of suspiciously similar "if" expressions -- that is, if we're in the middle of parsing a token do one thing, otherwise do something else -- for each of the cases.
I was thinking of having one parsing step after the lexing step in the above code, and then a compiling step down to the Robotwar virtual machine code. But after this week I realized that I should have as many steps as I need to make it easy, and I also realized that there's no reason for this first step to have any logic in it at all. I ended up separating a couple of things out into their own functions: stripping out the comments (which happens before the lexing step now) and dealing with the ambiguity of the "-" character (which happens after the lexing step). The minus sign issue turns out to be pretty easy to do in the next step, the parsing step, once we've isolated all the operators and words in the lexing step.
Last but not least, I jettisoned
core.match for the time being, since I realized that by getting rid of that minus sign nonsense, I was down to a level of simplicity where I could use regular expressions (it's possible I could have used them before, but I suspect not, and I wasn't quite enough of a regexp master to attempt that one). Here's the new code for the lexer, which is drastically shorter while only sacrificing a tiny bit of functionality that is better off elsewhere in the program anyway:
All that remains now is parsing, compiling to the virtual machine object code, writing an interpreter for it, and making a graphics engine to show robots fighting!
Last but not least, the above code can be found on github in the following locations:
tl;dr Tic-tac-toe, and more Tic-tac-toe
I’d gotten started on my Tic-tac-toe AI (artificial intelligence — a pretty fancy word for a Tic-tac-toe algorithm, but that’s the term people use) in Clojure at the very end of the previous week, and my plan for Week 3 was to wrap that up by the end of Monday, then do an implementation of the Game of Life in Clojure, then start working on my Robotwar project (see my blog post from Week 2). By the end of the week, I was still working on Tic-tac-toe. This was a little discouraging, but I was learning a new language, so I tried to give myself a break.
I actually got a basic Tic-tac-toe AI going fairly easily, using a heuristic algorithm, which means a series of basic rules for picking good moves. Mine picked them in the following order of priority:
- Pick a square that will be a winning move.
- Pick a square that will prevent the opponent from making a winning move on their next turn.
- Pick the center.
- Pick a corner.
- Pick any other free square.
This pretty much works every time, but as I learned early in the week, there is a more elegant solution, called the minimax algorithm, which can be applied to any zero-sum game like Tic-tac-toe (or really any competitive game, I think, with some modifications and compromises).
Minimax seemed like magic to me when I heard about it. The basic idea is simple to understand: when given any board, either at the beginning of the game or in the middle, have the AI play out every possible combination of moves, figure out who wins at the end of each branch in the tree of all possible moves, and work back recursively to figure out what is the best move for a given player at the given point in the game. (When doing the calculation, the AI makes the assumption that each player will play as well as the AI does.)
There are a number of variations and optimizations for speed, the most important of them being the one where you have to evaluate intermediate game states, because playing every game out until the end would consume too many computing resources (I gather this is true of pretty much any game except Tic-tac-toe). In this version of the algorithm, you set a depth limit, say 10 moves into the future. Then for each branch where the AI ends up calculating 10 moves into the future before it reaches a final board, it has to use some kind of heuristic algorithm to analyze that board 10 moves into the future and figure out which player that board is most favorable to. This means that even in games like Tic-tac-toe where there are only a few outcomes (win, lose, and draw), point values are assigned to intermediate boards so that they can be compared with each other.
The minimax algorithm gets its name from the fact that one player is designated the “maximizing” player, and the other player is designated the “minimizing” player. The maximizer wants the score to be as high as possible, and the minimizer wants the score to be as low as possible. There are a few variations, but a common version is that winning boards are assigned the value positive infinity (if it’s the maximizing player’s turn) or negative infinity (if it’s the minimizing player’s turn), and all boards that must be calculated in an intermediate state receive positive or negative scores, of various values. So in evaluating any given square before the depth limit is reached, its value is the numerical maximum (for the maximizing player) of all the values of the opponent’s next move, or the numerical minimum (for the minimizing player).
If you understand this immediately and can write out the algorithm, you’re way ahead of me. It actually took me a week to get this working. What I kept getting stuck on were the signs, and what it meant for one player to arbitrarily be positive and the other negative.
I ended up finding it helpful to first implement a preliminary version of the algorithm — one without numbers. In a game which has only a few possible outcomes (in the case of Tic-tac-toe, win, lose and draw) and which can also be played out to the end, it is actually not strictly necessary to use numbers for the return values of the recursive function. You can instead use symbols or strings like “win,” “lose,” and “draw,” or better yet, “X”, “O”, and “draw”. The reason it’s better to use “X” and “O” instead of “win” and “lose” is that if you use “win” and “lose”, you have to pass the opposite symbol (“win” instead of “lose”, or vice versa) up the chain at each level of the recursion, because one player’s win is the other player’s loss. If you use “X” or “O”, you don’t have that problem.
But we’re going to start with the most arduous version here, the version that uses no numbers and uses the generic symbols :win and :lose instead of absolute player-specific values like :X and :O. I wrote it because it helped me to work through the logic behind the algorithm, and it also helped me appreciate the numerical version, once I got to it!
Some helper functions not included below include
winner, which returns :X, :O, or nil,
board-full?, which is self-explanatory, and
free-squares, which returns a set of coordinate pairs representing all the free squares on the board. In the first
potential-board is a new board with a marker added. The values of the squares are either :X, :O, or :e for empty, and the values that the minimax function may return are :win, :lose, and :draw.
And now, here’s the eventual version I wrote using the more usual numerical version of the algorithm to compute the value of a square in Tic-tac-toe. It needs to use the Clojure
declare form because it involves two mutually recursive functions, but it is more elegant than the one above.
Because I’m still not bothering with intermediate depth calculations — I haven’t gotten to that point in my study of the minimax algorithm — I’m just assigning the arbitrary values 1 and -1 to wins by X and O. I could have actually used any positive and negative numbers.
In the version below, 1, -1, and 0 are actually used to represent both the values of the markers (X, O, and empty, respectively) and the return values of the minimax function (X wins, O wins, and it’s a draw, respectively). The
final-score function statically analyzes a board and returns 1 for X winning, -1 for O winning, 0 for a draw, and nil for a game that is not over.
Note the lack of the need for an
opposite-result function, and also the lack of a need for a complicated
reduce operation (we can just use the
max functions instead of
Short Answer: So that this will work:
What confused me when I first started learning this stuff was the use of the word “prototype” as a property name. It seems like the “prototype” property of an object should refer to that object’s prototype, but it doesn’t.* A constructor’s “prototype” property is not a pointer to the object that the constructor looks to when it wants to start looking up its own prototype chain; rather, it is a pointer to the object that the objects created by that constructor look to when they want to start looking up their prototype chains.
Therefore, when one of those objects wants to see which object created it, it accesses its “constructor” property. Since it has no “constructor” property of its own, it starts up its prototype chain to find a “constructor” property. The first place it looks is the “prototype” property of its constructor function, which contains a property called “constructor,” and that “constructor” property should point to the constructor of the object that started the prototype chain lookup.
In order for that to work, every constructor has to have a “prototype” property which has a “constructor” property which points back to itself, the constructor, so that objects created by that constructor will be pointed to it when they start looking up their prototype chains. So that’s why MyObject.prototype.constructor == MyObject.
Keep in mind also that this “constructor” property is totally unsafe and not to be trusted, unless you take care to keep it intact. At the time any function is defined, it gets a “prototype” property which points to an object having exactly one property: “constructor.” After that, it’s fair game. You can reassign the “constructor” property to anything you want, or, more commonly, you can reassign the entire “prototype” property itself, which will eliminate the “constructor” property. This can sometimes be convenient, but if you care about preserving the “constructor” property (and you may not), then you have to reset it manually after reassigning the “prototype” property. For instance:
* For that, you used to have only the special property __proto__ which was non-standard and only worked in certain browsers, and now in ECMAScript 5 you have Object.getPrototypeOf(object)