[New Version] v0.231b - Bug fix and depth/new replacement scheme

Changes:

• A bug in the new 'game over' check for winboard that made the engine crash was fixed
• The transposition tables now use depth/new replacement scheme

Note: This 'hotfix' was nescessary since I had forgotten a simple out of bounds check in the winboard version. To atleast add something more in this 'new' version I added depth/new replacement scheme for the transposition tables, I have not had any problems with out of memory errors due to this (and there should not be any if I counted right), but please send me a note if you run into any. The next version will include a possibility to change the size of the transposition tables from the interface.

mediocre_v0.231b

[New Version] v0.23b - Evaluation

Changes:

• Completely new evaluation, now accounts for king attacks, pawn evaluation and more
• Check extension added
• Draw repetition is now accounted for in the search tree as well
• A bug concerning contempt factor was fixed
• Piece lists added, no more 120 loops
• Now gives correct mate count (and not just a high number) for both uci and winboard, but evaluations from the transposition tables gives the count when the mate was found (this is on the todo-list)
• The broken 'force' mode in winboard should now be fixed
• Winboard protocol now sends the score when the game is finished (still needs some work)

Note: The evaluation is an ongoing process and not a one time implementation. There are still a lot of adjustments to be done.

I decided to include jlaunch in this release since people have been complaining about Mediocre not working in the Shredder and Chessbase interfaces. I might not include this in the future but simply link to it.

mediocre_v0.23b

[Other] Adjustments to evaluation

I rewrote the greater part of the evaluation for some better nodes per second performance.

For example I only calculate king attacks if the queens are still on the board. There are different opinions about this. I think most attacks without queen are pretty harmless, and the occassional dangerous position without queens is either handled by the search or had a queen in the attack up to a point so we already should have 'seen it coming'.

Anyway this rewrite regained the end game playing strength. I think the king attack code occassionally interfered with the general play (not only with worse nodes per second), especially in the endgame.

Here is a test tournament versus the old version of Mediocre. Mediocre v0.23b has piece lists, new evaluation and check extension.

1: Mediocre v0.23b uci 64,5/100 
2: Mediocre v0.22b uci 35,5/100

So Mediocre has gotten a bit stronger.

There are still a few things to work out (connected passed pawns are handled wrong at the moment, and backwards pawns are not handled at all), and also some adjustments need to be made so we can avoid what happened in the following game:


On move 30 Mediocre v0.23b played 30. ... Re7 and evaluates the position to slightly worse. It sees the following moves where it loses the bishop, but considers the passed h-pawn to be enough compensation.

After a few weird moves it completely misses the 35. f5.

These kinds of errors are quite common for some reason, but usually the new evaluation is put to good use like here:


Both king safety, pawn evaluation and rook positioning helped winning this game.

I also need to take another look at the development in the openings, the new version is quite fond of leaving pieces undeveloped even though it gets a penalty for leaving them on the first rank. Perhaps some special code is needed here.

[Other] Playing around with the evaluation

I have implemented king safety, pawn evaluation, some trapped piece detection and a bunch more piece positioning evaluations. They work without bugs, but are in need of some serious tweaking.

In its current state the new evaluation takes the average calculated nodes per second from about 150.000 to 75.000. This is a bit too much, but I think I can cut it down some with better written code. Also the piece tables I have been talking about should increase the overall speed some.

Here are a couple games where the new evaluation works well.










Keep in mind that the new version searches about half as many nodes, so logically any tactical combinations should be due to the evaluation (and not out-calculating). Of course it could be luck as well.

I especially like the last game where the new version evaluated the position after 12. Bxh7 to +3.0, seeing the bishop getting trapped but figuring it would be ahead after the exchanges. This might not be sound at all, but it does indeed have a strong attack.

Unfortunately not all games work out this well, when v0.22b 'accidently' manages to castle and avoid attacks it can usually work out the position to its advantage.

This is probably both due to the slightly deeper depth it searches to, but mainly I think some parts of the evaluation actually hurts v0.23b. It seems to play a bit weird in endings and can get very careless in some positions.

So as I said there is still a lot of tweaking and optimizations to be done, but once we get there this should really improve Mediocre.

I have used ideas from TSCP (pawn eval) and Toga (king safety and trapped pieces) and once I feel the evaluation works as it should I will write a guide or two.

[Other] Running Mediocre in Shredder and Chessbase

The Shredder Classic and Chessbase interfaces do not like the .bat-file needed to run Mediocre, like we do when using Arena for example.

Shredder requires an .exe-file to recognize the engine as UCI (it recognize it as Winboard with the .bat-file but can not play games due to weird behavior) and Chessbase requires an .exe-file to even try install Mediocre.

The solution is to use a small program called jlaunch by Manfred Rosenboom.

For Mediocre you simply place the program in the main directory (where the .bat-files are located) and create a file called jlaunch.properties and place it in the same directory.

The properties file should look like this:

mainClassName=Mediocre
classPath=bin
app.arg0=u

You need to have paths set to the Java bin-directory on your system for this to work (try typing 'java' in a console window, if you do not get an error you have it set).

Now when installing Mediocre in Shredder Classic or Chessbase you simply use the jlaunch.exe as engine file and it should work.

This works in Arena as well.

Now I just need to track down the problems wbec-ridderkerk had with running Mediocre. That has nothing to do with the above solution since they run it as a winboard engine. I suspect it has something to do with a preset opening book.

[Other] A third of the results

Of course the tournament did not finish as it should, only a third of the games were played before a power outage stopped it. But anyway, all the engines played 35 matches against each other.

The time control was 3 minutes for each side and the results were:

1: Kingsout            120,5/140
2: Tscp181             84,5/140
3: Mediocre v0.23b dev 54,0/140
4: Roce350             47,5/140 
5: Mediocre v0.22b     43,5/140

The only real conclusions we can draw from this is King's Out clearly being the strongest and Tscp second, the 3-5 places are too close to call.

Roce takes way too many unnescessary draws so it probably places above Mediocre v0.23b if you take those out.

The 'individual' result between the two versions of Mediocre was this:

3: Mediocre v0.23b dev 20,5/35 101101111101===0=1001001=10101=011=
5: Mediocre v0.22b     14,5/35 010010000010===1=0110110=01010=100=

Quite close but the check extension seems to give a slight edge.

Many many more games needs to be played for any real conclusions, this is mainly for fun. :)

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

[Bug] Wrong node count

In some complicated positions Mediocre seemed to drop its node count way below the average. I never really figured out why since the type of position should have nothing to do with the number of nodes visited per second. It could affect the number of plies, but that is another matter.

One position I had this problem with was this one:

2rq1rk1/p5bp/bp2pnp1/n1ppNp2/2PP4/PP1BPN2/1B3PPP/2RQ1RK1 b - - 3 14

It is a fairly complicated position with many captures going on. Mediocre searches it like this:

Ply Eval  Time  Nodes Line
1    -15   140     36 Bb7 
2    -25   219    179 Bb7 Qc2 
3    -15   875    678 Bb7 Qc2 Nc6 
4    -15  1156   2040 Bb7 Qc2 Nc6 Rb1 
5    -10  4906   9434 Bb7 Qc2 Nc6 cxd5 exd5 
6    -15 11359  29397 Bb7 Qc2 Nc6 Nxc6 Bxc6 Ne5 
7    -10 53578 152535 Bb7 cxd5 Qxd5 b4 Qa2 Qe2 Nb3

As you can see it takes quite some time to get to 7 plies depth. But the node count is only 152535. That kind of node count takes about a second in most positions, and not 53 seconds like here.

I could never really figure out why this was. Of course it has something to do with quiescent search since that is the only place the engine could spend that kind of time without getting farther in the search.

And then today I was looking through the source code of some other engines and found a missing line.

Mediocre only increases its node count at the beginning of every alphaBeta()-call. But even though quiescent search has a limited number of moves to choose from, every position it finds is also a node, so of course the number of nodes should be increased there as well.

So I made quiescent search nodes add to the total nodes searched as well and the result was this in the same position.

Ply Eval  Time   Nodes Line
1    -15   140    7484 Bb7 
2    -25   218   19992 Bb7 Qc2 
3    -15   687   97129 Bb7 Qc2 Nc6 
4    -15   953  140802 Bb7 Qc2 Nc6 Rb1 
5    -10  4234  674731 Bb7 Qc2 Nc6 cxd5 exd5 
6    -15 10390 1675138 Bb7 Qc2 Nc6 Nxc6 Bxc6 Ne5 
7    -10 50812 8200247 Bb7 cxd5 Qxd5 b4 Qa2 Qe2 Nb3

Exactly the same evaluation and line, and time used is about the same (this differs some from search to search of course). But the node count is fifty times as high.

Conclusion

This does not affect the search speed, or evaluation, or anything else. But it does give us a much better view of how much time Mediocre uses to go through a certain amount of nodes.

The pruning of Mediocre was appearing to be quite awesome, and the nodes per second terrible. With this change we can see that Mediocre is not so bad when it comes to pruning (but not -that- good :), and it is also not as slow calculating nodes as it would have appeared.

As said this is only a matter of presentation and has nothing to do with the search itself. However comparisons to other programs will become much easier now.

[Other] A little tournament

I ran a tournament between all the versions since 0.12b (since that is when time management was implemented).

   Engine              Score   v.22 v.23 v.21  v.2 v.12
1: Mediocre v0.22b     13,5/16 ···· 1101 11== 1=11 1111
2: Mediocre v0.23b dev 11,0/16 0010 ···· 01== 1111 1111
3: Mediocre v0.21b     7,0/16  00== 10== ···· 1110 1000
4: Mediocre v0.2b      5,5/16  0=00 0000 0001 ···· 1111
5: Mediocre v0.12b     3,0/16  0000 0000 0111 0000 ····

The v0.23b dev is the development version, it has some adaptive null move pruning and check extensions but it is not working like it should yet.

Most of the draws were due to unnescessary repetitions.

One interesting aspect is the amount of repeated games. Even in this few games there were a few repeated games, i.e. games with the exact same moves from start to end.

Medioce has no random factor and I do not intend to add one, it plays what it considers best in every position. The way to get more variation in the games is improving the opening book.

I might add the posibility to use a common opening book through Arena (or other interfaces that support it), however I like Mediocre having its own book as well. Perhaps it is time to start building a bigger one.

[Other] Letting Mediocre loose on the ICC

I decided to try Mediocre against some human opponents so I dug up my computer account on the Internet Chess Club and let it have a go.

The name of the account is Independence, so if you have a user at ICC you can give Mediocre a try there, I will leave it up for a while.

The result after 12 hours was this:

       rating win loss draw total best
Bullet   2051 146   19   22   187 2085

Time control for pretty much all games was 2 minutes without increment. Among the beaten opponents were two FMs (fide master) and a WIM (woman international master).

Mediocre was pretty stable during the whole time, no crashes and a total of 2 illegal moves.

Both illegal moves came after a draw by repetition. Also draw by repetition is recognized only if Mediocre initiates the repetition. I.e. it does the first 'repeating' move.

Basically the repetition detection needs a checkup, but for everything else Mediocre is looking just fine. :)