Isn'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.
Re:2022 Letter
by lordofmoria on Saturday December 31, 2022 @10:37PM
(#34203333)
Sadly 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!
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.