Feb 17, 2007

[Plan] Many things to do

I have been out of town since thursday (and still is) so I left the computer running a 1000 game tournament between TSCP, King's Out, Roce, Mediocre v0.22b and Mediocre v0.23b (really only check extension added). Getting back tomorrow and looking forward to the results.

I do not know what the statistical value of such a tournament is, but atleast we get 100 matches between each of the engines which should give us some idea of the strength differences.

My guess would be King's Out as clear first with only a few losses, and Mediocre v0.23b on fourth place but with quite some wins against TSCP and Roce. We will see tomorrow though. :)

Still some problems with basic running

Mediocre was signed up on the wbec-ridderkerk site and they had some problems running it. Apparently Mediocre did not like playing black.

I have not had any problems at all with this however.

There is also a french site (which I forget the name of) where Mediocre is listed as 'faulty', giving errors when played in the shredder and chessbase software.

To be honest I have no idea what Mediocre is doing trying to play tournaments on those sites. :) I do not consider Mediocre to be ready for any kind of 'official' tournaments yet. But the problems they had with it were not expected since I have never run into them.

From what I have gathered the shredder and chessbase software does something Mediocre does not recognize. I do have a copy of chessbase somewhere, and shredder has a 30 day trial period so I should take a look at those and see what I can do to fix it.

Outline for the next version

I have been reading some on the Talk chess forums and picked up a few simple things I want to implement (more below).

But the main goal of the next version is a complete rewrite of the evaluation, this is where the most can be done to improve Mediocre at the moment.

Mediocre runs quite fast right now, with an acceptable amount of nodes, and an equally acceptable amount of time used for each node.

This does not help however if we actively search out bad positions. When letting Mediocre play games against other engines, and especially against older versions of itself I see this happen over and over again.

The newer version searches 3-4 plies as deep and decides a line where it ends up with trippled pawns and an open king is the best position.

As the search depth gets deeper the tactical tricks are not so important anymore. If one version searches 7 plies and the other 10, the faster version of course has an edge, but it is not as noticeable as 3 vs. 6 plies. So more plies is not the solution anymore.

Anyway, here are a few things I am going to work on.
  • Dynamic time control check

    Currently we set a fixed amount of alpha-beta nodes to search before we check if the time is up or if the user told us to stop thinking. For a few versions this number has been 2000. If we set this number too high we get overruns, that is we keep searching beyond the given time by a certain amount. This is of course not good, especially if we are very low on time.

    I have had some bugs with this that I do not really understand, but the number needs to be well adjusted.

    A better solution is to keep this number dynamic, meaning it changes depending on how much time is actually used between the nodes. We could start with say 2000 nodes per time check, but if those 2000 nodes take 10 seconds to calculate we will get in trouble. Also if those 2000 nodes take 1 millisecond to calculate we will run the check for time way too often.

    So we keep track of how much time we use between the nodes and adjust the time check accordingly. This is a quite simple thing to implement, and should make Mediocre rely less on the hardware it is running on.

  • Piece tables

    A piece table simply keeps track of the pieces positions of both sides so we do not have to look for them in a big loop.

    This has been suggested to me for quite some time. In v0.22b I let the Board-class keep track of the kings' positions to eliminate the loop for finding them in the inCheck methods. I am sure this saved some time, but we should extend this to include all the pieces.

    There are three important places where this would be very useful.

    The move generation where we loop over the whole board to find a maximum of 16 pieces to generate moves for (the pieces of one side).

    The isAttacked method where we do the same loop to find the pieces of the attacking side (this is one place where we used to loop to find the king as well).

    And in the evaluation algorithm where we loop to find the pieces for evaluation.

    What I plan to do is keep a 32 slot array in the Board-class which keeps track of the piece positions of both sides. 0-15 is black pieces and 16-32 white pieces. 0-7 black pawns and 16-23 white pawns, 15 black king, 32 white king and so on.

    The array is filled at the start of the game and with every makeMove we update it for the new positions. If a piece gets captured we put -1 there to indicate the piece no longer exists.

    Now when we want to generate moves for white pieces we only need to loop 16 times, index 16-32 in the piece-array.

    This should save quite some time and is very easy to implement.

  • PickSort or similar

    Currently Mediocre has a very messy move-sorting procedure. First we call sort() which actually does not sort the moves but only assigns them a sorting value based on being a hash-move, killer-move, capture etc. Then we call bubbleSort that sorts the moves in the assigned order.

    This is a very slow way to go about it. With some redesigning we could easily avoid the sort()-method altogether, but even better we could even avoid the bubbleSort.

    Instead of sorting all the moves we could do a 'PickSort', we simply go over the moves one time and grab the move with the highest ordering value. First time around this should be the hash move, most of the time this move will cause a cutoff so we do not have to bother checking the rest of the moves, hence sorting them beforehand is a waste of time.

    If the first move does not cause a cutoff we do the same thing again and grab the move with the second highest ordering value (should be primary killer move).

    And so on. We have then eliminated unnescessary sorting and should speed up the search quite a bit.

    The only problem I can see with this is the problematic assigning of ordering values. Where should we award the values if we do not use the sort()-method? I will come up with something. :)

  • Evaluation

    This is the main subject of this version. I will do a complete rewrite of the evaluation algorithm. And there are three major areas I will concentrate on.
    • Piece tables - We need a lot better piece placement tables, involving all the pieces
    • King safety - I have looked alot at Rebel's king safety evalution and it makes a lot of sense. Hopefully I can find a way to implement this efficiently. Maybe we even get a SEE (static exchange evaluation) out of it which we can use for quiescent search
    • Pawn evaluation - This along with king safety is where Mediocre lacks the most at the moment. We need to spot passed, doubled, isolated, and backwards pawns. There is more but I think I will start with this

  • Interface problems

    As mentioned above. I need to get Mediocre working correctly on all types of software. Perhaps we need to implement a hash size function as well to cover everything, we will see

That is about it. There are a lot of things to do, but really it is only the evaluation that should challenging. The evaluation will continue to grow over time, but the things listed above is a good start.

No comments: