My Apprenticeship - May 2004

It's the 5 year anniversary of my 3 month apprenticeship at Object Mentor so I thought I'd revisit my original blog posts about my time there. Why? Well mostly because I used to collect LaserDiscs and really enjoyed listening to a director's commentary on something they had done many years ago. These days commentary tends to be done either right after the movie is made or because there's a financial obligation and it kinda cheapens the whole thing -- I'm hoping I can at least do better than "Larry the Cable Guy."

Anyway, this first post was written in May of 2004 before I actually started working at O.M. And since it was the first post I think I did a pretty good job setting up my background. I should point out that I was a high school physics teacher at the time and so I was giving up my summer in a desperate gamble to get a new job. Most people, when I told them I intended to become a programmer without going to college, thought I was nuts but were nice enough to nod and smile. I was pretty sure it was a long-shot myself but I had just started teaching "remedial physics" which is physics for kids who don't know algebra and have problems with calculators so I was ready to try just about anything.

And I did. Anyway, without further ado, here is my first blog post ever:

May 2004

I'm going to be spending the summer at Object Mentor learning various programming languages, agile software development, and all sorts of other stuff. In return for dealing with me, they get free labor. All the monkey-work that would be a waste of a good programmer's time will be handled by me. No, I'm not exactly sure what that will be. Should be a pretty exciting summer.

First I should talk about my background and where I am now as a programmer. Probably the first computer I ever used was a TRS 80 in grade school. I was part of some sort of gifted pull-out program and I wrote the usual things a 4th grader would (10 print "Jake is cool." 20 goto 10). During the 80's, when I was in junior high, I got my parents to buy me a TI 99 4/a and I learned Basic. I spent a fair amount of time writing programs. Extended Basic could do sprites, but was so slow that I could never get any decent video games to work because the computer never caught any collisions. All my lasers passed harmlessly though their targets.

Getting a compiler so I could write something faster cost just about as much money as the whole computer, so I was stuck with Basic. Pretty soon I got bored with it and moved on. In high school I got interested in physics and later, in college, I decided to become a physics teacher.

Now here it is 20 some years later and I'm back learning to code. Where'd all the line numbers go? And what's an Object?

About November of 2003 I started working through Eckel's "Thinking in Java." Good, but tough for someone who doesn't know C. In January I started taking an Intro to programming in Java class at a local community college. This was pretty helpful, but also pretty easy. It gave me good footing in what modern programming is all about.

Since I wasn't going to start at O.M. for about a month and I was anxious to learn something, Micah (Micah Martin -- the guy who will be looking after me during my apprenticeship) gave me a project to work on: Design an unbeatable Tic Tac Toe program.

My first pass at this went like this: A TTT board is basically a 3X3 matrix (array), so how about empty spaces being 0, X's are 20, and O's are 1? This way I can multiply all the numbers in a row (or column, or diagonal) to see if there's a win (any zero's will make the product zero, and 3 X's or 3 O's will produce a distinctive number). So checking for a win is easy. So is checking for offense or defense. Add up the row (or column, or diagonal) and a potential win will be either 1+1+0 = 2 or 20+20+0=40. So the computer can block wins, or win itself if it sees the chance. But, there are some ways to set up two winning moves at once, so I needed a series of conditional statements to handle the first few moves (kind of like in a chess program when the computer is "on book" -- playing out well researched moves). If there were no preset moves, offense, or defense, then the program made a random legal move.
Well, it worked, but the code wasn't very elegant. Here it is: (Note: Future Jake moved the code to GitHub. The "first_pass" dir contains the code I am referencing here.) Micah had me clean up the code lots and add the ability for the computer to play itself. He also wanted the human to be able to chose between X or O. Since I wrote the program with the Human always being O, this was a pretty big re-write.

After we got that cleaned up, he had me look up the minimax algorithm and use it to make the computer move. Basically minimax has the computer create a game "tree" with each possible move being a branch. The leaves are the end points: win, lose, or draw. Winning is scored +1, losing is scored -1, and a tie is (kissing your sister) 0. The computer picks the maximal score if it is the computer's turn, but it picks the minimal score if it is the opposing player's turn (based on the assumption that the opponent will play perfectly, and that he/she/it wants to win). Now if the board is empty, the computer has to look at around 40,000 moves. So the first move takes awhile. But the cool thing is that now the computer not only doesn't lose, but it can set traps for the other player. Neat.

This algorithm uses recursion to construct the game tree, and that was pretty new to me (I had used some trivial recursion before, but nothing this involved) so this re-write took a fair bit of time. Here's the code: (Note: Future Jake moved the code to GitHub. The "second_pass" dir contains the code I am referencing here.)

Doing all that filled up the month before I started nicely (keep in mind I was still teaching full time, so this was free time work).


Isn't the part where I talk about multiplying or adding up the TicTacToe rows weird? Where the hell did I come up with that? I seriously have no idea.

Comments

Popular posts from this blog

Point Inside a Polygon in Ruby

What's a Good Flog Score?

SICP Wasn’t Written for You