Search v. Evaluation

[benstoker]

I hope I pose this question clearly.

Within in any given chess engine, is the evaluation function intertwined with the "DNA" of the search function so that the two cannot be divorced. OR, do or can the two functions be completely modularized so that the search function could employ any number of different techniques without having to change the mechanics of the eval function?

For instance, could there be a kind of protocol or api for the eval function such that different eval functions could be dropped in place with any search function. Thus, you could conceivably mix and match Toga's Search with Stockfish's Eval.

Most likely I have a deep ignorance of the process ...

[Greg Strong]

I hope I pose this question clearly.

Within in any given chess engine, is the evaluation function intertwined with the "DNA" of the search function so that the two cannot be divorced. OR, do or can the two functions be completely modularized so that the search function could employ any number of different techniques without having to change the mechanics of the eval function?

For instance, could there be a kind of protocol or api for the eval function such that different eval functions could be dropped in place with any search function. Thus, you could conceivably mix and match Toga's Search with Stockfish's Eval.

Most likely I have a deep ignorance of the process ...

This isn't going to work with most (if any) currently available engines. The search and eval functions both depend on the program's specific board representation (and other state data, such as the information in the search stack).

I do kinda wish we could have a couple "standard" implementations of state information so that such a thing could be possible... But "standard" implementations would also probably rob the really strong programs of some potential for clever enhancements/tricks...

[Dann Corbit]

I hope I pose this question clearly.

Within in any given chess engine, is the evaluation function intertwined with the "DNA" of the search function so that the two cannot be divorced. OR, do or can the two functions be completely modularized so that the search function could employ any number of different techniques without having to change the mechanics of the eval function?

For instance, could there be a kind of protocol or api for the eval function such that different eval functions could be dropped in place with any search function. Thus, you could conceivably mix and match Toga's Search with Stockfish's Eval.

Most likely I have a deep ignorance of the process ...

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

It would also take some discipline on the part of the programmer to never, ever go right to the bones underneath the covers and always use only the API for analysis and search operations.
(IOW, it is tempting at times to make data members public and operate on them directly).

[Greg Strong]

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

Totally possible... The question is how many people are interested in writing chess code in such a way. I certainly am, and would be very interested in helping to design the interfaces and write a reference engine if others were interested. I think there is a lot to be learned, potentially ...

[Dann Corbit]

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

Totally possible... The question is how many people are interested in writing chess code in such a way. I certainly am, and would be very interested in helping to design the interfaces and write a reference engine if others were interested. I think there is a lot to be learned, potentially ...

It's not just search and eval that would have to be written in this manner. It would be the entire program. For instance, move generation must also use the interface in this manner and all other aspects of the chess program.

It's not difficult at all, really. It's just different from the way that things are usually done.

[Dann Corbit]

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

Totally possible... The question is how many people are interested in writing chess code in such a way. I certainly am, and would be very interested in helping to design the interfaces and write a reference engine if others were interested. I think there is a lot to be learned, potentially ...

It's not just search and eval that would have to be written in this manner. It would be the entire program. For instance, move generation must also use the interface in this manner and all other aspects of the chess program.

It's not difficult at all, really. It's just different from the way that things are usually done.

The author of Elephant, Harald Lüßen, did something a bit like that for bitboards only (so he did not have to be quite so extreme about it). What his code allowed was for any sort of bitboard representation to be chosen at compile time (so magic bitboards, rotated bitboards, hyperbolic bitboards, etc. could be changed at will).

[benstoker]

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

Totally possible... The question is how many people are interested in writing chess code in such a way. I certainly am, and would be very interested in helping to design the interfaces and write a reference engine if others were interested. I think there is a lot to be learned, potentially ...

Off the top of your head, do you have a rough I idea what this abstract API would resemble? What would be the 'universal' terms to pass between the two function, ie, search and eval?

[MattieShoes]

In C++ you could model this with abstract classes and then implement the particular ideas uderneath which use the abstract API. There will be a small performance penalty for doing things that way. However, the gain in understanding of how different systems interact might make it worthwhile.

Totally possible... The question is how many people are interested in writing chess code in such a way. I certainly am, and would be very interested in helping to design the interfaces and write a reference engine if others were interested. I think there is a lot to be learned, potentially ...

I was considering doing this myself, though it's mostly in the thinking stage... Nothing so grand as defining some overarching standard, just a very modular approach, so I could in theory write a couple subclasses and implement an entirely new game. It wouldn't be strong compared to the serious programs but... If nothing else, it'd be a nice testbed for screwing around with new ideas.

There are two areas that I haven't really figured out though.

1) The definition of a move. I could make a purely virtual move class and have different games define it for themselves, or I could make some sort of generic move class that'd hopefully be applicable to most games. Given how much boxing/unboxing would be going on, I'm leaning towards the latter. It's kludgy but I imagine just about any game will be able to use something that has from, to, and a couple extra fields (in chess, move description and promotion piece).

2) Scoring for move ordering. This is obviously hugely important, but who does it? It'd need to access to the move stack, the board, the hash table, and the eval in order to work. Perhaps have an entirely separate class with access to all of these?

If anybody has any suggestions, I'm all ears

[Greg Strong]

Ahhh, you've changed the subject slightly ... You're talking about a universal chess engine, a subject near and dear to my heart

1. You want the second option for sure... a generic structure. In ChessV a generic 'move' structure contains four values - from square number, to square number, promotion type (zero if not a promotion), and 'tag' (a generic number for special purposes. Each of these can be a single byte (assuming no board has more than 256 squares), and they pack together nicely into a 32-bit integer. The 'tag' value is only necessary when the combination (from square, to square) isn't unique and it isn't a promotion. I almost never had to use it at all in ChessV. The only instance I can think of was for the special 'free castling' rule in Capablanca Chess Aberg Variant. In free castling, the king can move any number of squares toward the rook and the rook can be dropped on any square passed over, so the tag value holds the rook square. Since I almost never even needed to use the tag value, I'm pretty confident that these four values are more than enough for any game reasonably chess-like.

2. Good question - I have no grand architecture for this (as far as I recall) - no virtual functions or the like. Again, as long as you're only playing games that are reasonably chess-like, you can go a long, long way with simple MVV/LVA move ordering for captures, PST ordering for non-captures, a bonus for a move where more than one piece moves (so castling moves get ordered high), and of course standard TT move & killer move(s). Your move ordering code doesn't really need to know game specifics to do a pretty good job. Now in ChessV I did also add an SEE function with the ability for a variant to turn it off for the exotic games where capturing is not by replacement. (Chess has one example of capture not by replacement - En Passant, but the ChessV SEE doesn't understand that at all and it still works well enough even ignoring that situation ...)

If you're really interested in making a universal chess engine, and I strongly encourage it as there are only a few in existance, then I can give you a *lot* more advice, having been thinking about them and working on them for nearly 8 years now! And, of course, check out the ChessV source code if you haven't already... http://www.samiam.org/chessv

Cheers,
Greg

[Karatorian]

My current project has search compleatly modularized away from board representation and move generation. In general, the whole thing is pretty modularized. I should be able to change move generation, eval, or search without alterning any of the others. Changing board representation would be a problem though.

I did it this way because my program is in the early stages and I know that a lot of this stuff is going to be heavily modified in the future, so reducing interdependance of the parts is will make it less likely to introduce bugs while doing so.

However, some things aren't entirely independant. For instance, I don't currently have qsearch and to add it, will, obviously, require changing both search and move generation.