[Kde-games-devel] Introducing the KDE AI library

[Inge Wallin]

Hi people,

Some of you might not know this, but when I started to program in KDE around 
2005 I came from a game AI background. I was even in the Computer Olympiad a 
couple of times, representing GNU Go (and winning one class :) )

Anyway, I have noticed that one of the weak points of many of the KDE board 
games is the AI. And this is not strange since it's an area where you need 
lots of specialized knowledge to actually create something good.

I had a lot of code lying around so I decided that I'd try to port my old C 
sources to modern C++ and make it easily usable in other programs. This has 
been a background task for over a year now and today I got an example program 
playing the game of Connect 4 (a.k.a. Four in Line) working.

So I thought the time would be ready to announce the existance of the project 
and let other people take a look at it.

To use it, you need to provide a few classes:
 - Position: represents the state of the game
 - Move: represents the transition between two states of the Position
 - MoveGenerator: generates moves from a Position
 - Evaluator: evaluates a Position
and a few more. This is documented inside the library.

Ok, that was the good news.  However, I'd also like to say that this is not 
yet ready for prime time. The documentation is not complete yet, and there are 
probably bugs inside it. But it's good enough to take a first look at, and it 
actually does work for the example program.

The repository is kde:libkdeai or 
http://quickgit.kde.org/?p=scratch%2Fingwa%2Flibkdeai.git if you prefer to 
look at it on the web.

At this point it implements an iteratively deepening enhanced negamax alpha-
beta algorithm with some optimizations: scout with zero-window search, killer 
heuristic, null-move heuristic. If this doesn't tell you anything, then you're 
the perfect user of this library because you don't have to care. Just plug it 
in and you have a professional level game searcher in your program.

Still lacking is other types of search (single agent search like A*, proof 
number search, etc), quiscence search, opening book and some other things that 
are in the roadmap. I have a lot of code still to port, so there is no lack of 
possible enhancements in the future.

Feedback is very welcome even if you don't use it in your own program!

	-Inge