Maximin Connect 4 Completed
I’ve finished working on the Maximin Connect 4 program. I’ve set up a page where you can play around with the AI since I’m not sure how to embed HTML in these posts. Some general things I learned (I’ll make a separate post with more Connect 4 specific ideas once I’ve run some more tests on the AI):
- Different browsers render javascript in wildly different ways. In Chrome and with the most limited searches, each game takes about two seconds to play with pieces appearing and disappearing faster then game board can be understood. Firefox can also play a few games quickly, but starts to redraw the frame slower and slower until it only updates once every few games. Initially, I thought this was because Firefox had terrible garbage collection or was unable to deal with extended recursion. After adding better game logging, I realized Firefox was playing only about 20% less games then Chrome, but looked much worse because it had stopped rending. Opera performed about the same as Firework while IE9 failed to display the page (either because security settings stopped it from loading local javascript or because it wasn’t comparable with some aspect of the javascript).
- To make the program display better in non-Chrome browsers, I added an option to disable animation while the bots play each other. Hopefully, I don’t run into many more large gaps between browsers. The main appeal of javascript is its ability to run on everyone’s computer without downloading or installing anything. If the AI requires Chrome to run properly at some point, that advantage is lost and it would make sense to switch to another language for increased performance. After javascript, I’m most familiar with matlab but since none of the algorithms I’m planning on using lend themselves to vectorization, I don’t think it would be that fruitful. I’ve seen other AI projects done in python but I haven’t used python for years.
- javascript’s lack of a build in way to pass functions a copy of an Array instead of a reference to the Array really slows down the AI – over 1/3 of the the processing time is spent on copying Arrays.
Fixing this shouldn’t be that difficult; the psuedo code I read suggested using a ‘undoMove’ function instead of creating new Arrays every ply. Thinking that storing an extra few Arrays wouldn’t be too costly, I didn’t do that. Since creating Arrays is costly, an ‘undoMove’ function should be used.
- Implementing a working version of the psuedo code required over 20 times as many lines of code.
In my defense, my code also includes the negamax algorithm; still actually writing the eval function and hooks for the rest of the Connect 4 program to use requires more verbosity then I was expecting. Looking over the code, there is some duplicated functionality that would be nice to remove, particularly the similarities between the negamax and alphabeta code.
- I’m never sure how general to make things ahead of time. Working on my reversi game, I initially created a version that worked locally in one browser window. After playing around with the hangout API, I slowly added functionality to the handout version – syncing board state between all participants computers, only allowing the active player make move, buttons to start a new game, ect. Once I finished reversi, I wanted to add more games, but the prospect of getting a new game working only though testing on hangouts was daunting because loading new version of code takes over a minute and I’m used to iterating much faster then that. Additionally, if I found problems with code that interacted with the hangout API, I’d have to also correct the issue in the other games code. While this isn’t a huge deal with only two games, it’d become a big time suck once six or seven games were made. To get around these difficulties, I wrote a wrapper for the reversi program that generalized board updates and game endings away from the specific logic of reversi. While I was working on the wrappered reversi which worked locally, I felt fairly silly since I had already created a copy of reversi that worked locally! I think the extra effort was worthwhile – it only took me a few hours to write a checkers game with the local wrapper and it didn’t require too much more work to make checkers also work with hangouts.
