Website for micro-Max

[Uri Blass]

Note that the main problem that prevents me to compile MicroMax is
the following error.

c:\simple chess program\main.cpp(219) : error C2065: 'random' : undeclared identifier

random is simply not available C++ fiunction and in the help I find nothing about it.

I can use rand instead of it but i am not sure if this is the intention.

Uri

[Uri Blass]

Well, I did some tests after making micro-Max quasi Winboard compatible, (thanks, R?mi...), but it is clearly weaker then TSCP. What seems to break it is the complete neglect of King safety in the positional evaluation. In combination with the lack of check extensions and check detection in end leaves, this is quite fatal.

If playing strength is the main concern, threat detection and threat-evasion extensions would probably be a much more valuable investment than a hash table. The latter does not buy all that much advantage in the middle game. I already found earlier that the recapture extension is also a bad idea; a version of micro-Max that only searches recaptures in QS, rather than alwas giving an extension for them, beats the version on my web-site by 65-35 when given equal number of nodes to search.

But micro-Max is meant more as a show case of important concepts in chess programming than as an attempt to play the best possible chess. In that respect it seemed interesting to also have an extension in it (and I could get this one for free). This is why I left it in.

I think that king safety is not the main problem.

It is possible to be significantly stronger than tscp with no king safety evaluation.

Check extensions is very important for playing strength and it is the only simple important extension.

It is possible that inspite of hash tscp has better order of moves and order
of moves when you have no move in the hash is important.

Uri

[H.G.Muller]

random() seems synonymous to rand(). The latter should be a standard library function. (And it is even saves 2 characters! ) I did not bother to look it up in the manual, I just guessed the name of the routine I needed would be' random()', and under cygwin this worked so I did not bother to look further. But if I compile with the option '-mno-cygwin' (which I had to do for a Winboard compatible version, where it has to be able to run from an ordinary command line) it complains also about the random(), so apparently this is a redefinition in a cygwin-specific automatically included .h file (Also see: http://www.gnu.org/software/libc/manual ... om-Numbers)

That the linker does not recognize the printf() and getchar() standard functions is probably because it is a C++ linker that distinguishes functions not only by name, but also by type, and the (implicit) declaration that the C-compiler gives it from the program might not coincide with the definition in the library. I guess that an explicit declaration through #including <stdio.h> should solve this. I don't know if a linker option existst that can tell the linker to simply link, and refrain from type checking. (I had this problem in some of my scientific calculations too, where it proved suddenly impossible to link hand-optimized assembler files that were originally derived from -S compiler output from an older gcc version to a main program compiled with a newer version, because it imagined a type mismatch.... )

The 'undeclared identifier' errors on the arguments of the function D() are a bit strange. Surely Dann's version that converted the declaration from Kernighan&Ritchie- to ANSI-style should not evoke these errors?

Finally, the warnings about operator priorities are extremely pedantic. Of course I don't write parenthesese where they are not needed by the rules of C operator priority, when I am minimizing the source size. Perhaps you can suppress them by compiling with the -mno-idiot option...

[Sven Schüle]

I decided to try to compile the program as first step before learning it and the program from the post of Dann Corbit does not compile correctly

I get 3 errors and 18 warning

Copying it directly from the site is even worse and I get more errors

Hi Uri,

this code is plain old K&R C but it's easy to get it compiled with an ANSI-C/C++ compiler; at least I've tried it successfully with MSVC++ 6.0.

Based on the original code on H.G.'s website,

1) replace the function header line

Code: Select all

D(k,q,l,e,J,Z,E,z,n)

by

Code: Select all

D(int k,int q,int l,int e,int J,int Z,int E,int z,int n)

, then remove the line directly below it, and

2) replace "random()" by "rand()".

Sven

[Tony van Roon-Werten]

Well, I did some tests after making micro-Max quasi Winboard compatible, (thanks, R?mi...), but it is clearly weaker then TSCP. What seems to break it is the complete neglect of King safety in the positional evaluation. In combination with the lack of check extensions and check detection in end leaves, this is quite fatal.

You might want to add some bonus for placing pieces close to the king. With 0x88 that's quite easy and small.

Just subtract the 2 squares (piece and oppo king), add 128, and lookup the value in a precalculated table[256]. You might also want to use it for your own king.

Tony

[H.G.Muller]

That's about how I do it in Usurpator (my serious engine): it checks if there is a proper Pawn fortress around the King. In particular for Pawn moves I use the method you outline, to effectively freeze the Pawns in 'line of sight' with a King that has no castling rights. For judging the move of the King it is faster to simply scan the surrounding squares in the board array. (In fact I make this scan, that is only done in the middle game, color dependent, and check only the 3 squares in the forward direction. I also use it to recognize checking moves two ply earlier than the search (which waits for the King capture) would find them.

But on the scale of micro-Max this is not so easy to program, it would easily add 50% more code. There is no piece list there, so you would somehow have to locate the King by scanning, and you would need the delta_vector table and initialize it.

A minimalistic way to do it that is more in line with the micro-Max philosophy of getting as much out of as little code as possible might be like this:

Start the iterative deepening at a depth-left 'd' of -1 in stead of 0, so that not even moves that deserve an extension are searched. If nothing is searched no fail-high cutoffs can occur, (except if King capture is detected), so the generation of moves will always continue to the very end. Add a code line to count those moves. So far, that is hardly any extra code, and the obtained count can be used as a mobility term in the evaluation before the start of iteration 0 (in which only the recaptures are searched, to see if they exceed the static evaluation, as the current version does).

In fact you might want to do this for the opponent as well, i.e. start at d=-2, and change sides at the end of every iteration with a negative d (if(d<0)k=24-k;), so that d=-1 is done for the opponent and d=-2,0,1,... are done for the side-to-move.

So far this doesn't do anything for King safety, it just implements mobility in the evaluation (and your nodes-per-second takes a big hit...). But now, if in an iteration with d<0 you treat the King as a Queen (by replacing the line t+=p<5; that terminates the rays of crawling pieces by 't+=p<5-(d<0)' so that if d<0 it effectively compares p<4 and a King with p==4 is treated as a sliding piece... These pseudo-King moves are then counted with a negative weight in the mobility, (e.g. mob+=1-3*(p==4);) meaning that if there are many open lines to the King the static evaluation score drops like a stone.

[Uri Blass]

I believe that it is probably better to add search improvement and not evaluation improvement if the target is to do it as strong as possible with the limitation of 2 mbytes.

I plan to replace the name of the variables by significant names to make the program more easy to read and I already started it.

After having significant names I may start to think about improvement in the code(without adding a lot of code).

Note that I did not understand most of MicroMax at this point of time and I do not spend a lot of time on it so I have no idea when I finish it.

Uri

[Tony van Roon-Werten]

But on the scale of micro-Max this is not so easy to program, it would easily add 50% more code. There is no piece list there, so you would somehow have to locate the King by scanning, and you would need the delta_vector table and initialize it.

A minimalistic way to do it that is more in line with the micro-Max philosophy of getting as much out of as little code as possible might be like this:

I agree. How about deciding on kingpositions before search and then incrementally score moves towards the king position ( or rather: the position the king used to be )

For deep searches this would go wrong/way off, but still the program has some clue gathering pieces for "king attacks" Accidentle checkmates also count

My point / opinion is that this kind of scoring is a long term scoring wich tends to make evaluation more lasting therefor giving a more stable search resulting in a lower effective branching factor giving a smaller search tree.

Whereas fe with piece square tables, I place a piece, wow great position -> great line-> make it mainline/fail high, you attack my piece -> my piece moves ->low scoring position -> fail low -> search new mainline/fail high -> wait a few minutes -> bye bye branching factor.

But then again, maybe I'm too focused on stable search.

Tony

[H.G.Muller]

The piece-square problem you mention seems intrinsic to any search that works through iterative deepening. No matter how you determine if a certain position is good for a piece (piece-square, (safe) mobility), if the opponent can chase you away once you get there, it is not so good after all. The chasing away is simply the positional equivalent of a recapture:

I capture QxR: great score! He captures my Queen back: ughhh!

The search only stabilizes after the entire tactical exchange is within the horizon, before that, scores are simply crap (with all the bad consequences that has for alpha-beta pruning). The most succesful way to ameliorate this problem is by QS, in general this works much better than statically predicting the outcome of the part of the tactical exchange that would be behind the horizon, or simply ignoring it.

In analogy, the problem that you sketch could be combatted by having a positional QS, where any move that 'captures' a great square (by occupying it) is not automatically awarded in end leaves with a static evaluation, but must allow the opponent the alternative of conquering the square back (by attacking it with a lower-valued piece). Of course you would only do that when positional scoring is likely to be decisive, otherwise you can be lazy and skip it.

[Tony van Roon-Werten]

The piece-square problem you mention seems intrinsic to any search that works through iterative deepening. No matter how you determine if a certain position is good for a piece (piece-square, (safe) mobility), if the opponent can chase you away once you get there, it is not so good after all. The chasing away is simply the positional equivalent of a recapture:

I capture QxR: great score! He captures my Queen back: ughhh!

The search only stabilizes after the entire tactical exchange is within the horizon, before that, scores are simply crap (with all the bad consequences that has for alpha-beta pruning). The most succesful way to ameliorate this problem is by QS, in general this works much better than statically predicting the outcome of the part of the tactical exchange that would be behind the horizon, or simply ignoring it.

In analogy, the problem that you sketch could be combatted by having a positional QS, where any move that 'captures' a great square (by occupying it) is not automatically awarded in end leaves with a static evaluation, but must allow the opponent the alternative of conquering the square back (by attacking it with a lower-valued piece). Of course you would only do that when positional scoring is likely to be decisive, otherwise you can be lazy and skip it.

Qsearch off coarse solves the big swings, but what I try to do is "soften" scores.

Bad pawn structure in front of your king and I have many pieces: give bonus, the more pieces, the more points (why, not because of a king attack, but because of the possibility of a king attack)

Rook on 7th big score: ==> possibility of a rook to go to 7th also score.

Pawn on 7th is a much bigger score than pawn on 6th. Pawn on 6th that can go to 7th ? score as 6.5th rank.

I think you get the idea. Collecting pieces near the king seems to be in the same group.

The idea behind it is that I'd rather fail low because you appear to be having some kind of king attack with 3 plies remaing to find a new fail high than discover 3plies later I'm loosing a knight in a king attack with 6 plies remaing to find a new fail high.

This way of scoring seems to "prepare" the search for score swings.

Tony

[H.G.Muller]

This might be related to an idea I so far never followed up on, to not evaluate each position as a single score, but on a two-dimensional scale. In this particular case, you could both account the score that you actually see ('pawn on 6th') as well as what it might become ('pawn on 7th').

The question of course is how to combine that with minimax. Logically the 'solid' score of a position would be that of the move with the best solid score, and the speculative score that of a (possibly different) move with the best speculative score. That would make alpha-beta difficult to implement, should you cut off if one move fails high, or should you continue searching until all scores fail high? In order not to make the search harder, you could make the pruning decisions on the solid score, and just carry along the speculative score as an extra, accepting some inaccuracy there.

So if your solid move fails high, you cut off and report for speculative score the best one you had seen so far, ignoring the fact that the skipped moves might have found a better one. (The speculative score can also be lower than the solid score.)

The speculative score could be very useful in move sorting, because although the move might be bad judged on its solid score, a high speculative score holds the promise that it suddenly turns good on deeper search, because this move leads to a leaf node that was perhaps not so quiet as you might have wished. The sorting order would depend on the window: if you need a desperate attempt to exceed alpha you would sort moves with a speculative score that could do it before moves that can't, even if their solid score is less. If beating beta seems easy, you pick a move that seems not to hold any unpleasant surprises, i.e. both the seculative and the solid score above beta, rather than a move with a better solid score but a bad speculative score below beta.

This should provide much of the search stability that you wish for: occupying a good square at the horizon is awarded the points from the piece-square table, but as long as it is not verified by deeper search that you can not be chased away there, it carries a 'might-be-chased-away' penalty in the speculative score. This would make you refrain from appointing this as principle variation, that could later be overruled. Only if the search deepens and it turns out that the piece can hold its ground on the good square, the speculative penalty disappears and it can become such.