Friday, April 27, 2007

Chess Computer 2

I've fixed the memory leak. Turns out that it was caused by not overriding the destructor (not something needed to do in other languages I've used, that I recall). Some of my objects have their own internal objects, and they are de-allocated in the destructor, so when it wasn't called they weren't, and they quickly became numerous since it's a type of object that I create and destroy a lot when the ai is thinking (hundreds of MBs became allocated if I left the Ai thinking for a shore while...) I spent hours trying to find that leak. No warning from the compiler or anything (it warns about all sorts of things, like declaring a small variable and then not using it, but if you write the worlds longest and coolest destructor without overriding it, it won't say a peep. Boo, etc. But still, Delphi's great.) Anyway, now that's fixed, although I still have a minor memory leak yet unfound.

The ai examines about 2000-3000 positions per second. That's pretty bad, but I don't mind as I've not taken speed into account when writing the code. It will get better as I refactor the code. (My main consideration has been the structure of the code, at least on a higher level like what objects and what relations etc, but that too will be improved.) At first I got the result 4000-5000 positions per second, and even 10000, but then it got lowered. I'm not sure why, but I've changed the code back and forth without keeping track of anything. Anyway, I like things measurable and it will be fun to see what speed I can reach. And with a baseline like this, it can only get better.

Apart from being slow in general, the search-algorithm is also ineffective in another way. It searches all branches, even useless ones. I've implemented the minimax algorithm so far, and my next step is using alfabeta pruning. Code-wise the change is minimal, but search-wise the change is huge. The same number of positions will be examined given the same time, but irrelevant branches will be cut off. And without risk too (as compared with minimax, but of course both suffers from the horizon effect, but alphabeta normally sees further given the same time.)

.

6 comments:

Loomis said...

Do you plan to have your program playing online anywhere? I recently whipped up my own (weak) chess engine and have let it play on FICS a bit. After a lot of work, it's nice to see the thing move some pieces against people.

XY said...

I intend to let it play on FICS within a month or so. We could let them compete, but I'm afraid mine will lose badly despite the supposed weakness of yours. :) At least initially and for a while. Still, could be fun.

Blue Devil Knight said...

Very cool. If you ever implemented a flexibility function to help users in their opening preparation, that would be sweet.

XY said...

I don't know what a flexibility function is, but I'll look it up.

And I should add that even though I intend to have it ready for some FICSing within a month (hopefully), it will take some time before I have public version ready.

Blue Devil Knight said...

The problem is, none of the programs actually provide a flexibility function! This is largely because for the computer it is pretty much useless (it will choose the mate in 15 line, even if there is a (to a human) more flexible, simple win that takes 30 moves). I really wish some programmers would integrate such a measure to provide feedback for humans in their training.

What language are you writing this in again?

XY said...

Delphi.

 
Locations of visitors to this page