Recently I’ve been doing a lot of work with awk, and I’ve been really impressed with all of the features available in its programming language. This got me to thinking about what kind of programs one could write in awk, that go beyond just text manipulation.
So, I decided to see if I could implement Tic-Tac-Toe with AI in awk. The quintessential project for undergraduate AI classes, it’s long been a favorite of mine because it’s not too long, but also not completely trivial.
My implementation, which is ~200 LoC, uses the negamax algorithm to scan the entire game tree for Tic-Tac-Toe, and gives the player the option to either go first or let the computer go first. The performance isn’t too bad: the computer’s first move (if the player goes first) takes about 10-15 seconds, but after that, it’s pretty much instantaneous.
I had a lot of fun implementing this, and there were some interesting things I encountered along the way:
- A large chunk of my time was spent trying to debug my implementation of the negamax algorithm. Unfortunately awk doesn’t really have a debugger per se, so I sort of cheated and implemented the algorithm in perl first, then translated that implementation into awk.
- The one blunder that really tripped me up was the find_best_move() function, which uses negamax to find the computer’s best move. I erroneously called negamax with a ‘color’ or 1 (instead of -1) and I didn’t negate the score that came back. Essentially, the thing to remember is the for loop that scans for the best move should look exactly like the for loop inside negamax, except that you’re recording what the best move is and returning that instead of the heuristic value of the board.
- One super-important detail in awk is that to make a variable local to a function, it has to be part of the parameter list. If it’s not, the variable comes into existence in the global namespace, which can lead to some very subtle bugs.
- Portable awk programming is tough! There are a lot of differences between implementations of awk, and getting one script to work on all of them is a real challenge.
- awk’s regex engine makes for a nice, fast board evaluator if you can create a regex to determine if a win exists for a player.
- One interesting way to view writing big awk programs is to think of the rules as ‘event handlers’, and each line of input as an ‘event’. This helped me avoid having to use getline() everywhere, and I think is a nicer way to structure the overall program.
If you want to try out the script yourself, just download it and run with the command awk -f ttt.awk. I’ve tried it out with gawk and BSD awk, and those both seem to work fine, but the script doesn’t work with AIX’s awk (due to issues with the split() function).
This entry was posted on Tuesday, March 9th, 2010 at 3:24 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
Leave a Reply