8 ms·
In 2008, I was taking COS 217 at Princeton - our final project was to write a program to play Othello competitively. We were told to use alpha-beta-pruning for
by lordofmoria 4y ago
In 2008, I was taking COS 217 at Princeton - our final project was to write a program to play Othello competitively. We were told to use alpha-beta-pruning for grading, but that there would be a tournament at the end of class, so we could tweak our programs for that (the assignment was insanely hard, so of course no one had time to tweak).
To my surprise, I won the tournament, despite having done the bare implementation with no tweaks! I didn’t get a perfect grade on the assignment though - apparently I had miss implemented the queue for the alpha-beta search, and had completely reversed the queue ordering.
Of course, searching “in reverse” through the alpha-beta tree turned out to be the difference that won me the tournament. It was rather humiliating, but a good lesson on sheer luck’s role in academic approaches to AI.
- dmurray 4y agoIsn't searching the right way round extremely important? If you get the ordering right, a search to depth N takes time O(2^N), if you get it in reverse, O(2^2N). Perhaps if there were no time constraints, doing something slightly different was enough to beat the other competitors who cancelled each other out.
- lordofmoria 4y agoSadly the mistake was even more basic than you’re likely thinking - as I recall, min-max is necessarily breath-first, and I simply pushed onto the queue from the wrong side (think: append instead of push), so the queue was backwards, and breadth first traversed from right to left. Same time complexity, but slightly different paths reached within the same time constraints!