fun with AI's

My connect 4 AI has improved yet again. This time around I just tweaked it so that I compute the full score for each state in the BFS potion of the tree and sort each group. With this improvement, I'm running to a depth of 12 in less than 30 seconds. I've still got a bit of tuning to do (some ad-hoc testing shows that running the BFS to a depth of 3 is several times faster than a depth of 4 on the single core machine I was using)

After that's done, the next bit is to figure out how to do a sliding depth scale to leverage all the remaining time. I expect that the progress vs time plot is going to be rather interesting.

On another front, I am back in the lead; I figured out how to beat the AI while playing second!

My AI is working (mostly)

As I posted a few days ago, I'm working on a connect-4 AI as a class project. It turns out that counting the children works and the whole thing performs well (at least as fast as the single threaded version)

The solution ends up working by keeping a count of how many unpropagated children each node has. When this goes to zero, the nodes value is propagated up the tree another level. The only tricky part is building the tree in the first place. The issue here is that you can't propagate stuff while the tree is being built so it has to happen as an intermediate step before the leaf processing.

Once all that gobly-goop is done the main evaluation runs just fine. However I still haven't figured out how to do any better than evaluating the leafs in the order they fall in (fact is I haven't even coded anything yet, only puzzled over it). That works very well because, most of the time, both threads are working on nodes that share a parent so alpha-beta pruning works correctly. At 2 threads, I suspect that I'm running at almost 100% efficiency but if I stared using more threads (say more than the branching factor) I would expect that to drop a lot.

The next thing I'm planning on trying will be to run my heuristic function on all the nodes and sort each group of children as they are generated. I hope that this will better optimize the alpha beta pruning and might even give an order where I can get something closer to ideal while adjusting the depth based on time renaming.

In asking around for others solutions I was pointed at this paper that mentions something called "mandatory work first" that might mesh well with my stuff if I can figure out how to sort based on it.

Anyway, the code functions and beats me easily. On the other hand I have a few more tweaks I want to try. Fun!

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...

I just got a 25% speedup in my code!

I am working on a Connect-4 AI for an AI class. Being me I decided to go all out on the bit twiddling and whatnot to make the thing as compact and as fast as I could make it (there is a 30 seconds per move limit).

The big part turns out being how to test for a win/loss and how to score the leaves of the tree. I chose to go with bits masks for the board as it lets me do both of these with ANDs, shifts and XORs. I shift the bits so that each sequence of 4 spaces stack and then build a set of adders from ANDs and XORs. Checking the 4s bits finds wins and looses and masking with the inverse of the opponents and counting the 3s, 2s and 1s gives a heuristic for the state. The problem with this is that the direct way would end up with about 100 lines of bit ops and piles of goo for variables names. I actually started in on that tack but decided it wasn't a good idea.

What I settled on was a templated struct that handles the shift and adds and another struct to handle the next higher level of the mucking around. The main problem with that is that I end up with about 160 variables (most of which are not needed at the same time) that are locked into struct so I don't expect that the compiler will do a good job of reusing them (I also suspect that many of the methods won't get inlined as aggressively)

I was tossing around the idea of getting the code working and then editing the structs back into the main loop (inlining by hand) to address these issue and it occurred to me that if I turned the struct into templates I can do a named mixin and I don't need to alter the usage code one bit.

As an example, this code:

struct S
{
   int i;
   int I()
   {
      return i++;
   }
}

void main()
{
   S s1, s2;
   s1.i = 0;
   s2.i = 0;
   assert(s1.I == 0);
   assert(s2.I == 0);
   assert(s1.I == 1);
   assert(s2.I == 1);
}

becomes this code:

template S()
{
   int i;
   int I()
   {
      return i++;
   }
}

void main()
{
   mixin S!() s1;
   mixin S!() s2;
   s1.i = 0;
   s2.i = 0;
   assert(s1.I == 0);
   assert(s2.I == 0);
   assert(s1.I == 1);
   assert(s2.I == 1);
}

In my actual case this resulted in about a 25% speed boost.

of course this does have a few down side like I can no longer use this or any of it's aliases. I can't use the data as a struct and I can't copy it.

But all in all a 25% speedup for almost no coding is just cool!