Motivated by a recentish chess-related question (http://www.allegro.cc/forums/thread/600698), I returned to chess programming. I found that it was probably better to rewrite almost the entire thing from scratch (move generator, search, evaluation) and after more than a month of tinkering with it, things seem to be coming along fairly well.

{"name":"599212","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/8\/a8506c1a6d60f6dd39a8145e69853386.png","w":893,"h":665,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/8\/a8506c1a6d60f6dd39a8145e69853386"}

All rules are implemented (obviously) although I disabled repetition checks and left out the 50-move rule (the first are actually important if for no other reason than to kick the program out of searching cycles) for the time being.
The program reaches a somewhat decent 7-8 ply search depth fairly easily, but the evaluation function mostly only looks at material, which is not really good enough. The program will also mess up its opening quite badly, but I haven't really invested any time into that department yet.
That said, if I give it a decent starting position I find that it can already give me a hard time, so I fully expect the program to be able to beat me consistently if I put some more effort into it.

The (Allegro 5 based) graphical interface is very elementary at the moment: you can make a move (not underpromotions though), tell the computer to play a move or load a position from disk. No time control, difficulty settings or other options. I'll be adding those eventually, and I'll make a text-based interface and a UCI/xboard interface (standard protocols for chess engines, so they can be used with other interfaces) too. Eventually.

If the Allegro interface is a bit more polished and the program doesn't make a complete mess of the opening anymore, I'll put it on the depot (along with some information on how the program works and what decisions I made in its design and why).

Sounds neat. I'd find it much more interesting if you don't use an opening move database but if your goal is making a strong competitor, that's sadly how it's usually done.

Oh, I do plan to give it enough rudimentary opening knowledge that it will at least be able to place its pieces half-way decently on its own before adding an opening book.
Right now (at 5s per move), it calculates the first position to 8 ply and plays 1. f2-f3... (however, previous preferred 1. e2-e4 or 1. d2-d4, so it should be able to do better with a little tweaking).

f2-f3 is probably the worst first move one can make... Couldn't the position evaluation also take into account how many moves are available / how many squares are under fire (f2-f3 not only doesn't open up any important diagonals and weakens the king's position, it also blocks a useful move for your own knight).

It should probably just choose the first move at random (but not f2-f3, except in handicapped mode).

Hey, it has some merit: it attacks e4 and it moves your weakest pawn^[1] to a saver square!

No, seriously, it's pretty atrocious, for pretty much the reasons you mentioned.
It's said that letting a computer play an opening on its own (no opening book) is the ultimate proof that computers can't "really" play chess. They're unbeatable in tactical positions though.

It should either have a decent-ish evaluation for opening positions (centre control, develop pieces, castle king are all good), or it needs to draw moves from an opening book. Otherwise you end up with silly things like 1. Nh3 or 1. h4. Many moves are bad, although e4 d4 Nf3 Nc3 c4 f5 g3 h3 b3 b4 a3 are all playable, which is slightly more than half (a3 obviously isn't that great, but it's surprisingly enough not completely horrible either because a6 is a semi-useful move in many black defences, which means you get to play a black defence as white, so you have a tempo more).

I'll work on that in due course; I'm trying to get it to perform decently in test positions first. It needs a better mate determination; right now it will sometimes find a deep mate and discard it until it reaches a deeper overall search depth, at which point it sometimes no longer sees the mate because the line that lead to it has been overwritten in the transposition table, so it can't look as deep. I'll fix that, then improve the evaluation function so it is more aware of piece placement, mobility and (very important) king safety (that will also help detect mate threats). I'll probably have a look at the openings after that.

That said, I just fixed a stupid mistake in my search implementation (it was trying to give accurate scores to all moves, which is stupid: you only need an accurate score for the best move, for the others you only need to know that they're worse) and now the search is about three times faster. Yay!

I would not mind to try your chess program, I used to play a lot of chess. At one point planned on writing a chess engine for practice programming. ( never materialized ...) Did you include promotion and en passant in the rules ?

Ok. That reminds me: at the moment it probably only compiles on OS X... although that shouldn't be hard to fix.

It's a fun project to undertake, but it's not an easy task. Bugs can be very subtle and hard to find, and it's not so easy to make the program fast (read: strong).

Of course. Though as I said, you cannot specify an under promotion at the moment (the program will play them, but if you play a promotion the move will be matched to a queen promotion). This is more of an interface limitation though, the engine will play them if applicable. I should really fix repetition detection though; the 50-move rule is less important.

It would be really nice to be able to try it under Linux, but Windows will do too...

Yes chess programming is pretty complex when it gets to making it the engine strong enough to play masters. I wonder if computers in my lifetime will be ever so fast as to actually brute force mate from an early position...

Linux is probably easier for me to get to work than Windows.

I doubt it, to be honest... the size of the search tree is just too prohibitive.

Anyway, things are progressing nicely. I took a break from running it against test positions and played an actual game yesterday. I'm not entirely unhappy with how it played the game in the end, but there are quite a few oddities that need to be worked out (I was white):

This is still without an opening book of any kind, so it's quite interesting that the first 10 or so moves are quite decent (3. ... f5 is a bit odd though). 12. ... Kf8 is of course a horrible move, but it should be very obvious from how the game progressed that the program has no notion of "king safety" (and that it desperately needs such a concept). Personally (without analysing the game in detail) I thought black was slightly better until around move 20 or so, at which point the scales tipped. By the time I got to play 24. Rc8+ I felt fairly certain I would be able to win.

EDIT: fixed a few typos I made in transcribing the game above, attached PGN file of the game for easy viewing.

It does not play correctly here for me, it plays some of the white's moves on the black side, anyhow it looks like black gets to make two moves after Bb4...Kf8 ?

Using glchess.

I wonder if you could program a pixel/vertex program to work as a move generator? Anyway, I really enjoy the subject of <game>-playing computer programs (I don't enjoy chess much though). I would love to try it out at some point (and I have a mac).

I found another typo: white's 7th move should be 7.Ngf3. I used the PGN viewer from http://members.shaw.ca/lapides/pgnedit/pgnedit.html to test it (the software I have installed on my machine plays the moves very slowly for some reason; it also didn't catch the error in the recording of white's 7th move).

I should really add exporting games to PGN before I do anything else... been on the list for a while and it will make these things much easier.

EDIT:
Double checked, with the corrected 7th move for white, the game plays correctly for me in the online viewer linked to above.

I'm not sure what's causing that... but try after correcting white's 7th move.

Consensus seems to be that you can't use a graphics card to speed up chess programs very much, the reason being that graphics card tend to be good at parallel floating point operations and chess engines mostly needing bitwise integer manipulations. Even if you could, move generation is fairly quick and easy to do; it shouldn't be the thing that determines the speed of the chess engine.

I'll try to get the source in a shape where it will compile for other people on the weekend. It'll need a recent version of Allegro 4.9 (but not SVN at the moment, though I may change that before then).

EDIT2: Uploaded a slightly changed version of the previous game: I replaced the horrible move Kf8 by a more reasonable development move and let the program play the game normally again from there onwards. The final position has black up by two pawns but in an ending of opposite bishops that I hope is somewhat drawn. Certainly my program doesn't know how to play the ending if it isn't though.

Ok, i looked at the game and the moves seem pretty decent, does your engine focus on mate and / or material at this point ?

It'll only evaluate material (well, not entirely - it has some other terms in there, but it's all very crude and rudimentary at the moment), but it will of course flag a checkmate as a win and it has some code to help find mates more quickly.
The occasional strategic blunder aside, it plays very decently. Hopefully I'll be able to turn this into a reasonably strong program eventually.
Right now, I'm testing it against a set of tactical test positions. It scored 247/300 last night, it's well on its way to score 251+/300 at the moment.

I'll focus on making the code ready for a release this weekend before trying to make it stronger though.

Are you hardcoding decisions or you got a rules database? While you should not focus on the opening, maybe you should start after the opening movements (setup the initial board with a finished opening) and see how it goes.

The program uses a set of heuristics to score a position: doubled pawns are bad, passed pawns are good, rooks are stronger on open files than on closed files, a knight is usually better placed near the centre than near the edge of the board, etc. These get translated into a number and summed (so the evaluation function is a linear function of the game features it knows about) along with the material balance. Picking the relative weights is what determines how good an evaluation function is; however, the evaluation function alone isn't enough: you need to add a search function as well to find the line of play that leads to the best position.

The sad thing about the game I posted above is actually that the program played the opening better than I did...

Cool! What license are you releasing the code under?

I'm making a mechanical chess board that allows you to play people online. I'm looking into making chess-bots so that the online community can be started.

http://www.chessghost.com/sand/

Good question. I hadn't really thought about that yet.
For now, it's under something I just cooked up. When it gets to the stage where I want to release it "properly" I'll probably get a proper licence for it.

Cool! When I was younger I always wanted a chess board that I could connect to my computer. I still don't like staring at a diagram on the computer screen; however, the expected lifetime of a chess set is much larger than that of a computer, so I now feel that a chess board that I can hook up to a computer is likely to be outdated quickly...

Feel free to have a look at my source code, although there are probably other resources available to look at that are easier to get into. Two design elements of my code factor into this: I make heavy use of static inline functions in header files in an attempt to speed up the code (probably not as important as I thought when I first wrote it because the search algorithm is much more important; still my program was clearly faster than my previous attempt had been when I just got it working, it's a lot faster now) and I use "bitboards", 64 bit integers that represent one piece of information about the board (location of kings, white pieces, black pieces, etc.), which are very powerful but not that easy to wrap your head around if you're not used to them. A plain char array is better for that, and there are many open source programs that use those.

Anyway, all of that said: source attached for anyone who is interested!
No binary I'm afraid - I tried making an application bundle for OS X at least, but I couldn't figure out how to put Allegro's dylib's inside the bundle (and I couldn't static link for boring reasons having to do with being unable to compile all of Allegro in 64 bits and therefore being unable to install the static version of Allegro). I didn't have time to try the code at all in Linux, but it should probably work. I have no idea about Windows. MinGW will probably work after modifying the Makefile, MSVC will probably not work.

EDIT:
Added a new screenshot, highlighting something I'm quite happy with: my program finding Bxf7+ in less than one second (it used to take ~15 seconds not too long ago).

{"name":"599241","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/a\/1a2d4f3cff771ed39355692ae0399594.png","w":532,"h":514,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/a\/1a2d4f3cff771ed39355692ae0399594"}

Chess programming is really an interesting thing. I'll give it a go one day.

I don't get it, how is that a good move?

See the main variation printed at the bottom of the "Iterations" window.
After 1. ... Kxf7 2. Ne6 Black's queen has nowhere to go. The only alternative is 2. ... Kxe6, which leads to a forced mate after 3. Qd5+ Kf5 4. g4+ (which is why the program opts for 2. ... dxe6 3. Qxd8 instead).
Neither of the alternatives 1. ... Rxf7 and 1. ... Kh8 do anything to prevent 2. Ne6 either, of course.

It's probably just me and my lack of memory, but I like chess boards to have the letters/numbers next to them so I don't have to work out where pieces are moving in relation to the move history

Hmm... good point, I didn't realise I hadn't put those in! Easy to add though.

I'm going to try it when I get home tonight.

Amazing!
I was able to speed the program up by some 20-30% by just refactoring code in various parts of the move generator and board update code. Remember how barnches are expensive and chars are slower than ints? Well, they're faster than unconditionally calculating things you don't have to while relying on the compiler to pair instructions to eliminate any overhead (and we're not talking expensive calculations here, we're talking bitshifts and logical ors):

is a whopping 20% faster than

static inline uint8_t get_piece(const board_t *board, const int where)
{
   assert(where<=H8);
   assert(board);
   int n;
   int piece = 0;
   for (n=0; n<6; n++)
      piece |= ((board->bbp[n]>>where)&1)<<n;
   piece |= ((board->bbc[1]>>where)&1)<<7;

   return piece;
}

Maybe I shouldn't be surprised, but 20% is a lot more than I was expecting to get (yes, that piece of code gets run all the time).

Anyway, I'm happy. Test suite score has increased to 275/300.

Have you compiled with loop unroll ( -funloop-rolls for gcc) to test the loop speed?

Hi Evert, congrats on a working chess program! If it gets UCI interface (or WB), it will be able to enter tournaments. There it can get a rating and match versus some real competition.

Good luck making it stronger, I know it's a lot of fun!

My ongoing tournament: KCEC

A couple of quick notes on compilation in Linux. My glibc doesn't include qsort_r() yet so I had to nick one off the web (attached). depend.sh expects echo '\t' to print a tab. This is non-standard, but you should be able to use $'\t' which is a POSIX shell feature.

When I told the computer to make the first move, it crashed. I can't reproduce it now though (maybe I'll run it through valgrind later). You should handle display expose events. Other than that, it seems to work. Unfortunately I don't know anything about chess.

Hmm, I have fairly aggressive optimisations switched on (those make a difference too!), specifically "-fast" which enables "-O3 -fomit-frame-pointer -fstrict-aliasing -momit-leaf-frame-pointer -fno-tree-pre -falign-loops" but not loop unrolling (I thought it did!), I'll test that.

Thank you! It's actually my third (fourth if you count my Chinese chess one).

I have UCI planned (it looks slightly easier to do). It'll be interesting to see how it fares against other programs. It does decently well on some benchmarks, but not so well (yet!) on others...

Damn frustrating too! The immediate effect of a lot of improvements I put in is a decrease in tactical strength/speed. Usually that means there is a subtle bug somewhere that is tricky to find.
For instance, I had a problem where in certain positions, the search would take a very long time. This turned out to be an interaction between the check extension (look deeper in lines with checks, with some restrictions) and the recapture extension (look deeper in lines with recaptures, again with some restrictions), which generated long sequences of pointless checks and silly exchanges. Fixing that is what gave my Bxf7 in the above example (current build finds it in 0.45s but doesn't see that it wins a queen until 0.61s).

Cool! I'll be very interested to see how my program does. Though if Crafty is down in 31st place I can't hope for much, I tink...

Heh, oops! Sorry about that; I have one ready in src/misc/ (probably the same one you found) but didn't get round to using that. Mostly because OS X (and BSD?) libc have it already.

Ah! Good to know. I should actually just replace it with a Perl script I wrote for another project and that works much better (the bash script is hacked together based on Allegro's old depend.sh script from several years ago).

Hmm...

Ok. That could be helpful!

Oh, right! I forget, since they're not needed on OS X...

You have a golden opportunity to learn.

EDIT:
I tried adding -funroll-loops; the difference is within the error bar but it seems slightly slower with -funroll-loops enabled (in the current code, I didn't try with the old version of get_piece()).

EDIT2:
Ok, did that experiment too. With the for loop instead of the if statements, the version with -funroll-loops is 10% faster than the version compiled without that flag. The if statements are 20% faster, so it's closer but still not enough...

The content of the loop itself are more complex than the if statements, so it is expected to be slower.

A profile run would tell you if you can optimize simple functions too. Also, many programs cache results to prevent having to review movements again.

Results on test suits unfortunately don't correlate very well with the ratings, playing real engine-engine games is more reliable way to track the progress. So actually implementing the UCI interface will be very useful for your development too, as it will allow you to run test matches.

Yes balancing search speed versus evaluation accuracy is a challenge! Test suits are good for a quick check that you haven't broken anything, but test matches are really more sound way to test the changes. Some authors run matches between different builds of their program, some use other engines as opponents. I prefer the latter way, as testing against itself may hide some weaknesses that your engine can't exploit but others will. Variety of at least 10 or 20 different opponents is much better. And anyway in the tournaments you'll face other engines so why not test against them during the development too.

My list is missing a few recent strong engines, so in fact it's even tougher than it looks. But if you don't set unrealistic goals, like getting in top 50 from the start, then you'll be OK.

Yes, but they avoid a branch. Anyway, no matter, things are fine now the way they are.

It would, if gprof would give me sensible output on my MacBook, but it doesn't. I have no idea why, but gprof seems to be broken on OS X.

Oh, that is absolutely essential to have. The speed of my program increased by more than an order of magnitude when I first added it (which was the second thing or so that I did).
This is particularly important because chess programs tend to use "iterative deepening": you search a position to 2 ply before doing a 3 ply search before doing a 4 ply search... etc. The idea is that a low-ply search is relatively fast and you can use the extra information to speed up the deeper search.
Without a transposition table, I don't think this would work at all.

EDIT

True. There's also another more subtle danger: before I was testing a small number of test positions and optimising my program so it could solve them quickly. However, it actually performed worse on other positions than before: I had been tuning it to solve one particular set of problems very efficiently.
Most test positions will only measure tactical ability and possibly the evaluation function. It's important to get those right, but it isn't the whole story, because in most chess positions you have to play strategically rather than tactically.
I had a very beautiful test game against my program that showed this a couple of days ago (unfortunately I accidentally deleted it). The program was playing sound moves tactically, but putting its pieces in bad squares (it had two bad bishops at one point) and keeping its king near the centre. All I had to do was develop my pieces and wait for the right moment to sacrifice a knight to draw its king out in the open. It avoided being mated, but by then its position was so horrible it was always going to lose (a lot of) material and it was an easy win after that.

Still, that's fine. I see getting it to play tactically well as a first step into making it play generally ok.

I know. They take a while to run though...

True; again, it takes time though.
The choice of engine is also important: the opponents must be of comparable strength or slightly better. I don't think I'd learn much from pitting my poor program against the likes of Fruit, Glaurung, Rybka or Crafty!
Are there any engines you'd recommend as test opponents?

-O3 BAD! VERY BAD!

Expect odd unrepeatable errors with -O3. It is explicitly marked dangerous and may actually generate bad/wrong code.

I've used -O3 in programs doing heavy floating point calculations and have the resulting code produce absolute garbage as a result. I'm well aware of the dangers of using -O3.
The proof of the pudding is in the eating though, as they say. So far everything works perfectly fine. The only case so far where I was having problems when using -O3 (instead of -O2) those problems were actually due to passing the wrong size to calloc(), thus allocating insufficient memory to hold an entire array. After fixing that, things were fine.

Very nice looking project! I will try to compile it sometime soon. I'm intrigued by chess programming, but I will probably start out with something simpler, such as Othello. As you say, the bitboards will be a tough nut to crack, especially since I'm not that well versed even with simple bit operations.

Just making sure. It could still be producing broken code though, just that it doesn't always matter much. Like very hard to find crashes (see prior messages), or making odd choices (ones you didn't expect it to make)...

I find its better on my sanity to use -O2 and hand select extra opt flags instead of wonder if -O3 is silently trying to drive me insane.

You could, though I'm not sure it's actually that much easier to program (maybe, I haven't given it much though). Draughts might be even simpler.
Even a tic-tac-toe program can be solved using the same approach as a chess program. It's overkill, but it would work - and teach you the basics of the search algorithm.

You don't need to use bitboards - plain char arrays are perfectly fine. In fact, some people will tell you that plain char arrays are better and produce faster code... then again, other people will tell you bitboards are what it's at.
It seems that you can do whatever works best for you. Writing the search and evaluation properly is more important than your particular choice of board representation.

It's pretty much impossible to work out why the code thinks some moves are good or bad anyway, there's simply too much happening at once. But don't worry, when I see something funky turn up, the first thing I do is switch off optimisations.

I need to start working on an AI for my Sos game. The problem is it can use an arbitrarily sized board, and theres only a few rules:

• Use an S or an O on any open square

• Make an SOS in any direction (horizontal, vertical, or diagonal) and you get a point, and a free turn

It vaguely reminds me of Go, at least with the simple complexity of it all.

I'm sure I could program a really stupid AI for it, but to program anything that approaches GOOD would take intelligence I probably don't have right now.

Not only do you have to pick a good spot, you have to guard against the other player picking an SOS string. Just how deep do you look for strategy? Especially on a 50x50 or 100x100 board?

Go is a notoriously difficult game to write programs for, at least programs that play somewhat decently.
It does sound like something where an alpha-beta type approach and transposition table would be quite useful to have, but the number of possible moves is enormous. Most of these are probably obviously bad or not very good, so you could use some sort of move ordering/depth extensions to help things along. The good thing is that the number of possible moves decreases as the game advances.

I'd start with something relatively simple, say a 16x16 board, and then work from there. You can generalise it later.

Thanks for the tips. I'll have a look at alpha-beta and transposition tables

For a game like that (SOS, which I've heard called Oxo in the past), wouldn't it be sufficient to treat the game board as though its size was maybe two or three spaces larger in each dimension than the smallest board that would contain the current state? The board size would get bigger as the game progressed, but with a game like that I don't think the possible moves would increase dramatically.

This thread made me take up chess again (as well as go for the first time) so thank you.

That would be Tic-Tac-Toe wouldn't it?

Tic-Tac-Toe is just Ooo. Or Xxx, for the mature version.

add: Oh, according to Wikipedia OXO was the name of "the first graphical computer game, a version of Tic-tac-toe". I'm talking about the Oxo described here, which sounds like what you're doing, with X's instead of S's.

Yes tactical strength is the start. Also, at the larger search depths the difference between "tactical" and "strategical" is getting blurred. Some moves that we think are bad strategically are also bad tactically when you search deep enough. Famous example is Rybka - when it first appeared in the end of 2005 it was 1. Very strong 2. Showing rather low node-counts. So most of people concluded that it was slow and had very accurate evaluation. Later it turned out that Rybka in fact is a crazily fast searcher with relatively primitive evaluation. It was manipulating the node-count to make it look slow. Still from the games you could not tell the difference easily.

Do you score piece mobility? Like, scoring higher when there are many squares a piece can go, and lower if there are few? This may already help with the bad bishops.

Yes it takes lot of time, but it is necessary if your goal is high. As your program gets stronger, it will be more and more difficult to find an improvement. Most of time will be spent tuning parameters and testing the difference. And the difference will typically be very small. So small that it will need many thousands of games to detect with significance. Accumulating these small differences you'll still be able to progress, but strong testing strategy is essential for this.

Famous examples are Crafty, and again Rybka. Both use clusters to run automated test matches day and night.

You'd be surprised to know how many engine authors don't get this simple idea. Many test their engine agains itself, many choose opponents that are too weak or too strong. The good choice is opponents of comparable strength. It's difficult to choose without knowing approximate strength of your engine. There are hundreds of engines to choose from. Some important lists: CCRL 40/4, CCRL 40/40, WBEC, RWBC, UEL.

These two engines are fun because they are open source, and the source is just about 2 KB of C code: Toledo Nanochess, micro-Max. (The latter one is from Netherlands too). These two guys are competing for the smallest C source that can still beat the other one. (Both claim that their engine is stronger). Since your engine is probably more than 2 kb of code, it's worth checking that it can beat these two.

True. I did a quick test (by hand): running my program against TSCP (at a fixed time of 5s per move), which is listed as one of the weaker programs on the pages you linked to (no particular reason, I just happened to have a copy of it because I wanted to have a look at how it retrieves its principle variation).
It has a very simple evaluation function, but it's still much more advanced than mine, which has material and some odd tweaks for material imbalances and pawn structure and that's it. Most of it is supposed to be framework for when I do get around to implementing a better one (I have a long list of things I want and notes on how I want to implement them). It doesn't even have piece square tables, so my program has no notion of where it should sensibly put its pieces. Well, it has them (I copied them from my previous attempt), but they're unused.
Throughout the game, my program outsearched TSCP by 5 or 6 ply (13 or 14 ply in the end game) and fairly often, the main variations agreed for the first four or five moves - so the greater search depth at least partially compensated for the horrible evaluation function.

Both programs played fairly horribly, although TSCP at least put its pieces in semi-sensible locations (it then didn't know what to do with them, of course). I had been hoping that there would be some deep combination that would win material and allow my program to win, but of course that is statistically unlikely if your pieces are badly placed to begin with. Conversely, if your pieces are placed right, there probably is some deep combination somewhere - which my program saw even when TSCP didn't, which meant it gladly gave a pawn to prevent losing a minor piece in some deep combination that was beyond TSCP's horizon. My program then proceeded to trap its bishop on a7 (the classical Bxa7 b6) and entered the end game with two pawns and a knight down. It managed to get down to knight+rook pawn versus king, which you can draw in some situations but you need to know what colour square your king needs to be at (the knight must be able to drive the king out of the corner), which was beyond my programs horizon (maybe not if it had been allowed to search for the full 5 seconds, but it was also limited to 20 ply, which it reached in 0.5 seconds at this stage of the game).
I stopped the game when my program reported the promotion in the main variation.

So, lessons learned: 1. I need a better evaluation function. 2. It can probably still be fairly simple, especially if that means it's also still fast. 3. Search depth alone doesn't mean a thing if your evaluation is really bad (well, I knew that).
I will probably have to adjust how the different extensions and reductions work too, which means the speed of my program is likely to go down. Still, that's ok, as long as it increases in strength as it does so.

Evil!

From what I remember, programs like Fruit and Glaurung also have fairly simple evaluation functions (although they're still much better than mine) and simply "out search" the competition.

Nope. On the list.
Should definitely help with bad bishops, although I also had another idea for that: a bishop is marked "bad" if it is on the flank and its forward advance is blocked by its own pawns. I haven't worked out the details, and I'd need to somehow catch situations like Bd4, Pe5/c5/b4f4, which is also not so great.
Or forget about bad bishops entirely and rely on the concept of colour weakness to handle the situation (although in that case I would still withold the bonus for having the bishop pair if one of the bishops is "bad").

I know. For now, my goal is simply to write the best chess program that I can write. It's a spare-time project, so I have a limited amount of time to spend on it.
But, we'll face that burden once my program gets a little stronger.

Really? It's not really any different from humans playing humans: you don't learn what your weak spots are unless you play against evenly matched opponents. And without knowing that you cannot advance.

For something like Crafty, this is probably fine: the old version is strong enough and tested enough that it isn't likely to have major weaknesses.

Indeed. Well, at least I have a temporary target to beat now.

Yes, it's about 20xthat, but that includes variable names of more than one character.
Those will be my next targets.

Anyway, onwards to play with the evaluation function!
(Weekend, bed now, work tomorrow).

Fun! It will be even more fun when you can let the two programs play automatically, so you can sit back and watch.

Yeah. Historially computer chess was considered as kind of AI application, very complex eval was respected. Though some were successful with very simple eval and fast search (like Fritz 5). It was always a big debate. The turning point happened I think with the emergence of Fruit. It was amazing example of a fast searcher with clean and simple evaluation. Now most people don't think computer chess is about intelligence anymore, but about outsearching the opponent. Fruit's influence on computer chess was enormous. Rybka, Fritz 11, Naum 4, Loop, Onno owe a lot of their strength to Fruit (they don't admit it though), plus countless Fruit derivatives (Toga, Grapefruit, Cyclone, TheMadPrune, etc).

Of course this is mainly about the competition at the top. In the amateur area anything is fine as long as it works. Personally I don't like to see other people's code as it spoils the fun of coming up with my own solutions.

I'd try the general piece mobility first - it is a robust and rightly popular idea. Anything specific to bishop-pawn placements will likely slow you down for too little benefit. (IMHO).

Actually the most common mistake in testing is simply not testing enough. Often people run a couple of 100-game matches, and based on that decide if the improvement is good or bad. If the improvement is worth 10 Elo points, that's invisible in the noise with this number of games. So their progress is forward or backward depending on random chance. And having too strong or too weak opponents of course will increase the number of games necessary for the same error bars. Anyway, we can get back to that later when you have UCI protocol done.

Crafty is being tested against selection of a few opponents (less than 10 IIRC). The opponent selection is very bad, it includes Glaurung and some other much stronger engines. But Bob is able to run millions of games on his cluster, so he can measure very small improvements. The superior testing scheme plays important role in Crafty's steady improvement during the last few years.

Rybka is playing test games with itself, but in this case it's fine because there are simply no other opponents of comparable strength to play with.

Check this out: CPW (also other materials in the wiki).

I would think it happened much earlier than that - when it became clear that a Shannon type B approach (only look at good moves, don't waste time with poor moves) could never beat a type A program (look at all moves). The first would be some sort of artificial intelligence (no human considers all moves in a position) whereas the second approach mainly needs a fast searcher.
The irony (if that is the word) is of course that pretty much all strong modern programs are a bit of a hybrid: they examine all moves, but extend lines that look interesting and reduce lines that seem poor. You then rely on the time you save to give you extra plies that will enable you to research nodes that you thought were poor but are actually good, the idea being that this happens relatively rarely.

I might be wrong, but wasn't Rybka originally a Fruit derivative?
I know there is a lot of debate about whether it still is (in which case it's in violation of the GPL) that I'm not particularly interested in diving into.

There's only so many ways in which you can write an alpha-beta search.
I've mainly looked at other people's source (mainly Crafty and Glaurung) to make sure that I interpreted a particular algorithm correctly. I agree it is more fun to try to do your own thing (and sometimes reinvent the wheel, but if it's Robert Hyatt's wheel you reinvented there's no reason to feel bad about it).

I suspect it will actually score the same thing (more or less). Mobility for knights doesn't depend on pawn structure very much as long as they're somewhere on the middle of the board (depending a bit on whether you count destination squares attacked by enemy pawns in your mobility or not), for rooks the main mobility determinator would be that they're on (semi) open files. So the main mobility term would (generally) come from bishops, I would imagine.
We'll see. I was going to do mobility first anyway because it's easier (doesn't require pattern recognition). The tricky thing will be to do it somewhat fast.

Quite. A difference of ~100 Elo is something you could see though, but when your program is already strong it'll be hard to advance that much.

Already have. Some of the stuff on there I find very useful (my static exchange evaluator is based on the description given there), some of it not so (when it's mainly code and not so much explanation in the article itself). I've also gone over Ed Schroeder's disection of the internal workings of Rebel several times, though I wish he'd written it in Dutch because his English sometimes isn't that good...
Lots of ideas to play with!

Well as you say no strong program looks at all moves to the equal depth anyway. However there was still considerable debate about the relative importance of eval vs search. Fruit's emergence and subsequent improvement of top engines underlined the importance of fast search and fast evaluation, even in the context of already highly selective search strategies.

People could be sued for saying something like this openly without hard proof, so let's just say that I believe that Fruit's influence on Rybka is more than is acknowledged. Note that this applies to a number of other commercial engines too, just Rybka receives the most attention.

Yes there was a lot of debate in computer chess circles about it, and you are probably right to avoid getting into it.

I am happy with whatever works for you!

BTW, engine names shown in orange color in KCEC or CCRL lists are all open source.

Ok, I seem to have a working UCI interface - at least working well enough that I can play a game and everything seems to work more or less as it should. It doesn't do fixed-time-per-move yet and I'm sure there are other options I've missed, but the bottom line is: it's able to play a game through UCI.

I'll hopefully finish that up over the weekend and then get to work on the evaluation a bit more.

Cool! Please post any match results!

If you make a simple web-page with short description and download link, you can announce the engine and enter tournaments.

So far, I've been running a series of mini-matches against both micro-max and TSCP. The number of games is smallish, but results are fairly consistent: my program (current version, not the version I attached earlier) should be about 300-400 elo stronger than either of those two programs. However, test results are only ~150-200 elo stronger. There appear to be two problems.

One is with picking the fastest mate. The program should always pick the fastest mate (so it prefers a mate-in-two to a mate-in-three), but sometimes this doesn't seem to work properly. I suspect a problem with the transposition table, where the score for a position that was previously scored as "mate-in-N" has been lost, but the program finds the previous position, which was scored as a "mate-in-N+1" and decides that it will win from that position - and go back. Again, there's code in place that should prevent that, which usually works... something to look into, evidently.
The other is with three-fold repeat detection: the program sometimes goes into a repetition, even if it's ahead and it will get a draw instead of a win. This is where it loses most of its score in the test matches. I again suspect the transposition table: the code looks at the current position, checks if it's a repetition, if not it looks in the transposition table and then blindly executes that move and returns the score - without checking if that leads to a repetition.

Some interesting things I found:

1. In one of the test games (I'll have to look it up) my program was playing a rook ending (one rook each) with a free pawn and it correctly went for the Lucena position, building a bridge with its rook on the fifth rank. What's cool about this is that it doesn't know about rook endings at all, which means that it found the win through the normal search.

2. My program will score two connected pawns on the sixt row as stronger than a rook. I may need to temper this a bit depending on the opponent's material because I have the impression it sacrifices material a little bit too readily to reach this situation. It can be a real killer in some situations though, where it's fun to see!

3. My program seems to end up a lot with the situation where it has knights against bishops. I like to think it "plays well" with knights as a result, but I suspect something else entirely is going on: following Kaufman's analysis of material imbalances I award a bonus for knights in positions with a lot of pawns. The result is probably that my program prefers knights to bishops early on in the game and will more readily exchange one or both of its own bishops for knights (especially if it can also win a pawn or break up the enemy bishop pair). This isn't that great in the end game, however...

So, work to do, apart from isolating those bugs (which will be annoying, because they only seem to show up in the test matches so far). I'll probably also replace Kaufman's evaluation stuff by something else. I already took out his rook evaluation things (rooks are worth more in positions with fewer pawns) because that condition didn't make any sense to me and gave some funny results. Rooks are worth more on open or semi-open files, where they have greater mobility - which usually happens later in the game when there are fewer pawns on the board. The fact that there are fewer pawns by itself doesn't make rooks more powerful. It should be similar for knights: they're not as strong in the end game if there are pawns on both wings.

Damn! My program just dominated micro-max' queen with three minors (knight and bishop pair) and then slipped into a threefold repetition again!

Working on it.
I also have to iron out some details for the UCI protocol. Right now, I can only change the time settings by hand in the code, so I have to make sure that what the UI thinks the time controls are matches what my program thinks they are - or it would be unfair.

Great results for such a short development time! It looks like your program is about 2100 or 2200 points on KCEC or CCRL scale. If you like to test against stronger programs, just pick any entry with similar rating from the lists. For example, I would try Gk 0.90 64-bit.

It's a common problem. I know a number of engines that have troubles checkmating, including some rather strong ones (e.g., Smarthink 0.17a). In extreme cases they fail to win a KQQK endgame, which ends by 50 moves rule. I think it's not a too much serious problem, though of course it's best to fix it.

This is more serious - it may cost your engine many points, especially against weaker engines.

Interesting.. By the way, are you planning to employ any endgame tablebases?

Yes a pawns race is often fun to watch!

Yes, bishops are usually preferable in the endgame. (Except when you have an 'a' or 'h' pawn and a wrong color bishop, do you detect this?) Are you detecting game phases? People often adjust bonuses depending on game phase.

Yes, support for changing time control is very important, or with wrong clock your program will either move too fast or lose on time. By the way it's also good if you'll test your program with very fast time control, like 1 min/game. Time losses are very annoying, and often happen in my tournament.

Did you already choose a name for your engine?

I'll do that - once I get these bugs fixed...
Remember, it's not my first try at a chess program.

Preferring a distant mate over a quick mate is a problem I've wrestled with in the past, but this is very different and confusing. Right now, I seem to have "fixed" the situation by clearing the transposition table if the current position is a repetition and scored as a mate. I could do a mate verification search, but that could be very costly if the mate is very deep.

Yes. It's a rather nasty problem though: it doesn't show up anymore when I run it through its own GUI, so the bug has something to do with the way the UCI protocol interacts with the way the engine works internally.
By now I've fixed half a dozen things that could have caused that problem and it's still there. The repetition table seems to be updated correctly now, so the problem is elsewhere...

EDIT: fixed it! At least, the engine now properly wins a game where it entered a pointless repetition before. It was quite nasty: there was a bug in the UCI protocol code (the repetition table wasn't reset) which I fixed, but in the mean time I'd changed the logic in the search code in an attempt to fix the problem - but that code had a bug too and produced the same problem on its own. Argh!
I also fixed a nasty bug where an en-passant capture would not be recognised as a valid out-of-check move.
By now, my program has solved every single test position in the "Win at Chess" test set in under 10s at some point or another, but never all of them at once! Improve something so position X is solved in 10s and now position Y is not found. Overall, the trend has been to better test results though (currently 290/300) so I can't complain too much.

Not yet. I might at some point, if they're worth it. My understanding is that they don't actually add that much in terms of playing strength (although it does help, obviously). KRKRP might be interesting though.

Not yet; the situation arises quite often (although my program usually isn't the one with the bishop) so I probably should put it in. I'm not sure at what point to include it though: obviously if it's king+bishop+wrong rook pawn against a lone king and obviously not when there are still rooks or too many other pawns in play. I'd like to score such positions as draw-ish though, so the program knows its position is not as good as raw material would suggest.
Which reminds me: it should score lone kings or king+minor vs. lone king as draws too.

Sortof. I have some detection for the opening and the middle game and then there are some terms that become more important when there is fewer material on the board and some bonuses that are only given when there are only pawns left.
It's apparently important to make sure that the evaluation function changes relatively smoothly, and having a hard cut at some point could hurt the way the program plays. I know others use some sort of interpolation between a middle-game and an end-game evaluation function.

Will do. I have a basic framework in place for doing time management. It still only does a fixed time per move at the moment, but I'm working on it.

It's called "Jazz" at the moment. My previous attempt was called "Isildur", which I also still like as a name (in which case this would be Isildur 2.0). Or I might combine the two into "Islidur Jazz". Or think of something else entirely.

For now, Jazz will do.

I'll try to manage another code upload next weekend (as well as a more Linux-friendly version; I have no idea if things would compile on Windows though).

For names try: Anarion, Aratan, Ciryon, Elendur, or Valandil (being sons, or the younger brother of Isildur).

Hmm... those are neat too! I could write a series of chess programs that descend down the line of Tolkien's house of Elendil. It'd take me a while to get to Aragorn.

Anyway, latest test results are in: my program scores 90% against micro-Max. It needs two or three things to score 100%, I think: a better notion of king safety (it left the king vulnerable to attacks in two games, one lost and one drawn as a result), a better evaluation of material imbalances (two pawns for a minor is not a good deal if the opponent still has many pieces, even if you have three connected free pawns) and it needs to push free pawns a little more aggressively. And I need to make the program not end up with knights in the end game, because it just makes it more difficult to win (one game drawn because of that).

Do as apple does, and name each new version something different

Jazz is a much better name because it can actually be pronounced by somebody other than a Tolkien nerd.

I'd comment on the game itself, but it won't compile on MSVC without a major facelift and regardless, as I don't have the patience to play chess, I am horrible at it.

It also vaguely sounds like "Chess" - which now reminds me that another member of my old chess club once called his chess program "Jas", the Dutch word for "coat" which has a similar pronunciation to "jazz". That association must have stuck!

I'm not surprised.
It might be worthwhile to do at some point, especially since MinGW doesn't do 64 bit binaries as I recall. On the other hand, I don't know how wide-spread 64 bit Windows is these days...

There are engines out there that play variations like suicide chess or atomic chess. You might have more fun with those.

Anyway, I've upgraded my setup to play matches against gnuchess. As I suspected, I need to do a better job at king safety and material imbalances. Some end game knowledge wouldn't hurt either. It scores about 30%, which is consistent (rating-wise) to scoring 90% against micro-max.

Hey Evert, I hear you have some working source to compile, where is it ?

Attached here, but he may have uploaded a newer one later.

Nope, that's the latest uploaded source. I should post the updated source soonish too.

It gave me this after hacking your Makefile:

obj//a5jazz.o: In function `spawn_async_file_dialog':
a5jazz.c:(.text+0x9a9): undefined reference to `al_create_user_event_source'

...I guess I need an earlier version of a5 ? I have 4.9.13 now only.

No, you probably need a more recent version (ie, svn). It's a bit odd, since I though I had everything set up so it would compile with either version, but maybe not. I didn't test that very extensively since I didn't feel like reinstalling 4.9.13 after I updated.

If this is Linux, you'll want to add qsort.o to the list of object files, or you'll miss the qsort_r() function.
Yes, I should automate that by using a better build system than a static Makefile. It's on my (long) list...

al_create_user_event_source() has recently been replaced with al_init_user_event_source().

It should pick up al_create_user_event_source() if you're using 4.9.13:

#if ALLEGRO_WIP_VERSION < 14
   data->event_source = al_create_user_event_source();
#else
   al_init_user_event_source(&data->event_source);
#endif

Now I'm getting these...after installing SVN

a5jazz.c:(.text+0x265e): undefined reference to `al_get_mouse'
a5jazz.c:(.text+0x2670): undefined reference to `al_get_keyboard'
collect2: ld returned 1 exit status
make: *** [a5jazz] Error 1

also why do you have -g with -O3 ?
and OBJDIR=obj/ should be OBJDIR=obj maybe ?

Ah, right. Yes. Ok, those were removed after I uploaded the above source. Check the README file, it should list the exact revision number that I used at the time.

So I get function and variable names in gdb when something causes a segfault or accesses out-of-bounds memory.
It's perfectly fine to use -g in combination with optimisations.

Doesn't matter one way or the other.

Ok I understand, bummer, I have a fresher revision...

The whole thing is pretty funny, gotta love WIP... no compromise...

I think I'll try to fix the source, if it does not take more then 5 min...otherwise i'll wait for the mercy of the creator

Edit:
...gave up and bailed out

It's a good point, actually: I didn't update my installed version of Allegro yet either, I should do that before I upload the new source for my chess program (although strictly speaking you don't need Allegro in order to use it...)

Ye i gather that, i tried the test progs and it worked fine, in the meanwhile i fixed the source too so it compiled, i'm trying it now...

The chessboard is flickering a lot, is that normal ?

Edit:

Ok besides the maddening flickering it seems to be working right, I'll try to fix that later...But it looks and seems very nice so far, I'll be playing with it...Thanks Evert !

Only if a person understands that the code will be changed quite a bit, so you shouldn't expect to have a 1:1 relationship from the path gdb takes, and what you have written in your source.

I'm sure Evert does though

It doesn't on my machine... but it might be, depending on your system setup. I'm told I should process expose events, which the version I posted here doesn't do but the current version supposedly does. I say supposedly, since expose events are never generated on OS X, so I haven't been able to test.
That's assuming that that is indeed the problem...

He, wait until I find time to clean up and upload the current version! It's considerably stronger than the old one (it's about on-par with gnuchess, according to a few mini-matches I did a few days ago and allowing for a slight increase in playing strength since then).

Yup.
It usually spits out something vaguely sensible. If not, I can probably find the last time I touched a pointer/array and figure the problem out from there, since that's probably when I broke things if the error wasn't there before.
Using svn (or cvs) is also a great for debugging (if you introduced any new bugs that is).

Remember the problem I mentioned above where the program was going into repetitions if it found a mate-score in the transposition table? I was browsing through Crafty's revision history when I found this:

Glad I'm not the only one who runs into problems like this!

Even if you don't want to polish ending game right now, you could go to chessproblems.com and see if your program is able to find the asked mates.

Both "Isildur" and "Jazz" are great names, however not the combination of the two.

Evert, will it be possible to compile your engine without allegro? Or, at least, will there be an option to just run it in text mode without any graphics?

Interesting, because from last week GNU Chess also started to play in my tourney. Currently #78 in my list with rating of 2344 points, after 160 games. However it's so buggy that it's not a good engine to use as a rating reference. (It has serious time management problem when playing with external book, which makes it about 100 points weaker, alternatively it can play without any book to become only about 50 points weaker, these are initial rough estimates, more accurate estimates in September. Details here).

EDIT:

Practical benefit from Nalimov (or other DTM/DTC/DTZ) tables is very small, but some bitbases should give measurable strength increase, since bitbases are must smaller and faster to access (so you can probe them deeper in search), so you can keep much of them in RAM. Daniel Shawul's Scorpio bitbases is one nice open source impementation, used by number of other engines. (link)

I'll have a look. Most mate problems tend to be relatively easy though, since they're usually sequences of forced moves. Note that that just means finding "a mate", not necessarily the best one!

This little beauty

gets solved in about 0.2s:

However, the "correct" answer is 1. Rh6!, which is a mate in 5 (a mate in 5 starting with a rook sacrifice and followed by three quiet moves; not very nice for a computer).
They're good positions to check whether code to detect threats works, however.

In practice it doesn't really matter of course if you find a mate-in-N or a mate-in-N+a-bit, as long as you actually deliver the mate!

Oh yes. The engine itself is just a few interface functions that manipulate a "game" or "board" object (one is everything to do with the current game, one is about the current position only). The interface (any interface) is deliberately decoupled from that.
Right now I have about 5 different "interfaces": the Allegro-based one, a console one I never really did anything with after making the Allegro-based one (I use it to solve individual test positions though), a "perftest" that counts the number of nodes from the starting position after a certain fixed depth and measures the time it takes to get there (useful for debugging the move generator, apparently, though it hasn't helped me there, I've mainly used it to measure the effect of optimisations on the move generator and make-move functions), a "test" driver that loads a collection of test positions and runs them through the engine for a given time-per-move and the UCI interface (to the extent that this currently supports the full UCI protocol). Only the Allegro-based interface depends on Allegro.

Sounds about right, comparing the relative strengths I've seen in other rating lists.

Hmm... ok, I'll bear that in mind. My code still doesn't have an opening book (although it doesn't bodge things up as badly as it used to anymore) but since it's a UCI engine, I've taken the cheap way out and let the interface handle the opening for now (since I'm playing it against xboard engines under xboard, that means I'm running it through polyglot).

Thanks! I'll have a look. My understanding of bitbases is that they only offer information on whether a position is "won", "lost" or "draw". While I'm sure that's useful information, I need to work out how to implement that in the alpha-beta framework of a chess engine, where I'd typically want to know more than simply "won"; for instance, won in how many moves.
On the other hand, the main advantage is probably that you get an accurate evaluation of the position in a leave node near the search horizon after exchanging into the end game, where you otherwise wouldn't be able to tell as accurately whether it's a good ending or not and so whether you should exchange into it or not.

Solving mate problems is counter-productive for improving engine strength, because mate solving depends on pure tactics and discourages any positional knowledge. Although it's OK to solve mates just for fun.

Here is one much more interesting test suite: Strategic Test Suite.

Excellent! Naturally I am only interested in a UCI version.

With or without opening book code is both fine. Most chess interfaces provide book handling, as well as polyglot of course. If you'll decide to implement opening book, please provide a way to disable it, because many tournaments accept only engines that can play without own opening book.

Exactly. Yes, bitbases only have "win/loss/draw" information, but it's often enough. On the upside, bitbases are small and fast, so you can probe them long before the exchange, to know which endgame to convert to. Although winning some won endings (like some kqpkq positions) with just bitbases may be tough or impossible.

As long as your opponent doesn't have a mate-in-N-a-bit

Once I arrive home I will post the most beautiful game I have ever read about, to demonstrate machines can't yet reach a human's inventive

Yes, and it should play them out properly after finding them. It's also useful to check if the engine will correctly detect deep combinations that may show up outside of the principle variation that it builds up. I haven't tried to write an efficient mate-solver though, mainly for the reason you mentioned: it's a waste of time in terms of actual playing strength.
That said, I've probably seen better improvements on test scores from tuning based on actual games than from tuning based on test score results...

I think the UCI specification demands that you do that.
Not that I believe all engines implement the UCI specification to the letter.

In that case the position will not be scored as mate-in-N+a-bit in your favour.

Oh, most computers play a horrible kind of chess, and perform very poorly in closed strategic positions. They've become a lot better and maybe the top engines these days can't be defeated by "anti-computer" tactics so easily anymore, but all of the weaker ones almost certainly can be.

EDIT: Latest source attached.
It should now compile cleanly on both OS X and Linux (I haven't tried Windows, but since I haven't done anything for Windows specifically, it's likely to be as hard to compile there as the previous version was; MinGW might work though).
There are various improvements and enhancements, and the engine should play a better game than the one I posted here earlier (but maybe not as good overall as some of my earlier builds; I've been adding new functionality to the evaluation function and I don't think everything has been properly tuned yet - and of course, there's still a lot missing there too).
To build the UCI engine (for running using a generic GUI rather than the build-in Allegro5 one), run "make ucijazz". The UCI implementation is a bit rough at the moment, but it works well enough to play a game.
The engine's time management isn't that great at the moment (again, something I would need to tune); I find it plays best when given a fixed time per move...

EDIT2: Oh, before I forget: to build the Allegro 5-based GUI, you'll need the latest (SVN) version of Allegro...

It compiled fine here under Windows, and I started some test matches with it. I only compiled UCI version. Some comments so far:
1. I had to add qsort.o into makefile.
2. The engine does not print anything when it is thinking. When it moves, it sends no evaluation or ponder move.
3. An engine sais it's named "Jazz (i386)". It's better to specify its version there too. Releasing engine without version will result in a mess when people will try to run matches with it and report results.

More after some games are finished.

Amazing!

Cool. It'll be interesting to know how things run.

Makes sense.

Right. At the moment, it's only added on Linux. I should probably add it for MinGW as well, but better would be to detect when it's needed and when it isn't.
Or just always use it, even if a native version is available...

That's odd. It should, and does for me when I run it under a UCI interface here (but it doesn't when I run it through polyglot in XBoard).

Right, as I said, the UCI implementation is somewhat incomplete. Not sending a ponder move is correct: at the moment, the engine cannot ponder. This is actually relatively easy to add using UCI (just make the next move from the principle variation and enter an infinite search), but I haven't got round to doing this.

It'll have a proper version when it's properly released.
I'll stick something temporary in there now, so you can always identify different versions (this being the only one not to report any version information).

I compiled it using cygwin so I did not expect too much trouble. Although cygwin is 32-bit only. Does Jazz benefit from 64-bit?

Well the good news is that it works and did not crash or hang yet. The bad news: it's losing most of the games, probably because of broken time management. I use TC of 4 seconds for 40 moves, repeated. What Jazz does looks like this: at first all looks normal, then it starts thinking longer and longer on each move. Its time usage peaks at move 20, then the time is almost out, so it spends about a second on each move. On move 40 it receives another 4 minutes, so it starts thinking longer again. Then the time usage again peaks on move 60, and instant play after that.

It is playing with "Gk 0.90 64-bit JA" and "WJChess 1.64".

I would just add it for all cases.

Not sure what's wrong there, I may look into it in more detail if I have time.

Usually UCI engines send a ponder move even in ponder off mode, and even when they can't ponder at all. This way an engine tells which move it expects from the opponent, which may be useful for things other than pondering. I don't mean you have to do it, but it's a good style. Anyway, it's just next move from the PV as you say.

Yeah, anything is good as long as it's different from one version to another.

Considerably. The 64 bit version is about twice as fast as the 32 bit version on my test machine. Note that I've done all of my development in 64 bit and haven't (yet) made any effort to speed up 32 bit.
On the other hand, a factor 2 is "only" one ply of search... which makes a difference, but the difference between 10 and 11 ply shouldn't be so shocking, especially considering that the principle variation will probably be searched deeper and that this excludes the quiescence search.

Good, it shouldn't. That's not saying it never will, of course, but I hope I've been careful about fixing things like that.

That does sound similar to what I'm seeing. What it should do is divide the remaining time by the number of moves until the next time control and add half the increment (if there is one) and use that amount of time for each move. It's not particularly clever, but it should work nevertheless.
I suppose it's possible that I'm not checking the clock often enough during the search, but I wouldn't have thought it would cause that many problems. Certainly something I'll have to experiment with a bit. I keep a log of all UCI commands received by the engine, so I can at least look at that and try to reproduce what it's doing during the game (oh, you may want to remove that log, since it's appended to and never deleted. I'll make that a debug option so it doesn't get written by default).

I don't suppose you keep records of the individual games (PGN)? I'd be interested in checking some of them to work out where the problem lies. Major shortcomings I've noticed are in its idea of king safety (it'll castle and keep its pawn shield in tact after that, but it doesn't take much to have it wreck either before that, so it'll often either castle into a wide-open king side, or move the king on its own) and playing endgames. In particular rook endings, which is probably due to the very poorly tuned evaluation in the end game. And possibly the lack of bitbases for those cases as well.

OK, then I guess I or someone will have to try and build a 64-bit Windows binary when it's ready for prime time. (Most of tournaments are run under Windows for historical reasons).

Of course I keep all the games. I'll post the PGN of the complete matches, should be sometime tomorrow. By the way, do you also need that log-file?

I just checked that log-file and it only contains what engine received, but not what engine printed, so it does not help to understand why no engine output is shown when it's thinking.

Yup. The new 64-bit GCC released for Windows the other day^[1] looks interesting for that.

Interesting. I wonder what the main reason for that is, although I suppose most commercial engines being only available for Windows and most hobbyist programmers also (historically at least) using Windows has something to do with it. Crafty and GNUchess being obvious examples of engines that were born on different platforms.

Ok, great!

Probably not; unless I know what I'm looking for exactly it's probably too large and unwieldy to work out which line in the file corresponds to which position in which game.

That's actually just a matter of un-commenting one line in the source and commenting another, but what I'd do (probably will do, when I get round to it) is just start ucijazz in a terminal and send it position and go commands from the log. That's also how I plan to debug the time management.

EDIT
In fact, sending

(The last two lines of the logfile on my machine) I get

which seems right to me.
However, it doesn't send a principle variation. I thought I made it do that, but maybe it only prints it in its "native" output (which is suppressed when using UCI). There are issues with it anyway, since now and then the principle variation will be truncated by the transposition table. I know how to fix that (if the new PV is shorter than the old one, but the moves that are there are the same, keep the old one - or alternatively and in addition, try to reconstruct the missing part from the transposition table) but I haven't got round to it yet...

OK, here are some games (attached):

Jazz (i386) - WJChess 1.64: 4.5 - 27.5
Jazz (i386) - Gk 0.90 64-bit JA: 8.5 - 23.5

Not as bad as it looked from the beginning. Still it probably can do much better with fixed time allocation.

Somewhere in late 90's, thanks to the activity of Chessbase and other vendors of commercial software, Windows became de-facto standard for any serious chess (or computer chess) hobbyist. Then it entered an infinite loop - new authors and companies target Windows because 99% of potential users use Windows. Users keep using Windows because it can run about 100% of chess software.

Sorry, yes, that's what I meant. It does not send the PV, so I can't see what move it preferring currently, when it is still thinking.

Thanks!
I had a quick look at four of the games (one win and one loss against each of the opponents); it's a bit confusing. For the most part, Jazz seems to play decently well in the middle game, although it doesn't quite centralise its pieces as efficiently as it could and it seems to like leaving a pawn vulnerable and then stepping in to defend it at the last moment, which isn't so good. The way it plays endings looks pretty bad, and I've seen it drop a piece in both the losses I looked at in a position where I wouldn't have thought it necessary to do so. That could be the broken time management ruining things; I should check whether these blunders correlate with move number.

It's the same everywhere.
I neglected to mention Glaurung as another example of an engine that originated on another platform above.

Right, I checked the code, and it indeed doesn't send the PV in UCI mode. I'll fix that once I have the code to "keep" the PV (what I described earlier) in place.

By the way, I fixed a rather nasty bug late last night: when generating check evasions, Jazz will only generate moves that can eliminate the check (as opposed to generating all moves and discard the ones that don't eliminate check afterwards). It will generate captures (of the checking piece, if there is only one), legal king moves and (finally) moves that interrupt the line of sight of the checking piece. However, there was a bug where it would not generate these if the check was across a file. By ill luck, this didn't show up in any of the test positions I tested the new code on, but I found it yesterday when I used the same lookup tables for something else.
At worst, this bug could have lead Jazz to see a mate where there wasn't one, but the most probably effect is that it miscalculated the best response to check, maybe dropping a piece or walking into a forced mate in the process. I'll check to what extent this may have damaged match results locally, then attach a new version later on.

Hi Evert,

Great to see there's still people with enough enthusiasm to write chess playing programs. I dedicated a huge amount of time to writing an engine back in the 1990's.

It's a fun experience - as well as the programming side of things, I got to meet some interesting folk, and to travel around a bit to the world microcomputer chess championships.

I haven't developed my program for a few years, though - kinda got burned out on that front. If your engine runs under Winboard, give it a whirl against mine? She's called Francesca.

Anyhow, good luck and have fun with your computer chess developments

It crashed on me Evert, I attached the console output so maybe you can figure out why.

Edit:

Just happened again in a similar way...

The PGN includes thinking times, depth, evaluation and expected opponent's move (when it is different from the one played). BTW this is another downside of Jazz not sending a PV: there are no Jazz' evaluations or expected moves in the PGN. Sometimes they are very useful to see what happened in the game.

Hopefully also with a time management fix.

Hi S G! Francesca is doing fine in my tourney^[1], but unfortunately she can't use external book (because of missing support for setting a position). So she has to play without any opening book at all which probably handicaps her considerably.

There seems to be a fairly active community for it, although I can't really judge how large the influx of new people is.
I guess writing a chess program is a fairly daunting task and requires some dedication and attention to details (in other words, you need to write reasonably bug-free code), so I can imagine people getting started on it and then abandoning the prject before it gets anywhere.

Cool. My first chess program was from 1996 or so. I can't run it now though, because it was written in Turbo Pascal mixed with assembly language (actually, almost everything was written in assembly). It played horrible though.

That would be fun to do - but I'm afraid finding the time for something like that will be hard...

I'll give it ago! I decided to implement the UCI protocol (it's a bit simpler), but I can run through XBoard using a translator.

Damn! Sorry about that...
Any chance you could send me your moves so I can try to reproduce the sequence of moves here?
Alternatively (or perhaps even better), if you're willing to look into this, could you send me a gdb backtrace?

Heh. I'll do my best.

You must be tired Evert, for you forgot to read my post completely...

Also the flickering is related to the compositor...I ran it from gdb but it froze my machine...rare on Linux but it did happen... i had to press the power button...

I think it has to do with allegro and specifically the opensource ati driver...it's buggy.
Edit:

I was able to beat jazz after a couple of games, I think it plays a pretty good game at 5secs. It's weakness is the early middle game i believe.

It was late, but I think I read everything: it crashed, you attached the console output, then it crashed again in the same (or a similar) way. In the log you showed, there is a segfault after a 7 ply search... but that knowledge alone isn't enough to debug the problem, I probably need at least the sequence of moves from the initial position if I'm going to try to reproduce it...

Hmm. Do you see the same thing with the A5 examples or demo?

Woops! Again, sorry about that... it doesn't do that for me, but that doesn't help you. If you have the core dump, you should also be able to get a backtrace from that (gdb jazz core).

Perhaps... still, would be good to sort out.

Against humans, quite possibly. Against other computers, I'm not so sure... I've seen it play a pretty lousy end game as well.
The early middle game is probably where the search is shallowest (well, the opening will be worse, but it's not as important there) and where the lack of certain evaluation features (most notably, proper king safety) hurts most. If it gets through this stage without wrecking its king's position, it probably won't unless pressured, so it should do ok in that case and reach the end game ok. The end game evaluation is crude and inaccurate, but the search depth at least partly makes up for it. Again maybe not against other computers, but against humans it probably does.

Kirr - I checked out your website, what a fantastic effort.

Evert - I look forward to some Jazz vs Francesca games. Have fun with your development!

Greetz

I'm not able to save with F6, getting a zero length file.

Weird. Under which conditions? I'll see if I can reproduce it here.
To be clear, F6 is only supposed to save the position, not the entire game.

EDIT:
Interesting. I've been playing with the move ordering scheme, and there is a clear asymmetry between black and white in the order in which moves are searched and generated (not surprising, considering the way in which I generate the moves), which makes a big difference in the speed of the program: some test positions are solved almost twice as fast with white to move than the flipped positions with black to move.
That's nasty, and I'll need to fix that...