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

Hi Ian,

I'm replying to this part in private now since I think there is a good 
solution to have for the price of a very small development time.

I have looked at the AI code in more detail now and I am quite convinced that 
with just one day's work or so you can have a very much stronger AI. Mainly, 
I'd structure the search a bit better and use alpha-beta with iterative 
deepening. I'd leave out hashing and transposition table for later and also 
more elaborate optimizations.

To comment on your statement above, I don't think that 36 possible moves (for 
a game with a side of 6) is very large. Even 100, when you have a side of 10, 
is not that much.

 If you like, I can write a new AI for you, but I see that you have used 
threading to make the UI responsive even while it's thinking.  For this work, 
I'd ignore this and you would have to plug it into the threading yourself, 
which should be pretty easy. Is this interesting to you?

If it is, I think we can get one step further by improving the evaluation 
function.  As I understood it, you value the position for one side as:

 Val(c) = Ncubes(c)^2 + Ndots(c)
 
where
  Val(c) is the value of the position for color c 
  Ncubes(c) is the number of owned cubes for color c
  Ndots(c) is the sum of the dots on the owned cubes for color c

And the total value of the position is:

  ValPos(p) = Val(one) - Val(two)

Right?  That's probably a good start since I wasn't able to win even against 
the beginner level.  But I think we can do better. How do you think when you 
yourself is playing the game? How do you select your moves? How do you know if 
you're ahead? If we can answer those questions, we will have the key to a 
better evaluation function.

	-Inge


> 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/dda342f2/attachment.html>