Fun from the code lines.

My current school project is an AI for playing Connect-4 using minimax. The first bit was fun, lost of low level bit twiddling, building bit adders, monster functions that do recursion without recursion, finding bazaar optimizations... all the kinds of stuff crazy people like me enjoy.

After I got it to the point it could beat me, the real fun started!

So far I have, at least twice, found places where I had the AI’s playing the wrong side ("Here, let me help you win!") and then spent the better part of two days trying to figure out where the typo in a fundamentally broken algorithm was.

The thing was that I was looking to speed it up by going multi threaded. The way I was planning on doing this was

1. Run the first few levels of the min-max tree in a breadth first evaluation


2. Sort the leafs based on how good they look


3. Have several threads do the normal depth first bit on each leaf


4. Stuff the data back up the tree.

The theory here was that I could start running deep and watch the clock to known when and how much I need to back off the depth to use up all my time. However I managed to step on several severe problems with it.

First that form can’t do alpha beta pruning at all, so I drop a lot of performance right there. After being annoyed at that for a minute or two, I dug in to update the min-max tree on the fly after each leaf is evaluated. That shouldn’t be to hard, each time I get a value check to see if it is less/grater-than its parent and if so update and repeat.

The better part of two days later I was frustrated as all get-up and then noticed that this doesn’t work (I told you it was a fundamentally broken algorithm) Cases like this provide a counterexample:

First the 10 goes in, and the left min node and the max node go to 10. Then the 5 goes in and the left min node goes to 5 but the max node stays at 10. Oops...

Anyway, I think by counting children and a bit of fancy footwork I can solve that problem, but the result of that is the alpha beta pruning is going to be really funky. I’ll have to play around how things get sorted and whatnot to see what works.

Right now I’ve got the leaf evaluation and mix-max push working correctly but things go wacky when a win or loss shows up above the leafs. Fun, fun, fun. What I really need is another set of eyes to go over my code. Unfortunately given that it’s homework...