Generic Search AI

[searing]

I'm opening this issue to keep you guys updated on what's going on.

I have a rough implementation running. It appears to work, in the sense that it runs, gives a reasonable move, and executes in the time frame given (I'm using 10 seconds for now).

Here's some pretty output!

Pending moves (current level): 720
Pending moves (current level): 375
Confirmed moves (current level): 40
Levels traversed: 2
Confirmed moves (current level): 90
Levels traversed: 2
Pending moves (current level): 503
Confirmed moves (current level): 110
Levels traversed: 2
Pending moves (current level): 507
Confirmed moves (current level): 70
Levels traversed: 2
Winning move: (0:3):(6:3):(6:8) [31]

So this is basically a dump of all the threads' statuses when they got halted. "Levels traversed" means total levels traversed, so '2' means that it has completed the calculation for all of our moves, all of our opponents counter-moves, and some of our counter-counter-moves. "Confirmed moves" are moves that are confirmed as "good enough" to be included in the next pass. "Pending moves" are moves that have not yet been confirmed (and may be thrown away).

The number in brackets next to the winning move is its score. I'm using a very primitive evaluator for testing: take the sum of our reachable nodes in contested partitions and our total nodes in owned partitions, and subtract likewise for the opponent.

I'm testing with a branching width of 10, and 10 seconds for a run. I'm going to be bumping the number of seconds up significantly so I can get a better idea of what's going on within the search.

Edit: More data, this time from 60 seconds. Clearly, we won't spend this long crunching numbers, but the fact that it even finished level 3 is good. After some optimizations, we might be able to bring that into a reasonable time frame.

Pending moves (current level): 767
Pending moves (current level): 524
Pending moves (current level): 1040
Confirmed moves (current level): 300
Confirmed moves (current level): 480
Levels traversed: 3
Levels traversed: 3
Pending moves (current level): 860
Confirmed moves (current level): 690
Levels traversed: 3
Confirmed moves (current level): 580
Levels traversed: 2
Winning move: (0:3):(6:3):(6:8) [31]

[minustehbare]

This sounds awesome. Are you using the Heuristic class with generic constants? (i.e. 1 for each coefficient?) Post up results from the deeper/longer searches as you get them.

[searing]

No, just a primitive evaluator. I'll test yours later, probably early tomorrow morning. I have a profiling test for evaluators now - I see how long it takes to grade 100000 partition sets. I'll add a test for you soon.

I modified the search parameters a bit. Taking the 5 best first moves and the 2 best moves for each level after that, I got this:

Pending moves (current level): 1164
Pending moves (current level): 401
Confirmed moves (current level): 26
Levels traversed: 3
Pending moves (current level): 262
Confirmed moves (current level): 30
Confirmed moves (current level): 14
Levels traversed: 2
Levels traversed: 3
Pending moves (current level): 305
Confirmed moves (current level): 10
Levels traversed: 4
Winning move: (0:6):(6:6):(6:1) [31]

That was from 10 seconds! We'll have to run some tests once we start connecting to the server to see if this is better or worse than having shallower but broader searches.

Edit: And from the same parameters for 60 seconds:

Pending moves (current level): 790
Pending moves (current level): 535
Pending moves (current level): 604
Pending moves (current level): 443
Confirmed moves (current level): 76
Levels traversed: 5
Confirmed moves (current level): 76
Confirmed moves (current level): 120
Levels traversed: 6
Levels traversed: 4
Confirmed moves (current level): 140
Levels traversed: 5

There's still a lingering null pointer exception in here that I have to squash.

[searing]

I used your Heuristic class for this. (at 10 seconds, 5/2 branching width)

Pending moves (current level): 1096
Pending moves (current level): 1831
Pending moves (current level): 261
Pending moves (current level): 579
Confirmed moves (current level): 22
Levels traversed: 3
Confirmed moves (current level): 30
Confirmed moves (current level): 12
Levels traversed: 2
Levels traversed: 3
Confirmed moves (current level): 4
Levels traversed: 4
Winning move: (0:6):(6:6):(6:1) [34]

[searing]

Okay, last spam post for the night. I've implemented thread syncing, so none of the threads can charge ahead of the others. We may or may not want this. To show the effect, here's a screenshot of my CPU usage during a 60-second run. As you can see, it's not fully utilizing the CPU because some threads are waiting for others that have inherently "harder" workloads.