Dec 31, 2007

[Other] Mediocre in CCT 10

I have entered Mediocre in the CCT 10 tournament which starts January 26.

"Hopefully" I will have had some time to work on Mediocre until then. Ponder, some endgame knowledge and a recap of the evaluation is on top of the list.

Dec 25, 2007

[Other] Chesswar XI Over

Mediocre held its position somewhere in the low middle of the crosstable during the whole tournament. The final score of 32/71 gave 43rd place. I had hoped for a 50% score but this result is quite decent considering the competition. The notable games were the wins against Baron and Alfil and draw against Hamsters.

It was an exciting and interesting tournament, thanks Olivier.

Dec 3, 2007

[Other] All is well in WBEC

Mediocre has qualified for the next phase in WBEC Ridderkerk with a score of 19/22, there are still 3 more rounds to go but Mediocre will be in the top 6.

Qualifying for division 4 will be harder though, with engines like Neurosis, BBChess, Alf, Brutus and Lime all of which Mediocre very well could lose against. But as I said before with a bit of luck it should be possible.

Nov 16, 2007

[Other] OpenWar 3rd edition and WBEC Ridderkerk

It has been a while and I still have not had the time to work on Mediocre. Quite sad really, but I am following the tournaments Mediocre is participating in.

As you might have noticed WBEC Ridderkerk edition 15 has started and a couple of days ago the B group in division 5 where Mediocre plays started. Two rounds have been played so far and Mediocre has won both against Atak 5.03 and Rogue 1.1. I am hoping the for the top 6, and maybe later, with a bit of luck, a promotion to division 4.

OpenWar 3rd edition is still playing and is currently at round 41 of 71. Mediocre has a mediocre (!) 16/41 points. But the win against Baron 2.22 almost makes up for the poor results. :) Here it is:


Looked dangerous for a bit, but Baron found no way through to the white king.

Well that is it for now, hopefully I will get around to a new version of Mediocre shortly, I will keep you posted.

Oct 2, 2007

[Other] Poor/decent performance

Mediocre had 3.5 points after 7 rounds in ChessWar XI but after 3 straight losses and only a win in the last game Mediocre finished at 50th place in the in the D division. I had hoped for slightly more but I guess this is about what was to be expected.

OpenWar 3rd edition
(also held by Olivier Deville) has started and after 8 rounds Mediocre has a decent 4.5 points considering it has already played Erendal and Frenzee against which it should not really have a chance. The mix of engines here is quite large, ranging from pretty poor to very good so there are some quite interesting matchups. Somewhere in the middle is what I am hoping for here.

Sep 14, 2007

[Other] C and Sagan

I have never thought too high about programming in C, however I often find myself blaming Mediocre for being slow due to being programmed in Java.

Anyone programming in C will tell you that it is lightyears faster than Java. And anyone programming in Java will tell you that the difference is negligible.

I tend to end up somewhere in the middle. Not being a superstar programmer I think that whatever speed advantage I might potentially get with C will be lost in sloppy coding.

However, just to see if there really is a difference I have started sketching on a C chess engine I call Sagan.

I am mainly doing this to not have any excuses for the engine playing badly. :) I hate the "well it's not strong, but you can only expect that from Java".

This is just in the planning stages for now. Studying at 150% speed does not give much room for anything but planning. :)

Sep 10, 2007

[Other] Section D of ChessWar XI

Mediocre is doing better than I expected in section D of Oliver Deville's ChessWarXI. 2.5/4 so far. I am guessing 5 points should be enough to stay in the division so we are halfway there. :)

As for updates and Jonatan vs. Mediocre match I will have to postpone them yet a little while. I am currently taking three courses at the same time and have very little time for just about anything. Hopefully it will calm down in a while... hopefully. :)

Aug 23, 2007

[Other] Draw in last round

Mediocre managed to get a draw in the last round of ChessWar XI against Warrior. Mediocre fumbled away an outside pawn and the king safety looked fragile, but in the end Warrior's king got open and a draw by repetition was unavoidable.

This should be enough to finish in the top 20, if I counted right, and secure a promotion to section D.

That section will be a lot tougher and I can really only hope for a decent placement somewhere in the middle.

Aug 22, 2007

[Other] Last round of ChessWar XI

Last round of group E in Oliver Deville's ChessWar XI. Before the round Mediocre is on 13th place with 6.5/10 after a nice win over Joker in round 10 (game below).

With a bad S-B score it will take at least a draw in the last round to make it in the top 20 and advance to the D group. Last opponent is Warrior and with a bit of luck I think Mediocre can pull it off.

In the game against Joker, Mediocre got at nice space advantage which it patiently used to win. It looked like it got a bit too close in the middle game, but I do not think there ever was a risk of losing the advantage.


Aug 17, 2007

[Other] Status update

Mediocre is doing fairly well in the E section of Oliver Deville's ChessWar XI. I had hoped for a little bit more but I guess I should be satisfied with the results so far. 4.5/8 points after round 8.

Leo Dijskman's Edition 15 of WBEC Ridderkerk has been postponed again, this time to 1 October. It suites me quite well since this is really the tournament I am aiming to do well in and I simply have not had the time to make the changes I want to get Mediocre ready.

The Jonatan vs. Mediocre match is about to take place shortly. Though I have some exams to take care of before that. I want to feel ready before starting to play since I am expecting the match to take quite some time over at least two weeks. Mid september is probably a good assumption of when I get the time.

Updates of Mediocre itself is also upcoming, I have quite a few things I want to do and I hope to be able to spend some time on it now that summer is coming to an end.

Jul 26, 2007

[Other] New Jim Ablett compile of Mediocre 0.332

Jim Ablett has compiled Mediocre 0.332 using Excelsior Jet and the results are fantastic. I almost want to call this a new version. My test results shows almost a doubling of the nps.

Many thanks to Jim Ablett. Try it out! (for Windows only)

mediocre_0332_win32jet.zip

[Other] ChessWar XI Group F Finished

Mediocre placed 5th in Group F in Oliver Deville's ChessWar XI and will play next in Group E. Fairly easy group with no real surprises.

Group E is a lot harder, but it should not be impossible for Mediocre to place in the top 20 to qualify for group D. At least with some luck.

These are the 20 qualified engines from Group F:
1 ERENDAL 1.2          8.5
2 JOKER 1.1.08 8
3 HECTOR FOR CHESS 8
4 ROTOR 0.2 8
5 MEDIOCRE 0.332 7.5
6 FLUX 2.1 7
7 ADAM 3.1 7
8 MRCHESS 2.1 7
9 BIBICHESS 0.5 6.5
10 TIMEA 4a12 6.5
11 WARRIOR 1.0.3 6.5
12 ALF 1.08 6.5
13 CLARABIT 0.25d_x64 6.5
14 FEUERSTEIN 0.4.5.1 6.5
15 PLYWOOD 1.7.3 6.5
16 CELES 0.77c 6.5
17 DIRTY 070511 6
18 AX 0.8 6
19 COUNTER 0.3 6
20 GULLYDECKEL 2.16pl2 6

Jul 22, 2007

[Other] 2007 WCRCC Recap and results

Amazing result by Mediocre, I am extremely happy with it. More than 50% and a nice placement, 'tied' with crafty for example.

Of course the swiss system does not show anything near the truth since Mediocre lost the first few games and got to start from the bottom, working its way through weaker engines.

But all in all it is a very good result. Considering my weak hardware, no ponder etc.

Very nice and educational tournament. I got quite a few ideas what to work on now.

Impossible Rybka won of course. However it was not a clear as some might have thought, a loss against Hiarcs made it interesting. Hiarcs lost the last game which really was a draw, but failed to claim the 50-moves rule. Would not have made a difference in the standings though.

Vicki got a nice 1.5 points, impressive for such a new engine in this field. Jaco had hoped for 0.5 points so I guess he is happy. :)

 1 Rybka           13.0
2 Hiarcs8x 12.0
3 IkarusX 10.0
4 Erdo 10.0
5 DIEP 9.5
6 TerraPi 8.5
7 Frenzee 8.0
8 Ktulu 8.0
9 Rascal 8.0
10 thebaron 8.0
11 ArasanX 8.0
12 DirtyX 8.0
13 QuarkX 7.5
14 crafty 7.5
15 Weid 7.5
16 BertaX 7.5
17 Independence 7.5 (Mediocre)
18 PetirX 7.0
19 Symbolic 7.0
20 NowX 7.0
21 HfC 7.0
22 DeltomateX 7.0
23 LearningLemming 6.5
24 danasah 6.5
25 Tinker 6.5
26 Horizon-x 6.5
27 DeuteriumChess 6.5
28 Neurosis 6.5
29 parrotC 6.5
30 JokerX 6.0
31 Telepath 6.0
32 BirdEng 6.0
33 microMaX 6.0
34 HomerX 5.5
35 Buzz 5.5
36 Clarabit 5.0
37 Timea 5.0
38 Matilde 2.5
39 roce 2.5
40 Vicki 1.5
41 NoonianChess 0.0

[Other] Game 14 Mediocre - Horizon 1-0

Oh my goodness! This was so exciting. :)

Mediocre went for doubling Horizon's center pawns which turned out to be a big mistake. I am not sure if I have any code for awarding doubled pawns in the center, I have to look into that.

Of course Horizon got a massive advantage in the center and open files for the rooks, and it did not take long before Mediocre's king was in trouble.

Around move 29 Mediocre missed the obvious attack which cost the queen vs. a rook, and I thought the game was over for sure. But just a few moves later Horizon slipped up and let a passer run away followed up by a tactical shot that evened out the game again.

It still looked bleak however. Horizon up a pawn with a dangerous passer. But a couple of bad moves and Mediocre was ahead. Then the trade of queens looked suspicious but I guess Mediocre had it figured out.

Very very exciting game, with a lot of luck for Mediocre.


[Other] Game 13 Neurosis - Mediocre 0-1

Mediocre got a knight stuck on the edge of the board on the queenside in the opening. Did not hurt too much and Neurosis passed pawn got weak. Nice end game by Mediocre and a comfortable win.


[Other] Game 12 Mediocre - Joker 0.5-0.5

Joker held on to the queen's gambit pawn and got dangerous looking passed pawns on the queen side. I do have quite a bit of code to detect the danger of passed pawns, but it seems it fails from time to time.

However, Joker's king got quite open and with Mediocre's queen running around behind its defences it looked dangerous. I do not think there was any mating chances since there were just too few pieces in the attack, perhaps with a few kingside pawn pushes something could have happened.

The repetition draw seemed quite logical. There were going to be material gains for Mediocre one way or another, but nothing enough to give a winning edge.


[Other] Game 11 Berta - Mediocre 1-0

Mediocre got on the defensive fast in this game and had no chance to hold the position. Not sure what went wrong really. Good game by Berta.


[Other] Game 10 Timea - Mediocre 0-1

The game was forfeited by Timea since it did not start moving. Too bad since Mediocre should have a good chance at a legitimate win against Timea.

[Other] Game 9 Mediocre - Clarabit 1-0

Clarabit used book moves until move 16 which lead to a very dynamic position. Perhaps short castle looked a bit better.

A weak plan from Clarabit in the late middle game lead to what looked like a won ending, however BirdEng pointed out that tablebases said black had a draw on move 41 with Kd6. Neither Mediocre nor Clarabit uses tablebases, a bit lucky perhaps. :)


[Other] Sunday's games

Round 9 starts at 15pm CET tomorrow (today). I am hoping for a game against Vicki, should be interesting.

[Others] Game 8 Symbolic - Mediocre 1-0

Nothing too bad in this game. Mediocre held up well but was just not good enough in the end game. 36. ... Rc8 looks bad however, I have to analyze that move and see what Mediocre was really thinking. After that mistake there was not much that could have been done.

Decent game with one bad move that lost it.


[Other] Game 7 Mediocre - MicroMax 1-0

Mediocre played a very aggressive game where MicroMax never really stood a chance. MicroMax neglected development and payed the price. Considering the old version of MicroMax was one of the opponents I tested Mediocre against in the early stages of development I feel quite happy about the progress Mediocre has done.

MicroMax might only have 2000 characters of code, but atleast Mediocre can beat those characters without problem now. :)

(chesspublisher has problem with the 14. bxc8=Q+ again, just ignore the lingering queen)


[Other] Game 6 ParrotC - Mediocre 0-1

Nice game by Mediocre. Calm opening with a decent handling of the caro-kann for once. I guess the win was due to some easy tactical shot, and the king safety was more due to luck than good strategy. But not too bad overall.


Jul 21, 2007

[Other] Game 5 Mediocre - HfC 0-1

Erm... that was sad. Pawn up the whole game, then failed to convert by just moving back and forth. And finally a very weird end game bug I have not seen before.

Well at least a bug detected that should not be too hard to fix. Something positive out of it. :)

(there seems to be a bug with the chesspublisher, it does not remove the rook after 23. ... exd1=Q+, just ignore it :)


[Other] Game 4 Petir - Mediocre 1-0

Very bad game by Mediocre. A complete failure in the opening, underestimated passed pawns and general bad play.

Petir is a much stronger engine than Mediocre, but I had hoped for a bit better play. 16. ... b6 is about as bad as it can get when it comes to greediness and failing to understand the threats of the opponent.

Yuck. :)

One thing I could learn from this is perhaps try to work a bit with the development section. 3. ... c5 looks very fishy and should be easily avoided with some code discouraging moving the same piece (pawn) multiple times before the other pieces are out.


[Other] Game 3 Mediocre - Quark 0-1

Interesting game. Mediocre failed to castle and tried to attack. In the end the own king safety was too much to handle. I might have to do something about that. I want the evaluation of king safety to encourage castling instead of hard coding it (like for example Crafty does, i.e. penalizing loss of castling rights), but perhaps it has to be done.

Quark kibitzed its pondering moves and got it right mostly. Mediocre does not have pondering yet and of course it is a major flaw. It is on my todo-list. Also Mediocre does not move instantly when it only has one legal move. Against opponents that does not ponder this does not matter, however it is a severe weakness against those who does, since it basically allows them a free instant move.

Well, an exciting and educational game. Off to the next round.


[Other] Game 2 Bird - Mediocre 0-1

A bit more normal opening this time with quite some strategic play. Mediocre seems to handle these games quite well.

Mediocre probably got a bit too overenthusiastic on the kingside with a few pawn pushes but Bird could not pounce on it. And in the end it actually won the game.


[Other] Game 1 Mediocre - Frenzee 0-1

Mediocre opted for the King's Gambit and quickly got in trouble. I blame it on the new opening book. :) Trying to walk the king over to the queenside had little hopes of succeeding and Mediocre is not smart enough to go on an all out attack on the king side.

Better luck in the next game.

(Mediocre is playing under the handle "Independence")


[Other] Ready to roll

There was some trouble with the .ini file, that is why the book was not being used. I have no idea if this is a general problem or if it only occurs when using Winboard to play on ICS servers. Anyway I disabled the feature so the opening book can be used. I also switched to a larger book, compiled from a number of pgn-files. I have not tested it that much but hopefully it should help a bit.

The crashing upon game completion was of course the all existent memory overflow problem with Java, I had simply forgotten the -Xmx1024M flag in the Winboard batch file.

And finally I added kibitzes at the last ply of the search, and a note if the move is a book move or not.

So one hour to go and I am ready to see Mediocre getting lucky! :)

[Other] WCRCC 2007 Last minute fixes

So it is now two hours before the 2007 World Computer Rapid Chess Championships starts and Mediocre crashes upon game completion, does not kibitz its search and can not find the opening book.

Looking good. :)

Hopefully I can panic together a few fixes.

Jul 2, 2007

Chesswar XI

Mediocre is playing in Oliver Deville's Chesswar XI in section F. Looks to be a fairly easy group, but you never know. :) Will be fun to see how Mediocre does in games with a bit longer time control.

Jun 27, 2007

[Other] Mediocre on CCRL

Mediocre is currently fighting for a place in Division 5 of the 4th Amateur Championship on CCRL.

Right now Mediocre, Flux 2.0 and Joker are in the top. Quite exciting. :)

You can follow it more close on the CCRL Discussion Board.

Jun 20, 2007

[Plan] Something to work on

So it is time to start looking at some future changes for Mediocre again. Since I have taken a break for the last few weeks it is hard to just jump right back into it again without any clear tasks to work on.

Here are some things I will be looking at:
  • End game - I recently played a 300 game 1+1 minute match against an old version of Rybka and the result was 300-0 to Rybka. :) However I noticed that Mediocre surprisingly often came out of the middle game with an even or slightly worse score, and rarely (very rarely :) even slightly better. Only to be annihilated in the end game.

    To be honest I have worked extremely little with the end game in Mediocre and I think it is time I look into that. Some simple end game knowledge should make a big difference. And it is probably worth looking into some more separation of the evaluation to make better calls in the end game.

    Perhaps the next match could end 299.5/0.5 instead... :)

  • Transposition tables - When I wrote the transposition tables class in January I basically only tried to make it work. I am sure there are tons of things to improve in there and I would not be surprised if there is a bug or two as well.

    Since the class itself is quite small a complete rewrite is probably in order, and also cleaning up the repetition detection while I am messing around in there should be worth it.

  • Check history - As it is now the search checks for checks in three or so places. While this might not be that much of a slowdown since the check detection is quite fast it could obviously be better. I have made a few attempts at making the board remember if the position is check or not, and even had it in a version I was about to release but removed it at the last minute since it was so messy.

    This takes some major restructuring to work as I want, but hopefully it should help a bit atleast.

  • Definitions - This is a rather 'cosmetic' change to the code but the way I am using the definitions interface is just wrong in every way. :) A Java interface should not contain any real code, it is just not supposed to work like that. Java does not have .h-files like C and there is a reason for it, so using the Definitions file like I have done just has to go.
Well that should get me started. :)

Jun 14, 2007

[New Version] v0.332 - Bugfixes, fen-strings in UCI and move legality check

Changes:
  • Fixed a problem regarding fen-strings using the UCI protocol (thanks to Phokham Nonava)
  • Mediocre now checks for legality of inputted moves in both the UCI and Winboard protocol (thanks to Volker Pittlik)
Note: I am releasing these two bugfixes now to get it out of the way so to speak. They have been ready for quite a while, but I have not had the time to finish up on some of the other changes, so by releasing this I have a fresh version to work on.

mediocre_v0.332

Jun 10, 2007

[Other] WBEC Ridderkerk edition 15 delayed

The next edition of WBEC was delayed to the beginning of August (instead of July) so that gives me some more time to get the changes done for it.

Jun 4, 2007

[Other] Busy times

I have been quite busy the last couple of weeks and have not had much time over for pretty much anything. Sadly it looks like this will go on for a while, plus summer is here. :)

My goal for now will be trying to squeeze in some time to implement ponder and new time management before July 21 when the World Computer Rapid Chess Championships starts. There are also a few small bugs I will be looking at.

Also Volker Pittlik has been having trouble with the executables for Linux, but I have no idea where to look for the problem. So if anyone else is experiencing this please let me know, preferably with some debug information about the error.

If I get the time I will try to setup up the Jonatan vs. Mediocre match sometime soon. Will probably be a couple of weeks until then though.

May 19, 2007

[New Version] v0.331 - Bug fix for Winboard and Chessbase interfaces

Changes:
  • Fixed a bug that caused the feature command not being recognized by Winboard, and the first id command not being recognized by Shredder and Chessbase
Note: As I said in my previous post I think this should take care of the problems with both Winboard and Chessbase. (it takes care of the Winboard problem for sure)

mediocre_v0.331

[Bug] Both problems solved with one change (hopefully)

I found the problem with the Winboard interface, and I think it is the same with the Chessbase GUI (I will have to wait for Jim Abletts compiles to be sure, guess it is time I get a Java native compiler soon :).

In v0.32 and earlier when starting Mediocre without interface the welcome message and prompt did not show up until a dummy command was entered. This was due to Mediocre waiting for either uci or xboard to come as the first command to determine what protocol to use. If the first command was neither of those it went into line input mode.

I fixed this by always going into line input and if at any time uci or xboard was entered at the prompt, Mediocre switched to the protocol input instead.

But I forgot that I used print and not println for the prompt. This resulted in the feature line starting with the prompt (->feature ... instead of just feature ...), and apparently Winboard did not understand this and hence never received the feature command.

Which in turn resulted in the moves sent by the interface to the engine were on the form e2e4 and not usermove e2e4, so Mediocre could not recognize them.

The same happens in the UCI mode, only the second id command is received (the author one), while the name of the engine (id name Mediocre) is ignored since it is started with the prompt as well.

Hopefully this is why Chessbase GUI is having trouble. Shredder Classic only gives the author name and you have to input the engine name manually but at least it runs the engine afterwards.

Let us hope this takes care of both problems. :)

[Bug] Chessbase GUI problems

Seems I managed to seriously mess something up. :) Apparently Mediocre isn't running under the Chessbase GUI either at the moment.

Hopefully I will be able to fix it today.

May 18, 2007

[Bug] Winboard problems in v0.33

I have gotten a few reports that Mediocre is not running on the Winboard interface (but works with winboard protocol in Arena). I am trying to track down the bug, posting a fix as soon as I find it.

May 17, 2007

[New Version] v0.33 - Pawn and eval hash

Changes:
  • Eval hash added
  • Pawn hash added
  • The zobrist keys are now pseudorandom, meaning they stay the same when restarting the application
  • Pawn zobrist key added to the Board class
  • Pawn eval divided between structure and passed pawns to fit with the pawn hash
  • Switched name between 'depth' and 'ply' in the search, depth is the number of plies left to search ply is the number of plies deep the search currently is
  • Fractional plies added
  • Matethreat extension and pawn to 7th rank extension added
  • It is now possible to change the transposition table size in the mediocre.ini file
Note: I am not so sure about strength difference between v0.32 and v0.33, the new version runs faster for sure but there might be some bug somewhere that I have no yet found. Anyway I thought I should release this and see how it works for other people.

I made new addition to the readme.txt about setting the hash table size, here it is so you do not miss it. :)
Mediocre now comes with mediocre.ini in which you can set the size of the hash tables, and decide wether the own opening book should be used.

Since Mediocre is a Java engine it gets 64mb RAM allocated by default. In the .bat file I have now added "-Xmx1024M" which allocates 1024mb RAM instead. This is NOT the size of the hash tables or how much RAM Mediocre will use, it is merely the maximum amount the application CAN use.

If you set the size of the hash table to anything larger than the allocated memory Mediocre will not run. If you want more RAM to be allocated simply increase the number in the -Xmx1024M (e.g. -Xmx2048M). Again this is not how much the application will use, but how much it can use. Decreasing the number will have no other effect than not making Mediocre start if hash table size is set to anything larger.
Have fun playing around with it. :)

Edit: Fixed the version number in the application. Thanks Jim for noticing.

mediocre_v0.33

May 14, 2007

[Other] A little update

I am still working on getting the new hash tables to work smoothly. I have not had that much time lately since final exams are coming up, but slow and steady wins the race. :)

I hope I will be able to work out the last quirks soon and start looking at pondering and new time management.

May 7, 2007

[Other] The Jonatan vs. Mediocre match

When I created this blog almost six months ago I had three goals. Mediocre should be able to:
  • Play by all the chess rules
  • Play on ICS (and versus other engines)
  • Beat me in a match
The two first have been done for about five months now, but the last one I have put off.

Mainly because playing a match at classic time controls takes a lot of effort from my side and I want to be sure I get beaten since I probably won't have the motivation to play another match. :)

I think Mediocre is about ready to whoop the floor with me so I will plan a match in the near future, probably beginning of June.

The match will be 10 games at 2 hours per game. And if I get my personal ICC account up and running by then I will play it there (being a student I am a bit strapped for cash, that is the price you pay for too much spare time :).

I should have Mediocre v0.33 ready, and I will try to implement a few time management parameters since I have a feeling Mediocre uses the time pretty badly at longer time controls.

Hopefully I will also be able to implement ponder so Mediocre can play at full strength.

May 6, 2007

[Other] Still hashing

I have now divided the pawn evaluation so the passed pawns are separate from general pawn structure evaluation. This is needed since passed pawns depend on the king's position (and to some extent on other pieces as well) and that is not included in the pawn hash.

Running the selected.pgn YATS set to 8 ply fixed depth I get these results from v0.32 and the version with eval and pawn hash.
Analyzed Positions    : 26
Different Moves : 0
Different Scores : 0
Different Times : 6

Time Mediocre 0.32 : 1:52
Time Mediocre dev : 1:25

Nodes Mediocre 0.32 : 11.923.392
Nodes Mediocre dev : 11.859.579
This is exactly what I am looking for, same evaluations and moves, only faster with the eval and pawn hash.

I will still have to do some testing to find the right sizes for the tables, but it seems to be working without bugs now at least.

May 4, 2007

[Other] Some hash statistics

As you know I am currently working with the eval and pawn hash for the evaluation. With both implemented it seems Mediocre goes from around 100.000 nodes per second to about 150.000 on my hardware (AMD Athlon 2500+). This is quite promising since it is a pure speed gain, i.e. the exact same number of nodes are visited for each ply of the same position, and the end result is (should be) exactly the same (same move and same evaluation).

From the start position searched to 10 ply I get:
evalHashHits 40409
evalHashMiss 100159
pawnHashHits 126433
pawnHashMiss 14135
As expected the pawn hash hits far more often than the eval hash.

While the eval hash seems to work flawlessly the pawn hash is having some problems. Sometimes returning wrong values, this is of course not acceptable, but instead of just fixing the bug I will take a look at how the pawn evaluation is handled and adjust it to work smoothly with the pawn hash.

May 3, 2007

[Other] Setting hash table size

I have been working a bit with an eval hash table and pawn hash table. The eval hash table seems to be a quite noticeable improvement and is very easy to implement, there are a few tweaks I can come up with but in general it is pretty straight forward.

The pawn hash table on the other hand is a bit more complicated since it is only part of the evaluation and some things needs to be worked out on every call to evaluation (like the attack table). To take full advantage of the pawn hash it also needs to store information about passed pawns so we do not have to find them every time.

Because of this I had some doubts of how much the pawn hash would actually help, but since the pawn structure changes very rarely it should be a nice boost as long as it gets implemented smoothly.

Sizes

Now Mediocre will have three hash tables, main transposition table, eval hash, and pawn hash (and the repetition table, but it is so small it hardly counts). So what sizes should these have?

In Scorpio the default sizes are 16mb for main transposition table, and 8mb each for eval and pawn hash. These ratios seems quite logical (i.e. twice as big main transposition table as eval and pawn hash).

I could implement these sizes in the code directly, but it would be a lot smoother if the user could choose this, and this is currently not possible in Mediocre.

So it is time to be able to choose the hash table size in Mediocre. I have been meaning to do this for quite some time but it seems I always end up trying to implement some playing improvement feature instead.

The UCI protocol comes with a command where the hash size can be set, while Winboard lacks this option. Since Mediocre supports both protocols I am going to start with creating a settings file where the hash size can bet set, and later make it possible to change through the interface using UCI (during run time).

Since we have a settings file we might as well implement a few more settings to choose from. Like if the own opening book should be used or not.

Paths

I ran into a problem when trying to let the settings file decide in what directory the opening book should be located. Since Java is supposed to work on several platforms you have to be careful with using absolute paths. E.g. C:\books\book.zip will not work on a Unix machine.

So to be safe the paths should be e.g. ./books/book.zip

The real problem however was getResourceAsStream (which is used in the Book class) uses the path the file running is in, and not the path the application was started from. So if we use the Mediocre.bat to start Mediocre and have the the binaries in the bin-folder we need to use the current directory to find the Mediocre settings file, but ../book.zip to find the book file if it is located with the Mediocre.bat.

Messy? Yeah. :)

The problem is I can never know if the user is using an executable which will have book.zip in the same folder, or Mediocre.bat which will probably have the book.zip in the parent folder, so both folders will have to be tried which can get messy since getResourceAsStream uses another root directory.

The problem with book.zip is an old problem I have had. So far I have always had it in the bin-folder which is not logical.

I think I will sidestep all this and just assume all files Mediocre needs will be located in the same folder.

More settings

In future releases I might make it possible to change evaluation terms through the settings file as well as things like table bases and such.

(thanks to Tord Romstad for clearing up a few issues with hash tables for me)

May 2, 2007

[Other] Not 4.0

I noticed the latest release of Mediocre got zipped in a folder called "4.0", just ignore that. It is still v0.32. I have no idea why I named the folder that. :)

May 1, 2007

[Other] v0.32 test run

I ran a small tournament to try out the new version and it went pretty well for Mediocre. 3 minute games, with Arena main book.
01: GreKo 5.2.5     34,0/40
02: Mediocre 0.32 28,0/40
03: Pupsi 0.18 26,0/40
04: Lime_v62 25,0/40
05: GERBIL02 24,5/40
06: Kingsout 0.2.42 24,5/40
07: FluxII 0.7 18,5/40
08: Feuerstein045 17,0/40
09: Tscp181 11,5/40
10: Roce036 11,0/40
11: Vicki 0.021a 0,0/40
2007-04-30 Big one.pgn

The battle for second place behind Greko was quite exciting, but Mediocre pulled off a great last round with 9/10 points (losing only to Gerbil).

Vicki was only reaching depths of around 2-4 ply on my hardware (AMD Athlon 2500+) so it was of course having a hard time, but I will enjoy watching it improve and it is fun seeing the progress from the beginning. FluxII has made some nice progress and is not far behind Mediocre now, I will have to keep up the pace. :)

[Other] Keeping the archive more up to date

I updated the archive with the latest releases of Mediocre.

From now on I will always do this when a new version is released.

[Plan] A reluctant look at hash tables again

Implementing the transposition table and draw by repetition detection was probably the most complicated and tedious thing I have done so far with Mediocre. The bugs are extremely hard to find and can have devastating effects so I have basically left it untouched since version 0.2.

Since I want a pawn hash table, and perhaps also an eval hash table (which I have tried briefly already) it is time to take another look at the structure of the hash tables in Mediocre.

I think there is some optimization to be done in the general setup of the tables as well, especially in the draw by repetition detection scheme.

I just hope I do not mess something up. :)

Apr 29, 2007

[New Version] v0.32 - Hung pieces evaluation and general tweaks

Changes:
  • Killer moves verification to avoid generating unnecessary moves
  • The finalEval is now started with globalBestMove to make sure we always get the right move there (I'm not sure this was ever a problem, but just in case)
  • Passed pawn values halfed in middle/opening
  • Fixed bug with x-ray attacks for queens
  • Simplified castling rights code
  • Added time search to line input and fixed some bugs
  • Dynamic null move depth
  • Futility check moves outside while loop
  • Fixed bug with black queen on 2nd rank bonus
  • Increased bonus for rook on 2nd/7th rank
  • Searched moves instead of HASH_EXACT to determine LMR and PVS (results in more reduced moves)
  • Hung piece check in the evaluation
  • Tempo bonus in evaluation
Note: Of these changes the hung pieces in evaluation probably helped the most. I am still having trouble adjusting everything to work together but this release should be a noticeable improvement. More to come...

mediocre_v0.32

[Other] Some confirmed improvement

The changes I mentioned yesterday plus some tweaking to the late move reduction and principal variation search resulted in a noticeable improvement in a 200 game match against v0.311. About 50-60 elo points or so.

I did some tweaking to the aspiration windows as well and I am going to test it extensively today, hopefully it helps a bit as well and I can finally release v0.32.

Apr 28, 2007

[Other] Many attempted improvements

A couple of days ago I started testing every change I made for the new version one by one to see if I could find some obvious flaw in the code.

I implemented one change and ran a few test suites on it to see if it helped or made things worse, and then tried implementing one more and so on.

These are the changes I have tried so far:
  • Killer moves verification (avoids generating unnecessary moves)
  • Passed pawn values halved in middle/opening
  • Fixed a bug with queen's x-ray attacks
  • Dynamic null move depth
  • Slightly optimized futility pruning
  • Increased bonus for rooks/queen on 2nd/7th rank
  • Fixed bug with black queen on 2nd rank bonus
All these changes made no difference at all in self-play, and resulted in slightly worse results in the test suites.

However by testing them one by one I noticed the worse result in the test suites was only due to the last change. Without it the results were actually slightly better than without the changes.

The bug (as I mentioned before I think) was black queen getting the bonus for being on the 7th rank instead of on the 2nd rank. This is obviously a bug and should be fixed, but resulted in quite a few points less in the test suites I tried for some reason, this is just a coincidence and should not affect general play in that way.

So I am going to stick with these changes, even though they actually do not seem to affect playing strength at all. I will not release a new version until there is a clear improvement however, but at least I have gotten somewhere.

I have a strong feeling the dynamic null move pruning (reduces 3 ply if the remaining depth is deeper) helps more at longer time controls, but at least it does not hurt the play at shorter time controls.

Apr 24, 2007

[Other] Testing and testing

I have been playing around with a few new versions of Mediocre.

One version (which I call Mediocre v0.32full) includes all the tweaks I have tried so far, with things like; adaptive null move pruning, evaluation based LMR (it actually reduces more moves now), fractional plies, mate and move history in the board object, new extensions, restructured futility pruning, and some changes to evaluation.

I have had very mixed results with this version and until yesterday it played much weaker than v0.311.

Yesterday I tried only allowing null moves if the depth left was atleast 2 plies (which is the common way of doing it) and suddenly it started playing on par with v0.311. The results from the btm test suite is about as good as v0.311 but v0.32full searches about 1.5 deeper on average, which should be explained mainly by the greater number of moves reduced (apparently they are not all sound as of now).

I think there is a great deal of potential and there are probably a few more 'bugs' like this to work out.

Apr 20, 2007

[Other] Fixed

I have now updated and uploaded the correct files. Dangerous to do changes too early in the morning I suppose. :)

[Other] Whoops

I accidently updated the wrong sources so version 0.311 does not use null moves. I will upload the correct version in a few minutes. Sorry. :)

Apr 19, 2007

[New Version] v0.311 - Bug fix for winboard protocol

Changes:
  • Fixed a bug that made the engine enter an infinite loop if it was mated using the winboard protocol
  • Reworked the ended game draw detection using the winboard protocol (does not affect the search)
Note: This is merely a bug fix and nothing else has been changed, however in very fast games (less than 2 minutes or so) this version should play better than the previous while using the winboard protocol since the old end game detection was hideous. :)

mediocre_v0.311

[Bug] Fixed the winboard protocol problem

When using the winboard protocol along with the Winboard interface and Mediocre got mated the engine entered an infinite loop. This happened because Winboard sends the mating move to the engine while for example Arena does not, it simply states the result once the game is over.

So what happened was the mating move was played on the board and then Mediocre started searching, but since it had no legal moves at the root node (since it was mated) the searchRoot returned -INFINITY as evaluation which got caught by the window check and a research was made, and since the evaluation returned never changed from -INFINITY the loop never exited.

Some poor programming from my side of course. I changed it so the root moves are generated before the iterative deepening loop (since they never change in the current search) and if no legal moves are found an empty pv is returned and handled by the input loop.

Thanks to H.G. Muller for sending me some games that made it easy to locate the bug.

[Bug] Something with the winboard protocol

A few people have reported problems while using Mediocre with the winboard protocol.

I am quite certain the problem is with the 'end of game'-verification, I just have to locate it.

The reason I did not notice this earlier is I pretty much only use UCI when I run tournaments.

I will release a hotfix when I find the problem.

Apr 15, 2007

[Guide] Fractional plies

Fractional plies are used to make it easier to tune extensions (and reductions).

If you have an extension that might not be worth extending a full ply, you could extend it 0.5 plies instead and only if you get two of those in the same branch the branch is extended with one ply.

The easiest way to make this work is change the way the search handles the depth altogether.

In Mediocre the call to alphaBeta from the root will look like this:
eval=-alphaBeta(board,current_depth*PLY-PLY,-beta,-alpha,true,1);
Where PLY is a fixed number that represents a full ply, 16 for instance. So if we wanted to search to 10 plies we would call alphaBeta with 10*16-16 = 144, which means we call it with 9 plies left to go.

If we wanted to extend one ply we add 16 to the call, so the call would be depth-PLY+16.

To extend 0.5 plies the call would be depth-PLY+8 and so on.

When we run out of 'depth' the quiescent search is called and this happens pretty much automatically like this:
if(depth < PLY) do_quiescent();
Meaning we do not have a full ply left to search so we start the quiescent search (which does not keep track of depth so we do not have to worry about it there).

Fractional plies is very easy to implement (basically replace all depth-1 with depth-PLY) and is very handy to have.

[Other] Test sets

Up until now I have been testing additions to Mediocre by trying it on random positions and basically look at the node count and time to decide if the addition was an improvement or not.

Once I started to feel satisfied with a new version I ran as many games as I had patience for, somewhere between 100 and 1000, against the last version and a couple of other engines.

I never really ran into any problems using this crude way of testing since pretty much every addition and change resulted in a very noticeable improvement.

However recently I have been having some serious trouble determining if new changes actually improves the engine or not, so it is time to refine my methods a bit.

New way of testing

Quick test: Run the YATS test sets selected.pgn and tony.pgn at 5 seconds per position, and analyze the results with Pro Deo 1.4. This takes 3.5 minutes and gives a general idea of the effect of the change(s).

Mediocre v0.31 got the following results:
Testset        : selected.pgn
Level : 5 seconds
Engine : Mediocre 0.31

Positions : 26
Found : 1 (3.8%)

Maximum points : 260
Scored points : 145 (55.8%)

Maximum time : 2:10
Used time : 2:05

Testset : tony.pgn
Level : 5 seconds
Engine : Mediocre 0.31

Positions : 16
Found : 2 (12.5%)

Maximum points : 160
Scored points : 69 (43.1%)

Maximum time : 1:20
Used time : 1:17
Full test: Run the btm.pgn (Beat the Masters) YATS set at 1 minute per position. This takes 2 hours 46 minutes and should give a very good idea of the strength of the engine.

Mediocre v0.31 got this result:
Testset        : btm.pgn
Level : 60 seconds
Engine : Mediocre 0.31

Positions : 166
Found : 32 (19.3%)

Maximum points : 1660
Scored points : 993 (59.8%)

Maximum time : 2:46:00
Used time : 2:20:43
If this results in an expected improvement to the engine run a 100 3-minute game match between the previous version and the new version using the sherwin50.pgn test set (by Michael Sherwin). 100 games means two games per opening so each version gets to play both sides.

By using a fixed set of openings a lot of the randomness is taken out and it should be easy to determine if the new engine is an improvement and by how much.

100 3-minute games take somewhere between 5-10 hours, probably closer to 5.

Why YATS

YATS is a testing system created by Ed Schröder, that instead of giving 0 points for a wrong answer and 1 point for a right answer rewards 0-10 points depending on what move the engine chooses. 10 for the 'correct' move and less for alternative moves that might still be good.

For a mediocre engine, like Mediocre, this is a perfect way of analyzing its strength. It might not find the 'best' move very often, but usually find a decent alternative move in the same position.

This way even one analyzed position might supply some interesting information, an old version might find an alternative move that gives 2 points while the newer version finds a slightly better alternative that gives 5 points. The traditional test sets would reward 0 points for both versions.

Further reading on the YATS-site.

And stick to it

Having set up this testing structure I do not intend to change it for quite some time, except for perhaps adding a fixed depth search to the YATS sets as well.

By having it unchanged like this it will be much easier to determine individual strength of the different versions over time without having to run thousands of games just to avoid the inherent randomness of openings and in fact chess in general.

Apr 14, 2007

[Other] Stack done

I now have a working stack done for the Board class. It keeps track of trivial things like castling rights and en passant squares to make unmakeMove possible, but also what moves were played to reach the position and if the position is a check or not.

Things like determining if the last move played (i.e. in the last instance of the recursive alpha-beta) was a promotion, or a capture, or a check etc. are very simple now.

I should have done this a long time ago, but well, the first thing I wrote was the Board class and I simply did not realize what was really needed in it back then.

As I said the makeMove method now determines if the position before making the move is a check or not. I do not know if this is really nescessary, but considering pretty much every node uses this information in one way or another it is probably ok.

The problem is deciding if the next move to be played will be a check without actually playing it on the board. This is another matter though and I will probably implement a gen_checks to take care of that.

Anyway the way it works now the move generation is about 20% slower than without the checks, but all in all it should turn out to be slightly faster when used in the search. And most importantly it will make things like futility pruning and LMR much easier to adjust.

[Other] The joys of bug hunting

After some reconstructing of the makeMove, umakeMove, makeNull and unmakeNull methods I ran into a long streak of errors popping up in just about all positions.

I sat for a few hours commenting out all complicating code like transposition tables, null moves, futility pruning, quiescent search etc. trying to isolate the error but it kept appearing at the exact same spots. The perft numbers worked perfectly, so I had to look for the error in the search.

So I started printing the moves to see if I could find a pattern. I had found a position where the error appeared after 'only' 3000 nodes so the print out was atleast manageable.

At first I thought it was the legal move check that was the problem because that was the most obvious thing that was made differently from a plain perft search.

However, after 4 hours or so I concluded it had something to do with captures and it seemed to involve the hash move.

By then the time was 2am so I decided to try in the morning. And with a fresh mind I immedatiatly drew the obvious conclusion... hash moves depend on zobrist keys to work correctly of course, and there is a code segment in the makeMove method that updates the zobrist for captures.

And of course there the problem was, I had 'simplified' that part of the code and instead of removing black pieces from the zobrist I removed white and vice versa.

So it was the 'other' thing the search does differently execept for legal moves, it uses a transposition table. :)

This was so much fun I almost considered starting to put in intentional bugs just to enjoy solving them. Or not.

Apr 13, 2007

[Other] Some restructuring

I have taken a look at the different ways I could handle the extensions and it is a complete mess. :)

Currently the search is doing an inCheck at the beginning of each node to determine if we should extend for check. That inCheck is then used by null-moves and futility pruning for the current position.

After that futility pruning does another inCheck to determine if the next position will be in check, this is also done by the late move reduction.

So the worst case scenario does three inCheck lookups for one node. Which is just bad.

I have had a 'history'-array for quite some time that keeps track of passed castling rights, en passant squares and the fifty moves rule. Recently I extended that idea by adding another array that kept track of passed zobrist keys and captures to make the unmakeMove faster.

So basically there already is a stack keeping track of passed positions, only that it lacks information about inCheck and it does not remember what moves was made (only if they were a capture or not).

I am going to complete the stack with the needed information and make the inCheck while making each move so we always have that information.

I do not expect this to speed up the search that much, however the code will be much easier to modify which in turn will help make everything faster.

Apr 10, 2007

[Other] More work to be done

After 200 games the two versions finished with about equal score after a winning streak from v0.31 in the end.

I have a 'gut feeling' the v0.32 is be better, I can not see how it would not be. However at this point I am not looking for differences that take thousands of games to determine.

Mediocre is not nearly good enough to start chasing 1-2 elo points here and there, I want atleast 50-70 points (about 60% won games) before I am satisfied.

I think I will leave futility pruning and the evaluation as it is for a while and start looking at how extensions are handled. Currently Mediocre has only a very crude check extension, so I will take a look at extensions for mate threat (if null move returns a mate value the branch is searched more carefully), recapture, single-response and something regarding passed pawns.

I will need a new way of handling the extensions and probably make use of fractional plies for some of them. And while doing this I will take care of the repeated work Mediocre currently is doing for determining if a position is in check (it is done in the check extension, late move reduction and futility pruning, this should only be done once).

Off I go. :)

Apr 9, 2007

[Other] Settled for a futility

After some testing I decided which futility pruning I am going to use. These are the highlights:
  • Use full evaluation and margins 125 centipawns for frontier nodes and 500 for pre-frontier nodes, if the evaluation + margin does not reach alpha the move is considered for futility pruning
  • Consider the type of move, do not prune moves that
    • give check
    • move a pawn/queen/rook to the 7th rank
    • capture a bishop so the opponent loses the bishop pair
    • capture an pawn on the 2nd or 3rd rank
    • capture a queen
    The considerations are taken because these moves are likely to change the score more than average (e.g. moving a pawn to 7th rank will always make it a passed pawn, capturing the queen usually alters the king safety quite a bit etc.), thanks to Mark Lefler for these ideas
  • If the move is a capture make sure to add the value of the captured piece to the score and see if it still is below alpha minus the margin
  • If the move still is getting pruned after these considerations a final check is made to see if the evaluation is above the best evaluation of the node, if it is that evaluation is recorded so the node does not risk exiting without any evaluation
H.G. Muller pointed out to me that if one non-capture is futile, so is the rest so basically that check could be done before even generating the non-captures. However since Mediocre needs the move to be played on the board in order to determine if it is a checking move I can not do that just yet.

This setup is the best I found, but there does not seem to be a big difference between the implementations I tested. I really like the idea of not pruning moves that are likely to change the score however, and the way it is done here is very simple and effective.

Stumbling upon great things

Once I decided on this matter I went on to some other things, mainly bug fixes and such, but there was one thing that I stumbled upon that really seems to pay off. I wanted a pawn hash table since the pawn structure rarely changes and there is a lot of unnescessary work done in the evaluation.

However the implementation would take quite some work since the zobrist key for the pawns would have to be updated every time a pawn is moving and also the current pawn evaluation uses the king positions as well so that would have to be sorted out.

So I decided to try that later and instead I tried implementing a simple evaluation hash table that keeps track of passed evaluations so if we run into the position again that work does not have to be repeated.

This took about 5 lines of code and speeded up the search a huge amount. It almost feels like I did something wrong since I have read so much about how memory lookups are costly and barely worth it. But Mediocre took another little leap in strength with this change.

I will play a test tournament overnight and if the results are good I think it is worth releasing Mediocre v0.32.

Apr 8, 2007

[Other] Tweaking v0.31

I have yet to come up with the perfect implementation of the futility pruning in Mediocre. I ran a 300 game match between four different versions and the only conclusion was it is worth including captures in the futility, and I am already doing that. Using a limited material evaluation versus a full evaluation seems to be pretty much equal in strength.

There are a few more things to try out however, like not pruning pawns advancing to the seventh rank or similar, since they will most likely increase the score quite a bit.

There are also some adjustments to the evaluation that needs to be done. In v0.3 I had only a small bonus for rooks on the seventh rank since I did not check if there were actually pawns there (or opponent king on eight rank). Now in v0.31 I added that check so a rook on seventh should be valued higher than before.

The biggest flaw I found was with the x-ray attacks. A queen running diagonally into an own rook kept getting attack points behind it, this is obviously a bug and will be fixed.

Once I am happy with these things I will give candidate pawns another shot. I will most likely have to run a big test with them turned on and off to see if they are worth the effort in Mediocre. I am not expecting a big improvement from them in any case.

Apr 6, 2007

[New Version] v0.31 - Futility pruning and additions to evaluation

Changes:
  • Made a few arrays static in the SEE, speeding it up quite a bit
  • Futility pruning added
  • X-ray attacks in the evaluation (e.g. queen attacking empty squares behind own bishop)
  • Eval is adjusted towards 0 if a draw is likely
  • Pawns are valued slightly less but becomes a bit more valuable in endings
  • Knight outposts added
  • King tropism added
  • Rook/queen on 7th rank only awarded if enemy king on 8th or enemy pawns still on 7th
  • Fixed bug with bishop positioning and also one with pawn evaluation
Note: One particular implementation of futility pruning (and no additions to evaluation) performed slightly better against v0.3, however I believe this setup works better in general. Only testing will show so I am releasing this now since it is quite an improvement and make any needed adjustments in future releases.

Also I commented out the candidate pawns code. It follows the definition used in Fruit, but it got a bit messy and I did not notice any improvement from it. I will have to keep trying in that area.

mediocre_v0.31

Apr 5, 2007

[Other] Silly bug with bishops

I am currently reshaping the evaluation a bit and while doing that I noticed a very subtle bug. Instead of using the piece table for black bishops I used the table for black knights. This resulted in black thinking fiancetto was a bad thing since the knights get a penalty for standing on the G7/B7 squares, and also a smaller penalty for the D7/E7 squares (which are quite natural for the bishops).

I had been thinking about adding even more incentive for developing the bishops since it looked like they were rarely developed properly. This bug was probably the problem though.

[Other] New archive site address

Thanks to Wang Zhen the Mediocre archives now have a new ad-free home!

The new address is http://mediocrechess.varten.org/.

Apr 4, 2007

[Other] Finally futility

After hours of despair and a bunch of helpful tips that I could not get to work, I decided to post one of my implementations of futility on the Talkchess.com forum. And finally I got the mystery solved. :)

I had overlooked the possibility of all moves in a node fitting the requirements for futility pruning. In some of my implementations this caused a very faulty value being recorded for the node, and in other the mate detection thought no legal moves existed and returned the stalemate score (0).

After having sorted this out, the new implementation of fuility pruning in Mediocre is working like a charm.

I started a little tournament to test it out and the results so far looks quite promising:
   Engine            Score                              Me
1: Mediocre dev 0.31 20,5/30 ..............................
2: Mediocre 0.3 9,5/30 00=0=010101=110=0=00=0000=0001
And this is with futility pruning for only non-captures, so there is still some in there up for grabs.

Apr 2, 2007

[Other] Struggling with futility pruning

About two months ago I tried implementing futility pruning. I failed miserably and decided to blame it on the general structure of Mediocre at the time. :)

Once again I am trying to get it to work and obviously I am doing something terribly wrong. I have tried three different setups and run 100 games matches against version 0.3, all three setups resulted in weaker play.

The theory is so simple that I must be missing something.

Well I will keep trying this time.

Apr 1, 2007

[Other] Mediocre website is up

I uploaded the website. For now you can find it at http://hem.passagen.se/maragor/, sorry for the horrible ad covering half the page, it was the easiest solution. When a get a tad better cash flow I will probably get a better location for it.

It is very simple and only intented as a bit more structured way of reading the guides and downloading older versions of Mediocre, atleast for now.

As I said earlier I will be adding content to the site from the blog now and then.

One nice thing is the links to old Jim Ablett executables of Mediocre which I have not had up anywhere before.

Well enjoy. :)

Mar 31, 2007

[Other] Mediocre entered Division Poussin

Le Fou Numérique updated their divisions and Mediocre was entered in the lowest (just above the reserves).

Le Fou Numérique only uses UCI engines and this is how the division Mediocre will be playing in looks like:
Engine    Rating
Adam 2125
Mediocre 2116
Matheus 2106
Monarch 2098
Lime 2097
Firefly 2053
BigLion 2052
DelphiMAX 2035
Tournaments within the divisions are run regurarly so I am quite happy about this. 'Official' results from a third party are always nice to have.

Mar 30, 2007

[Other] Working on a website

The last couple of days I have been working on gathering all the important parts of the blog into a simple website. As the blog has grown it has become harder to find the good stuff and it is probably about time I do something about that. In the picture you can see a glimpse of the basic layout.

The website will be static in nature, meaning I will not update it like I do with the blog, but every now and then add new content from the blog to it.

As for the address I will probably use the same space as I do for storing the versions of Mediocre, to start with.

I will inform you when it is ready. :)

Mar 26, 2007

[Programming] Faster SEE

For some reason I had the following lines inside the see() method. Meaning they were initialized every time the SEE was called:
int[] piece_values = {0,1,3,3,5,9,99,0,99,9,5,3,3,1};
int[] w_attackers = new int[16];
int[] b_attackers = new int[16];
int[] scores = new int[32];
Since we actually do not have to clear any of these at the start of every SEE-check (we keep track of the index and never use what existed there before) I simply moved them out of the method, making them static variables that are not cleared at each call.

This speeded up the SEE-check with about 30-40%. Imagine that. :)

Now SEE is not called that insanely often so in total this small change probably only accounts for a 5-10% speedup overall. But it is a reminder that you have to be careful with your initializations in Java. :)

[Guide] Late move reduction (LMR)

A late move (as opposed to an early move :) is a move that gets sorted late in the list of moves we are about to search.

These moves should rarely produce any good results. For example the latest moves of them all, the losing captures, need very specific features of the position to be successful. Things like a sacrifice exposing the enemy king. But in the general case these moves will just be bad.

The idea of the late move reductions is since we predict these moves will not produce any good results we might as well reduce the time we spend on them.

One neat feature with LMR is that it considers the moves that are likely to fail low, i.e. moves that are not good enough, as opposed to null-moves that tries to find moves that fail high. Since these two techniques operates in different ends of the spectrum they are not likely to overlap, which many other reducing techniques are prone to do.

How it works

Here are the lines of code I added to Mediocre, just before the search is about to go into the PVS search.
if(movesSearched >= 4             &&
ply >= 3 &&
Move.capture(moves[i]) == 0 &&
!isInCheck(board))
{
eval=-alphaBeta(board,ply-2,-alpha-1,-alpha,true,depth+1);
}
else eval = alpha +1;

if(eval > alpha) // Continue with PVS search
We start with a few conditions for when we are allowed to reduce moves, more about this below. Then we do a search with a minimal window (since we are only interested if the move fails low or not) using a reduced depth. We reduce the depth with 1 extra ply (a usual search is ply-1). If the eval comes back lower than alpha we are satisfied with this result and can be quite confident that the move was indeed a poor one.

If the search however comes back higher than alpha, something is fishy and we have to continue with the ordinary search at regular depth.

When to reduce

The main idea comes with the first condition; movesSearched >= 4. Basically we start with searching all the likely contenders for best move to full depth, these being the hash move (by far the most common best move), good/equal captures (if there are any), the killer moves and possibly one or two of the best non-captures.

In general 3-4 moves is a good amount of moves searched to full depth before starting to reduce.

Now we need some guidelines as to what we should reduce among the 'late' moves. Here are some type of moves that we probably should avoid reducing:
  • Checks - and any other moves that the engine extends, if we reduce an extended move, the extension effect is cancelled
  • Captures - unless they are losing, and maybe not even then
  • Promotions - atleast if they are queen promotions
These are the obvious ones, there are several other techniques for determining if a move is safe to reduce. Moves that historically failed high might not be good to reduce, neither might moves that raises the static evaluation above alpha or moves that can be determined to cause some sort of threat. These techniques are however a bit more tricky to implement.

This is a rather new technique and there are endless possibilites how to handle the reductions. You could for example try to reduce more than one ply or skip the research when a move comes back above alpha.

For further reading take a look at http://www.glaurungchess.com/lmr.html.

Does it work in Mediocre?

Indeed. And extremely well. Even though I have only tested with a few different setups so far, each and every one of them has given fantastic results. Even the simplest reduction conditions (only captures not being reduced for example) seems to work like a charm.

I will have to do some more testing to see what works best.

I think it is time to call it quits here for tonight. I am not sure if I should go through the evaluation since it is rather huge so it is probably better if you read it off the source code.

Hope you enjoyed my little guide-suite. :)

[Guide] Static exchange evaluation (SEE)

Static exchange evaluation is a very powerful tool for evaluating a capture without actually playing out the moves.

It is mainly used for sorting quiescent (and ordinary) moves which produces far better results than the MVV/LVA scheme.

The implementation is very code specific, meaning there are not many general rules that apply, we simply have to find a fast way of determining if a capture gains or loses material once all the moves in the sequence has been played out.

To fully understand how it is done in Mediocre you might want to take a look at the source code in See.java which is not very long but heavily commented, I will try to give the general idea here though.

General outline

The see() method takes a move we want to check. This move is done by the initial attacker. For example Qxb6 in the diagram. It then returns a value for what this move is worth. If B6 contains an undefended pawn the value would be +100. However if the pawn is defended one time and there are no more attackers (like here) the value would be -800 (-900 for the queen +100 for the pawn).

I will use this queen and pawn capture sequence as an example when explaining other things below.

What we want to do is simply find all attackers, let them capture alternately on the square starting with the lowest valued piece, keep track of what pieces capture and finally find the best possible results of the capture sequence.

I have divided it into a few steps.

Step 1: Finding the obvious attackers

We start with finding the 'obvious' attackers to the square. Meaning pieces that directly attack it. If there are two rooks on the same file for example only the first rook is directly attacking the square, the second is indirectly attacking it and this will be handled later.

The initial attacker is not added here but handled separately.

We do this in the fastest possible way, for example we do not loop over all the pawns for each side, we simply check squares where a possible pawn could attack from, and if it contains a pawn of the right color we add it.

This is the general approach throughout the code. Instead of taking a piece and see if it can attack the square, we take the square and see if a delta runs in to a piece of the right type.

In the diagram you can see how we check for attacking pieces in the different deltas, red for straight, green for diagonal and orange for knight. Since the queen is the initial attacker it will not be added but handled separately as already mentioned, however the black pawn will.

When this is done we have two arrays, w_attackers and b_attackers, filled with all the obvious attackers of the two sides.

Step 2: Simulate the inital capture

We now simulate the inital capture. This is done like this:
score = piece_values[Move.capture(move)+7];
attacked_piece_value = piece_values[(Move.pieceMoving(move))+7];
sideToMove = board.toMove*-1;
The piece_values array simply contains the piece values (with an offset of 7 since black pieces have negative indexes).

So what was done was setting 'score' to the piece that was initally standing on the square (a pawn in the example, so score would now be 1), setting attacked_piece_value to 9 (for the queen) and 'switching' the side to move.

Keep in mind that we do not actually carry out this on the board, we simply simulate it. 'sideToMove' is just an internal integer that keeps track of what side to simulate next.

The attacked_piece_value keeps track of what piece is currently 'standing' on the square. In this case it is 9 since the white queen 'moved' there by capturing.

Finally we update the first index in the scores-array (not same as the score integer) with the score. After the capture sequence this array will be filled with alternating white and black piece values.

Step 3: Adding hidden pieces

Now that the queen was 'moved', we need to check for any pieces that might have been 'hiding' behind it, and hence attacking the square indirectly.

We do this by using the delta the queen moved with (that is by rook delta), and starting from the square the queen stood at we move away from the attacked square.

If we run into to a rook or queen while moving in this direction (since those are the two that can use the delta) we can add it to the attackers. If we run into any other piece, or move off the board, no attackers were hiding behind the queen.

You can see how this is done in the diagram.

The same is done for the other pieces, except for kings and knights. No piece can be hiding behind a knight (think about it), and pieces hiding behind kings are futile since if it is a piece of opposite color it would just catch the king and win the game, and if it is a piece of the same color it will never be able to reach the square since that would mean some other piece captured the king first in the sequence.

Step 4: Playing out the sequence

Now we simulate captures on the square, alternating between white and black, always capturing with the least valuable piece first. And updating the scores-array as we go along like this:
scores[scoresIndex] =
attacked_piece_value - scores[scoresIndex - 1];
scoresIndex++;
After every capture we attempt to add a hidden attacker.

Once we run out of attackers of either side the sequence is done and we stop.

So in our example we start out with the scores[0]=1 from the captured pawn, and on the next pass we add 8 (=9-1) to scores[1], and then we stop since white ran out of attackers.

Step 5: Evaluating the sequence

Now the scores-array is filled with piece values so we can extract the value of the sequence.

It is done like this:
while(scoresIndex > 1)
{
scoresIndex--;
if(scores[scoresIndex-1] > -scores[scoresIndex])
{
scores[scoresIndex-1] = -scores[scoresIndex];
}
}
return scores[0]*100;
In our example the scores-array would look like this {1,8}.

So scoresIndex would start at 2.

We decrement it to 1 and if scores[1-1] > -scores[1] (in our example 1>-8) we put the lower value in front.

Since we only had two captures in our example we are done here. And can return the centipawn value of -800. Since the queen captured a pawn and then was captured itself.

In conclusion

As you can see the example would sort under 'losing captures'. Winning captures would get a positive score and equal captures would get '0'.

It is hard to write a guide about something this code specific. But atleast I made an honest attempt. :) Hope it helped.

On to explaining LMR.

Edit: Added a few more images for better illustration

[Guide] Generating moves gradually

To start off I can say that this is one way of doing this, I am sure there are plenty of other ways that might be better (or worse). All I know is this made Mediocre a whole lot faster and if you do not have something similar it might well be worth implementing it.

Older versions of Mediocre had one big move move generation method called generatePseudoMoves(). This method generated all possible moves on the board and these were then 'filtered' with the method filterMoves(). The filterMoves method filtered out the moves that left the own king in check which resulted in all the legal moves.

For quiescent search moves the same was done except only captures were verified for legality (and the rest discarded).

A quicker apporach

To save time it makes sense to only generate the kind of move we want, capture or non-capture.

This is done by separating the generatePseudoMoves() into two methods, gen_caps() and gen_noncaps(). We simply do not store any move that is not a capture in the gen_caps, and do not store captures in the gen_noncaps.

Already by doing this we are saving some time in the quiescent search, but the ordinary search needs to use both the methods to get all the legal moves obviously.

However this is only part of what we can do with this.

Gradually finding all moves

In Mediocre v0.241b I introduced a way to avoid generating moves before we searched the hash move. If the hash move caused a cut-off we saved the time it would cost to generate the moves.

However if the hash move did not cause a cutoff all moves were generated, ordered and searched in one go.

Elaborating on this approach we can split up all the move generation in a similar fashion. In pseudo code it looks something like this (see the source code for Mediocre 0.3 for the full code):
while(generationState < GEN_END)
{
switch(generationState)
{
case GEN_HASH:
selectHashMove();
break;
case GEN_CAPS:
gen_caps();
sortCapsWithSee();
selectNonLosingCaps();
break;
case GEN_KILLERS: // See below
case GEN_NONCAPS:
gen_noncaps();
sortWithHistoryHeuristicAndKiller();
selectSortedNonCaps();
break;
case GEN_LOSINGCAPS:
selectLosingCapsFromCaps();
break;

for(int i = startIndex; i < endIndex; i++)
{
pickMoveFromList();
verifyTheMoveForLegality();
searchMove();
}
generationState++;
}
As you can see we start with selecting the hash move (if it exists, which it should after the internal iterative deepening), and searching it.

After we have searched the hash move and it did not cause a cut-off we move on to generating captures and ordering them with SEE (explained later), making sure we do not research the hash move (this goes for all the proceeding steps, if we run into the hash move again we simply discard it since it has already been searched).

When the captures are ordered we will have two parts, one with good/equal captures, and one with losing captures (captures that seem to lose material). We start with searching the good/equal captures one by one, leaving the losing captures for later.

Here is the next big time saver, instead of verifying all moves up front, that is checking wether it leaves the king in check, we save that check for when we actually search the move. If we get a cut-off somewhere we saved all the time verifying the rest of the moves.

So we take the first move in the good/equal captures list, verify it for legality and then play it on the board and search it.

Next comes the killer moves, for now they are handled in the non-captures part (more below).

So we generate the non-captures, sort the killers first and then by their history heuristic values. Verify each move and search it.

And last we get to the losing captures which rarely are any good (queen capturing a protected pawn for example) and do the same with them. We can not simply discard the losing captures here since they might lead to a winning combination that the SEE does not spot (however in the quiescent search the losing captures are indeed discarded, more about that later).

Extending the idea; killer moves

The killer moves are always sorted first in the non-capture phase as I explained above. However we already have the killer moves available without generating anything at all.

The problem is the killer moves are moves that are generally good at the certain ply, but we can not know if the move actually exist in the position we are at.

For example capturing a rook with a bishop might usually be good at a certain depth, but if we moved that bishop earlier in the search that move probably does not exist at this particular position.

To solve this we could write a verifying method that takes the killer move and checks if it actually exists on the board, if it does we could just play it without generating all the non-captures first.

I have not done this for Mediocre yet but it seems like a good idea since the killer moves often cause cut-offs, saving the time it would take to generate the non-captures.

Extending the idea; check evasions

When the own king is in check there is a very limited amount of moves that can be made to avoid the check. So instead of generating all possible moves with gen_caps and gen_noncaps we could make a third method called gen_evasions that only generates moves that takes us out of check. With the given condition that we know our king is in check this could be done quite fast by searching for the checking piece and generating moves that intervenes it.

This way we would save some time by not generating a bunch of moves that would be instantly be discarded by the inCheck lookup anyway.

I have not done this yet for Mediocre, but probably will quite soon.

In conclusion

This saved a whole bunch of time for Mediocre, mainly because the old move-sorting scheme was very crude and did a whole lot of unnescessary work.

Saving work until it actually has to be done is generally a good idea.

Moving on to SEE.

[Guide] Piece lists

I have been putting off the guides for some time. The main reason is we are entering territory that can be very implementation specific. Things that might work perfectly for one engine might be totally wrong for another. However I will make an attempt at explaining the five major new additions to Mediocre. Namely:
  • Piece lists
  • New way of generating moves gradually
  • Static exchange evaluation (SEE)
  • Late move reductions (LMR)
  • The new evaluation with Ed Schröder's scheme for piece attacks
In this post I will discuss the piece tables and why they are important.

The benefits Piece Tables

In earlier versions of Mediocre there was no easy way of determining where a piece was placed on the board. All we had was a 128 slot array with all the pieces and empty squares.

To find a particular piece we had to loop over all the squares. It is possible to speed this up quite a bit, by for example making sure we do as few loops over the array as possible, gathering all the nescessary information in one pass.

However it is still a slow process and even worse it makes for some very complicated code when trying to limit the number of loops. The old evaluation was an example of this with two huge loops trying to gather all the information at once.

A far better approach is letting the Board-object keep track of all the pieces and place them in separate lists as they move around. There are some things to consider while doing this, capturing a piece for example is no longer as simple as overwriting it in the boardArray. We now also have to remove it from its corresponding piece list.

Also promotions gets more complicated, we have to add a queen to one list and remove the pawn from another list. And similar when unmaking the promotion, the queen has to be removed and the pawn replaced.

There is also the matter of recognizing what particular piece is moving (not just its type). When moving a pawn from a2-a4 we have to know which of the pawns was moving so we know what index in the pawn list to change. We could of course loop over all the pawns to see what slot had the particular index and change it, but this would be quite slow.

Here is an attempt at an explanation of how I did it in Mediocre.

A possible implementation

I started with creating an internal class in the Board-class called PieceList which looks something like this:
public class PieceList
{
public int[] pieces; // Indexes on the board
public int count; // Total number the piece type

public PieceList()
{
this.pieces = new int[10];
this.count = 0;
}

// Various methods explained below
}
Since the Board-object is only initialized once at the startup of the program we do not have to worry about extra time for initializing these piece lists.

There can only be a total of 10 pieces of a certain type (two original and eight promotions), so that is how big the arrays have to be. Of course for pawns and king we can only have eight and one, but that is of minor importance.

We can now give the Board-class a list for every type of piece on the board.
public PieceList w_pawns;
public PieceList b_pawns;
public PieceList w_knights;
public PieceList b_knights;
public PieceList w_bishops;
public PieceList b_bishops;
public PieceList w_rooks;
public PieceList b_rooks;
public PieceList w_queens;
public PieceList b_queens;
public PieceList w_king;
public PieceList b_king;

Keeping the pieces unique

Many engines uses objects for keeping track of the pieces of the board, so one object is pawn(1) which keeps tracks of that pawn's index. When moving a pawn we automatically know which of the eight pawns it is and can update the object accordingly.

I went for a slightly different approach however.

I added another 128 slot array to the Board-class called boardArrayUnique, that instead of keeping track of what type of piece is on the particular index (square), keeps track of what index the piece on the square has in its corresponding piece list array.

In the position to the left there would be two 128 slot arrays, boardArray containing the piece types of the each square and boardArrayUnique containing information of what index the pieces can be found on in the piece list arrays.

The two arrays would look something like this (I left out the 'dummy' board for simplicity, there are however 8 extra zeros and -1:s to the right of each row, also the board is actually flipped, but this is just for illustration):
boardArray
0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0
0 -6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 6 0 0 0 0 0 0
6 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

boardArrayUnique
-1 -1 -1 -1 -1 -1 -1 0
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0
As explained a long time ago the boardArray keeps the piece types where -6 is black pawn, -1 black king and so on. Now the boardArrayUnique keeps the indexes in the corresponding lists (-1 being no piece on the square, hence no valid index, this actually helps catching faulty indexes since it would attempt to reach the -1:st slot which produces an error).

The lists would now look like this:
w_pawns
pieces: {16,33,0,0,0,0,0,0,0,0}
count: 2

w_king
pieces: {7,0,0,0,0,0,0,0,0,0}
count: 1

b_king
pieces: {119,0,0,0,0,0,0,0,0,0}
count: 1

b_pawns
pieces: {81,0,0,0,0,0,0,0,0,0}
count: 1

// The rest of the lists (w_knights, b_queens etc.)
// have count 0 and empty arrays
So if we wanted to move the white pawn on B3 we would check in the boardArrayUnique where that pawn was located in the w_pawns array and get index '1'.

Every time a piece moves we update both the boardArray with the piece type, the boardArrayUnique with the list index, and the piece list with the new square.

Maintaining the lists

There are three places where we have to worry about updating the piece lists:
  • makeMove()
  • unmakeMove()
  • inputFEN()
Things like generating moves and evaluating piece positions etc. merely uses the lists, they do not have to worry about updating them.

There are three methods that will be used at different times when setting up the board, and making and unmaking moves.
  • removePiece(boardIndex) - Removes a piece from the piece list and updates the boardArrayUnique accordingly. If we remove a piece from index 0 we move the piece on the last index to this place so we do not get any holes in the array.
  • addPiece(boardIndex) - Adds a new piece to the end of the array and updates the boardArrayUnique. This is done both when setting up the board but also for promotions and unmaking captures.
  • updateIndex(from,to) - Updates the boardArrayUnique so the correct index points to the correct list. It also catches captures and removes the captured piece from the right list.
There is actually not much to it. We just have to remember updating the lists in a correct way whenever something changes on the board. Promoting a pawn would include something like this:
w_pawns.updateIndex(fromIndex,toIndex);
w_pawns.removePiece(toIndex);
w_queens.addPiece(toIndex);
Along with the usual changes to the boardArray, history and zobrist keys of course.

Using the lists

Now we can reap the benefits of this very convenient (and time-saving) feature.

For example in the new evaluation there is a method that evaluates the positions of the white pawns. To get the positions of the pawns all we have to do is loop like this:
for(int i = 0; i < board.w_pawns.count; i++)
{
index = board.w_pawns.pieces[i];
// etc.
}
Compare this to the old way:
for(int i = 0; i < 120; i++)
{
if(board.boardArray[i] == W_PAWN)
index = board.boardArray[i];
// etc.
}
It should be quite obvious there is some serious time to gain, as well as less complexity in the code.

The kings

As you might have noticed the Board-class creates a 'list' of the white and black kings. This is of course quite silly since there will never be more than one of each so we could just as well just have an integer with the index. However to keep the make and unmake methods a bit less complex I decided to do it this way, there is no noticeable speed loss by doing this.

In conclusion

I have no definite number of how much this speeded up Mediocre since I did the change parallell to some other things, but I have a feeling it was with quite a bit. And even with zero gain in speed it would still be very much worth it since the evaluation code has become a ton simpler to write.

On to the guide for the new move generation code.