[Kde-games-devel] AI library in the gamelibs?

[Inge Wallin]

On Saturday, January 04, 2014 12:06:01 Ian Wadham wrote:
> On 04/01/2014, at 8:29 AM, Inge Wallin wrote:
> > It supports the following features, which none of the current or previous 
board games (like kenolaba), do:
> >  - time control of the engine, not just depth of thinking
> >  - Iteratively deepening alpha-beta search algorithm with lots of
> >  optimizations - Opening book generation and use of the opening books in
> >  the game - Support for games with many different types of rule sets like
> >  loss vs tie if no move is available, simple win/lose vs graded win/loss
> >  (like chess and reversi, respectively), etc> 
> > So, what's your opinion? You could argue that an advanced AI library like
> > this would be unnecessary for the simple types of game that we have in
> > the kde games, but I have one argument against that: efficiency is not
> > wasted even if you don't make full use of it. You can also use it to save
> > batteries which is very important on tablets and phones.  And I do think
> > we should port as many of our games as possible to Plasma Active and
> > other tablet operating systems.
> > 
> > Regarding use of it, if this is interesting I will personally port both
> > KReversi and KFourinline to it but this is probably a half to one year
> > into the future. Could also make a good Summer of Code project.
> Two comments.
> 
> Firstly, I know that smarter AI is a challenge and I wish to encourage
> you, not discourage you, but I believe it is important for our games
> always to contain difficulty levels that will not turn away beginners.
> In my own case, KReversi and KFourinline are both too hard to win,
> even at novice level, so I have never become "hooked" on them.

Efficiency is not the same as strength, as I hinted in my first mail, although it 
is a necessary part of it.  The architecture of this library-to-be is that you 
can plug in new evaluation functions easily and it would be trivial to create 
a more naive evaluation function for easier levels of KReversi and KFourinline 
and also better ones for higher levels.  So to answer your question that you 
never asked, yes, this would help in making it "better" for you. :)

> Secondly, I wonder if the above approaches could provide a better
> AI player in KJumpingCube (Einstein?). ATM the algorithm is basic
> MiniMax, preceded by an algorithm to pick a set of "likely" moves.
> Kepler AI is the original algorithm and Newton AI is one I added.

Interesting. I have completely missed this game.  I cloned the repo and had a 
quick look at the source code.  And I would say that yes, it could definitely 
produce a better AI.  Even if it didn't add anything to the evaluation, it 
would still improve things by letting you search deeper by using more efficient 
search code.

> The problems with KJC, as I see it, are that there is usually a large
> number of possible moves and that each move can require time
> to play its outcome, because of the possibility of "cascading" moves
> spreading all over the board.  I have speeded up the processes
> involved quite a lot, but am wondering (vaguely) where to go next.
> Newton and Kepler are fairly easy to beat at the highest level
> (i.e. largest number of moves in the lookahead).

Larger numbers than amazons (>1000 possible moves in the beginning)? That in 
itself is not a big problem as long as you have good move ordering inside the 
search. You need to have a heuristic for what is a good move and pick those 
moves first.  Then you will often get a beta-cutoff from the alpha-beta 
algorithm and don't have to evaluate more than 1 or 2 of all the possible 
moves.  I may be blind, but I didn't see any use of alpha-beta in the KJC 
code. Did I miss it?  That thing in itself would let you search almost twice 
as deep in the same time.

The basic alpha-beta algorithm is really simple.  It's just two parameters 
extra to the recursive search function and a couple of comparisons in 
strategic places.  You can read a very basic version of it on the chess 
programming wiki. If you optimize the search function without using alpha-
beta, it's like optimizing a bubble sort algorithm.  It can be twice as fast, 
but it's still O(n^2). The next step would be to introduce a transposition 
table[2].

My code already has both of these plus numerous other optimizations. You would 
just have to plug in 3 classes that you write yourself, and which you already 
have more or less:
 - A class representing a position (configuration of pieces, who is to move, 
etc)
 - A class representing a move
 - A an evaluation function.

That's it.

	-Inge


[1] http://chessprogramming.wikispaces.com/Alpha-Beta
[2] http://chessprogramming.wikispaces.com/Transposition+Table

> All the best, Ian W.
> 
> 
> _______________________________________________
> kde-games-devel mailing list
> kde-games-devel at kde.org
> https://mail.kde.org/mailman/listinfo/kde-games-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-games-devel/attachments/20140104/02dc69d0/attachment-0001.html>