General question about chess engines.

[Fguy64]

It's not exactly clear to me just what a chess engine does, besides calculate and analyze. Does it do legal move generation?

I'm asking because I have written a Java applet that consists of a GUI and a legal move generator, and little else. It works well, and plays by the rules, but has no smarts. I'm interested in knowing what it would take to interface a decent chess engine with it.

If you are interested in checking out my program, It's available at http://fchess.x10hosting.com. It's really nothing special, but I hope to change that in the future.

regards.

[Roman Hartmann]

It's not exactly clear to me just what a chess engine does, besides calculate and analyze. Does it do legal move generation?

I'm asking because I have written a Java applet that consists of a GUI and a legal move generator, and little else. It works well, and plays by the rules, but has no smarts. I'm interested in knowing what it would take to interface a decent chess engine with it.

If you are interested in checking out my program, It's available at http://fchess.x10hosting.com. It's really nothing special, but I hope to change that in the future.

regards.

Hi,
an engine does more than legal move generation. You can split an engine in three parts and one of them is (legal) move generation. Beside there is a search and an evaluation routine.

So if you add a search and an evaluation routine to your applet you have a chess engine.

You might want to look up Minimax, Alpha Beta and Negamax to get an idea how searching in a chess engine (usually) works. For the evaluation routine you could just sum up all the material on the board for a start.

best regards
Roman

[hgm]

Yes, engines generates legal moves. E.g. a WinBoard engine takes text commands to set up the board for starting a new game ('new'), tell it how much time it has for the game (or for a given nr of moves, 'level'), to start it playing for the side to move (when it has white, 'go'; after 'new' it assumes it plays black), or to play a move (just send the move, say 'e2e4' or 'e1g1').

It keeps track of the side to move in the game it is playing, and if the turn comes up of the color it is playing, it starts thinking spontaneously, and will print the move when it is done (as 'move d7d5', say).

There are many other commands you can give it as well (e.g. to synchronize its clock with that of the GUI, set up an arbitrary position, make it play a Chess variant in stead of normal Chess, offer draws). In fact an engine is a fully selfcontained Chess program, which communicates in text mode (oly gving moves, not printingthe board).

[Fguy64]

[quote="Roman Hartmann"][quote="Fguy64"]It's not exactly clear to me just what a chess engine does, besides calculate and analyze. Does it do legal move generation?

I'm asking because I have written a Java applet that consists of a GUI and a legal move generator, and little else. It works well, and plays by the rules, but has no smarts. I'm interested in knowing what it would take to interface a decent chess engine with it.

If you are interested in checking out my program, It's available at http://fchess.x10hosting.com. It's really nothing special, but I hope to change that in the future.

regards.[/quote]

Hi,
an engine does more than legal move generation. You can split an engine in three parts and one of them is (legal) move generation. Beside there is a search and an evaluation routine.

So if you add a search and an evaluation routine to your applet you have a chess engine.

You might want to look up Minimax, Alpha Beta and Negamax to get an idea how searching in a chess engine (usually) works. For the evaluation routine you could just sum up all the material on the board for a start.

best regards
Roman[/quote]

Thanks, That helps. I have poked around the chess programming wiki, looking at some of the topics you have suggested. I'm not an advanced level programmer, and most of the chess specific material I have read is too difficult. I feel I should build up to it, maybe with some introductory level recursive programming tutorial in order to get a feel for things. I'll keep trying.

p.s. I seem to have made a mess of this post. This is one flaky editor this forum has.

[Edmund]

The most simple recursive function to get a feel for it is probably one to calculate the factorial:

Code: Select all

 unsigned int factorial(unsigned int n) {
     if (n <= 1) {
          return 1;
     } else {
          return n * factorial(n-1);
     }
 }

In chess engines you are using something a little more difficult. For example the return value is inverted every time, because the advantage of one side is the disadvantage of the other and vice versa.

You might want to check some of the tutorial chess engines. CPW-Engine, TSCP, etc

[Fguy64]

Thanks gentlemen. I have found the following tutorial, which seems like a good place to start becoming more confortable with general recurson.

Sure enough Edmund, I just finished exercise #1, which was to code the factorial example. The "Hello World!" of recursive programming.


http://erwnerve.tripod.com/prog/recursion/

[MattieShoes]

For interfacing an engine, most engines use UCI or winboard protocols. If you wanted to connect an existing engine to your interface, chances are it'd support one or the other, so you'd need to code support for one or both. I haven't done that but I know it's not a simple task. Winboard, Xboard, Arena, and other interfaces already do this.

For writing an engine, I think you need six basic functions
1) make a move
2) take back a move
3) generate moves
4) search
5) quiescence search
6) eval
You probably have the first 3 done.

There's some differences from engine to engine in terms of how they handle illegal moves. For instance, you could only generate *legal* moves and then makemove just does the move blindly. The other scheme is to generate pseudo-legal moves in move generation, and then have the makemove function only make the move if it's legal, and return true/false to indicate whether it made the move. I think the second system is faster with most simplistic setups because check detection might be expensive. A third implementation only generates legal moves at the root of the tree, then lets king captures happen and score the position appropriately so the engine should avoid them.

For taking back a move, generally you have a copy of the board state stashed away or at least enough information to recreate it quickly.

For move generation, most engines have two functions. One generates all moves and is used in search. The second generates only moves likely to drastically change the score and is used in quiesence search. The simplest implementation for that is just generating captures.

For search, alpha beta is a good place to start. The code for a straight alpha beta search is very compact and easy even if the concepts are not. At least, it took me a while to understand alpha beta. The search function calls itself recursively until it hits the specified depth. Once it hits the specified depth, it calls the quiescence search.

Quiescence search is used to find a "quiet" position to evaluate. It searches only a subset of moves likely to drastically change the score, and compares them to the current evaluation or best score so far (whichever is higher) to see whether making any capture helps. Eventually it will reach a position where no captures help and get a realistic score from eval. This is necessary to mediate horizon effects -- for instance, QxP looks like a great move if it sits on the horizon, because it doesn't see the PxQ response on the other side. Quiescence search goes deep enough to finish off exchanges like that so it knows that QxP move was terrible.

Eval is as complex as you want it to be. To beat weak humans, material evaluation alone can do it, but it doesn't play very realistically. Adding in pcsq tables can make it play less weird. Basically pcsq tables are a bonus or penalty for each square on the board, and a piece occupying that square gets that bonus or penalty. Most engines have separate tables for separate pieces, and may even have an early game version and a late game version, especially for kings. That'd be enough to make it play interesting chess.

Then theres ten bazillion things to improve it after that, but I think those are the biggies.

[Fguy64]

Thanks Matt, that was helpful. You remark about legal move generation vs. pseudo legal move generation is appropriate. my program currently does the 2nd, generate all legal moves and then do searching and eval.

I find myself wondering whether my char[8][8] position representation will take me very far. So much of my program is tied to that. I have noticed something about mailbox vs. 0x88 board representation, I suppose I should check that out.


ANyways, like I mentioned above, I'm probably goona spend some time studying general recursion theory first.

regards.

[pedrox]

I use int[64], one for the type of piece and the other for color.

I do not use mailbox nor 0x88 nor bitboards.

I've tried mailbox 12x10 and it is approximately 30-40% slower for me. Gen moves is slower and is slower the calculation of mobility and check if a square is attacked by a piece.

[Fguy64]

Interesting, Pedro. Without further study of that design, I can only imagine that it would be a lot less intuitive than my simple char[8][8] with upper case for white, lower case for black, and '1' for empty squares, exact;y as in the standard fen string. After 30+ years of studying human chess, it's not easy to start thinking about different layouts of the chessboard.