Generic Search Engine Pseudocode Transformed into C

[LiquidNitrogenOverclocker]

Does anyone know of a complete set of C source for an engine that is just a generic implementation of "pseudocode" examples?

For example, we have all seen how "alpha_beta" is explained on many different wikipedia type pages:

Code: Select all

function alphabeta(node, depth, α, β)         
    (* β represents previous player best choice - doesn't want it if α would worsen it *)
    if  depth = 0 "or" node is a terminal node
        return the heuristic value of node
    foreach child of node
        α := max(α, -alphabeta(child, depth-1, -β, -α))     
        (* use symmetry, -β becomes subsequently pruned α *)
        if β≤α
            break                             (* Beta cut-off *)
    return α

(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity)

And then you usually find citations showing how NegaScout is slightly better than alphabeta...

Code: Select all

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            α := max(α, -negamax(child, depth-1, -β, -α, -color))
            {the following if statement constitutes alpha-beta pruning}
            if α≥β
                return α
        return α

... and this is usually followed by mentioning that MTD(f) is a further refinement if the transposition table is able to produce enough cutoffs...

Code: Select all

 function MTDF(root, f, d)
     g := f
     upperBound := +∞
     lowerBound := -∞
     while lowerBound < upperBound
         if g = lowerBound then 
             β := g+1 
         else 
             β := g
         g := AlphaBetaWithMemory(root, β-1, β, d)
         if g < β then 
             upperBound := g 
         else 
             lowerBound := g
     return g

But you DON'T SEE any C code anywhere that you can compile to support any of this.

It would be awesome if there existed some generic C sources that show the same move generator (and it can be primitive for demonstration purposes) with a hash table scheme (and this not be overly ornate either, again, just to demo the numbers) using different search schemes, so that you can see than searching to a depth 'D' using one scheme requires the examination of more nodes than searching to the same depth with a different scheme, and so on.

Has anyone ever seen such a set of code? Or have most of these claims just been taken on faith? I know papers exist on each of the schemes mentioned here, but I'd like to "see it with my own eyes" and do my own tests on these different schemes without having to reinvent the wheel.

Maybe that's just wishful thinking on my part.

[wgarvin]

Lots of little implementation details are an important part of most source code. The whole point of pseudocode is that it leaves out most of those details, so that the algorithm or concept being demonstrated can be grasped more easily.

There are working engines that are open-source that contain implementations of virtually every idea discussed in this forum, but reading them can be a pain because you have to cope with all of those details. To learn anything from the details, you have to separate out the ones that are something useful to do with the technique you're interested in, from the details that are about other things, or are just quirks of that particular engine.. Not everybody writes their code with other readers in mind, either.

Maybe what you're asking for is "an engine written in C, but without all of the little enhancements and clever tricks that real programs use"? In that case, maybe the closest thing would be something like TSCP. Of course it won't be as "pure" of implementation details as pseudocode is, but its short, well commented, etc.

But anyway, why would this be useful? For learning the algorithm or concept, it won't be as clear as pseudocode. For figuring out implementation details (efficient data structures, etc.) one will not learn anything from this simple kind of program, only from studying strong open-source engines or applying one's own programming experience.

[jshriver]

Checkout perft.c here this might help a little.
http://home.hccnet.nl/h.g.muller/dwnldpage.html

This is probably the cleanest and to the point code for what your wanting. Otherwise there are various open source engines that are written in C that you can look at their code. tscp, crafty and such.

Good luck, I've been there trying to figure it out. lol still am.
-Josh

[LiquidNitrogenOverclocker]

Checkout perft.c here this might help a little.
http://home.hccnet.nl/h.g.muller/dwnldpage.html

This is probably the cleanest and to the point code for what your wanting. Otherwise there are various open source engines that are written in C that you can look at their code. tscp, crafty and such.

Good luck, I've been there trying to figure it out. lol still am.
-Josh

Well, I wrote my first chess program when I was 19 years old, back in 1985. It ran on my 128K Macintosh, fit on a single 400K floppy disk that also needed to have the entire Operating System on it (no hard drives yet) and it ran at the blinding speed of a 6 MHz clock!

By 1987 it was a member of the United States Chess Federation, and its current rating is listed at 2129, (making it 22nd on the list of 71 computers, including 2 entries for Crafty and Cray Blitz, 2 entries for Deep Thought and its predecessor Chip Test, and of course HiTech by Hans Berliner and Belle by Ken Thompson) although it had not played a game after 1990, and never on hardware faster than 16 MHz.

http://www.uschess.org/msa/MbrDtlRtgSupp.php?12528567

I was not asking for the purpose of "learning", I guess it was more out of laziness. I thought, surely, somebody must have hooked up a move generator and search engine up to several different search strategies in order to figure out which one to use.