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

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

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.

-O3 BAD! VERY BAD!

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

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.

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.

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.

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.

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.

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

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!

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.