Winboard Forum

Hi,

I'm developing a chess engine (in java) which is not using that algorithm of Shannon (for the evalutation of a setting) nor using any alpha-beta or any other tree. Yes, it looks only one ply deep. Ok, 2 to be able to see if it got check or so, but not more.
Now I do not have so much chess knowledge so I was wondering if there's anyone out there who would like to evaluate the playing of my chess program. I'm not looking for comments like "it sucks" or "rubbish" as I already know that myself. More like: focus on this or that, or it behaves when this or that.
It can be downloaded from: http://www.vanheusden.com/pos/
It works with xboard and should work with winboard as well altough I never really tried that.

You should tell us why you are not using the tree aproach which has proven to be powerful over decades of chess programming.

If you are just looking for a way to make your engine stronger: read about alpha-beta etc. and implement it. Many engine authors before you have tried other aproaches than brute force tree search, with very limited success.

If you have a good reason not to implement alpha-beta (e.g. the engine is only a by-product of your attempts to write a heuristic good-move-generator for move ordering) tell us about your intentions.

Onno Garms wrote:You should tell us why you are not using the tree aproach which has proven to be powerful over decades of chess programming.

Because thousands of other people have already implemented such chess programs. I found that nog much of a challenge.

If you are just looking for a way to make your engine stronger: read about alpha-beta etc. and implement it.

No, then my program would just be one of the few.

Many engine authors before you have tried other aproaches than brute force tree search, with very limited success.

That others have also tried doesn't mean my ideas won't work either
Well clearly they don't yet but that might change in the near future. Am already implementing a different version which plays stronger already. It only needs big iron.

Hi Folkert,

have you implemented a WinBoard interface for your engine, so that you can let it play test games or tournaments against other such engines? If not, I would suggest to do so. Then select a few opponents (probably start with weakest possible ones), perhaps based on the WBEC rating list, download them via WBEC, and let your engine play some (better: many) games with short time control. See what happens.
I'm pretty sure you are also prepared for questions like these:
- How to find a mate in N?
- How to ensure that your engine makes progress in a clearly won position where the only goal is to mate the enemy's lone king?
- How to find tactical lines starting with a sacrifice and winning material after, say, 6 moves (not quite much today)?

Good luck for your approach! Let us hear about your progress.

Sven

Hi again,

sorry for not having followed your link before, now I did. So WinBoard support is there. Obviously already a sufficient number of games has been played on freechess.org to estimate the rating at about 700 for standard chess.

I'm afraid this is too weak for anybody here to give some hints for any improvements. Improving your engine from 700 to, say, 1500 would mean that the "1500" version would win >99% of all games against your current "700" version, but it would still be within the lowest 10% of the WBEC rating list.

Have you analyzed the games to find out the most frequent reasons for losing? I did not try it because I have no working java installation but I guess your engine simply loses material very early, and it will overlook trivial mating combinations quite often.

Sven

I downloaded the Win32 exe from Jim's site and played four quick test games against my own engine. Check your mailbox, please.

Sven

I have looked at a few games of POS, as POS participated in Sergio Martinez' qualifier tourney for La Liga, where my engine micro-Max also participated.

From that I got the impression that POS was merely capturing the most-valuable piece on the board (not caring if it was defended) and if nothing could be captured, just played the first move produced by the move generator.

When I was a student (around 1976) I wrote a non-Shannon blitz chess program, (it used only 3 sec of CPU time for an entire game on a ~1MHz PDP-11) and my recollection is that that program was producing significantly better moves than POS. (It probably would not win against POS, as its only purpose was to drive the Human opponent 'through the flag', or capture its King if he did not pay enough attention (according to good blitz tradition, he was not warning if he put his opponent in check... )

The algorithm was very simple: it counted the number of attackers and defenders for each square by running the move generator for each side. As an estimate for the SEE on the square it then took the value of the victim there if there were more attackers then defenders, or the difference of the attacker and the victim if there were equal or more defenders. A move was then scored as the SEE value of the TO-square plus the opponent's SEE value on the FROM-square. To that were added piece-square points for Paws and light pieces from a shared piece-square table (basically containing minus the distance to the center, as in uMax).

It seems that POS doesn't even go as far as that, as I saw it capture a defended Pawn with its Queen if a Pawn happened to be the highest piece under attack. So suggestion for improvement #1:

Do not take lower pieces with higher pieces if the former are defended!

I have revived my ancient non-Shannon blitz program, and posted it here. Basically it is a Joker clone, where I replaced the call to Search() that should come up with the move to play by the algorithm described above. As it uses Joker's move generator to pick a move from, which is pseudo-legal w.r.t. King moves, it might do illegal moves.

It did not really have a name before, so I decided to call it NEG. This is an acronym for 'Niet Erg Goed', (Dutch for Not Extremely Good).

When I played POS against NEG, POS was really chopped off the board. But as NEG doesn't know about checkmate, let alone stalemate, the game ended in a stalemate in the KQQRK end-game.

My earlier impression is thus vindicated: even for a non-Shannon program that only thinks one ply ahead, POS doesn't do a very good job. Counting number of attackers and defenders already does a lot better...

The routine that decides on the move is this:

Code: Select all

void NEG(int Color, int lastply)
{
    char attacks[128], LVA[128];
    int my_moves = msp;
    int i, j, k, from, to, piece, victim, Score, BestScore, BestMove;

    for(i=0; i<128; i++) { attacks[i] = 0; LVA[i] = 100; }

    move_gen(Color, lastply, 1);

    pseudo_gen(Color, attacks, LVA); /* count attacks */

    pseudo_gen(COLOR-Color, attacks+8, LVA+8); /* count defends */


    BestMove = -1; BestScore = -INF;

    for(i=my_moves; i<msp; i++)
    {
        from = stack[i]>>8 & 0x77;
        to   = stack[i] & 0x77;
        piece = board[from];
        victim = board[to];
        Score = qval[victim-WHITE];
        if(attacks[to] <= attacks[to+8]) Score -= qval[piece-WHITE];

        if(attacks[from+8] > attacks[from]) Score += qval[piece-WHITE]; else
        if(LVA[from+8] < qval[piece-WHITE])
            Score += qval[piece-WHITE] - LVA[from+8];

        Score *= PVAL;

        if(kind[piece-WHITE] < ROOK) /* P, N and B */
            Score += CentrPts[to] - CentrPts[from];

        if(piece = Color - WHITE) Score -= 50; /* King */

        Score += rand()>>9 & 15;

        if(Score > BestScore)
        {
            BestScore = Score;
            BestMove = i;
        }
    }

    RetMove = stack[BestMove];

    msp = my_moves;
    return;

}


pseudo_gen() is a routine that I had to specially write for NEG that counts the number of pseudo-moves (i.e. including self-captures) in the array passed to it as second argument, and the least-valuable attacker (P=1, N,B=3, etc.) of each square in the second argument. My initial try was to use the normal move generator for this, but that was a mistake: it thought all pieces were undefended. The new routine doesn't do X-rays, I left that for NEG 0.2...

The game I reported about actually was one for a version of NEG that had a bug: In stead of counting defenders I was counting attackers twice...

A game by the corrected NEG (which is now on my website) is this:

[Event "Computer chess game"]
[Site "FOM-RHKA8J2A5WY"]
[Date "2007.05.27"]
[Round "-"]
[White "POS v1.14 / Mon Apr 30 22:30:29 2007"]
[Black "neg01"]
[Result "0-1"]
[TimeControl "40/300"]

1. f3 Nf6 2. c3 Nc6 3. Qa4 d5 4. Kd1 Be6 5. Kc2 g6 6. Kb3 Bg7 7. Ka3 b6 8.
Qxc6+ Kf8 9. Qa4 c5 10. Kb3 Qd7 11. Kc2 Qxa4+ 12. Kd3 c4+ 13. Kd4 Ng4#
{Black mates} 0-1

[diag]r4k1r/p3ppbp/1p2b1p1/3p4/q1pK2n1/2P2P2/PP1PP1PP/RNB2BNR w - - 0 14[/diag]

So another remark about the play of POS: don't attempt King strolls through the center in the early middle game! Or even an opponent that doesn't know what checkmate is might accidentally checkmate you!

Another one, with a more typical result:

[Event "Computer chess game"]
[Site "FOM-RHKA8J2A5WY"]
[Date "2007.05.27"]
[Round "-"]
[White "POS v1.14 / Mon Apr 30 22:30:29 2007"]
[Black "NEG 0.1b"]
[Result "1/2-1/2"]
[TimeControl "40/300"]

1. f3 Nc6 2. c3 Nf6 3. Kf2 e5 4. Kg3 Bc5 5. Qa4 b6 6. Nh3 d5 7. Qxc6+ Ke7
8. Qxa8 a5 9. Kh4 Bf5 10. Kg5 Qxa8 11. Kxf5 g6+ 12. Kg5 Ne4+ 13. Kh4 Nd6
14. Kg3 f5 15. Ng5 Bd4 16. Kh3 Bc5 17. Kg3 c6 18. h3 Bd4 19. Kh2 Bc5 20.
Kg3 b5 21. Rh2 Kd7 22. b3 Nc4 23. d3 Ne3 24. Kf2 Nc4+ 25. Ke1 Nb6 26. Kd2
Nc4+ 27. Ke1 Nd6 28. Kd1 d4 29. Kc2 Qe8 30. Kb2 Qf8 31. Nd2 f4 32. Kc2 Nf5
33. Kb1 dxc3 34. Nde4 Bd4 35. Nf6+ Kc8 36. Ne6 Qxf6 37. Kc2 Qxe6 38. Rh1 c5
39. Rb1 b4 40. g4 Nd6 41. Ra1 Nf5 42. Kd1 Ne7 43. Ke1 Nd5 44. e4 Ne3 45.
Ke2 Nd5 46. Kd1 Ne3+ 47. Ke2 Qe8 48. Ke1 Kd8 49. Rg1 Kd7 50. g5 Nf5 51. Rg4
Nd6 52. Rh4 Nf5 53. Rxh7+ Kd6 54. Rb7 Ng3 55. Rb6+ Ke7 56. Ra6 Qb5 57. Rxg6
Qb7 58. Rg7+ Ke8 59. Rxb7 Rg8 60. Rb8+ Kf7 61. Rb7+ Kg6 62. Rd7 Kxg5 63.
Rd5 Nf5 64. Rd7 Ne3 65. Rh7 Kg6 66. Rg7+ Kxg7 67. Be2 Kh7 68. a4 Rg6 69.
Ra2 Rf6 70. Ra1 Ra6 71. h4 Rg6 72. Bd2 cxd2+ 73. Kxd2 Bxa1 74. Kc1 Bd4 75.
Kd2 Rg1 76. h5 Rg2 77. Kc1 Rxe2 78. Kb1 Rg2 79. Kc1 Re2 80. Kb1 Kg8 81. h6
Rd2 82. h7+ Kxh7 83. Kc1 Rxd3 84. Kb1 Rxb3+ 85. Ka2 Rc3 86. Kb2 Rc4+ 87.
Kb3 Rc2
{Stalemate} 1/2-1/2

[diag]8/7k/8/p1p1p3/Pp1bPp2/1K2nP2/2r5/8 w - - 0 88[/diag]

Hi,
I also have done a program in the past, which was looking only one ply ahead, and counting attackers and defenders, evaluating each possible exchange (like a SEE). As far as I remember, I also included positional terms (center control, mobility, number of defended pieces for each side, number of attacked pieces for each side...) so that the program was able to play not that bad in blitz as you noticed Gerd. The style of play was also very agressive, alway trying to attack a piece of high value or an undefended piece. But of course, in long time play it was not a good oponent !
Welcome here, and good luck with your original chess engine, Folkert!
Yves

Yes, a SEE would be better, and in the end that is what I did in 1974. Now I use counting, and if you see NEG play it is obvious that this has a very common case where it fails: NEG happily puts its pieces on empty squares attacked by the opponent's Pawns. Just because he thinks he is sufficiently defended.

Using only the LVA information allows you to do better than that. In stead of assuming you win the full value of the victim if you have more attacksers to the square than there are defenders, you should only win min(victim, victim + lowest_defender - attacker). So non-captures (which have victim=0) would score negative if the expose the piece to a lower-valued attacker. In NEG 0.1 they always score zero (i.e. only positional), even if they blunder away material. But that is still not enough to lose to POS...

It turns out NEG 0.1b scored about 50% against POS 1.14, as it did too many illegal moves. So I fixed that, and remove all illegal moves from the move list before scoring them.

The resulting NEG 0.1c beats POS 1.14 by 61% over 50 games. Not bad for a program that does not know what checkmate is! Typically it strips POS completely bare, with about 80% of its own material left. It must than hope for an accidental checkmate before stalemate or 50-move draws occur.

Nevertheless, POS was able to win a couple of games. If it gets its Queen behind NEG's lines, it can reverse the roles, as NEG has no idea what defending is.

Folkert van Heusden wrote:Hi,

I'm developing a chess engine (in java) which is not using that algorithm of Shannon (for the evalutation of a setting) nor using any alpha-beta or any other tree. Yes, it looks only one ply deep. Ok, 2 to be able to see if it got check or so, but not more.
Now I do not have so much chess knowledge so I was wondering if there's anyone out there who would like to evaluate the playing of my chess program. I'm not looking for comments like "it sucks" or "rubbish" as I already know that myself. More like: focus on this or that, or it behaves when this or that.
It can be downloaded from: http://www.vanheusden.com/pos/
It works with xboard and should work with winboard as well altough I never really tried that.

I once wrote you a bug report a while ago, but your answer
was so insufficient and egozentric that I did not care to
bother you again.
You should mention that POS at least in versions up
to 1.12 _doesn't_ support _any_ time controls which makes
it nearly unusable for testing. I don't know if that has changed
for the last version? Still I spent lots of hours of
cpu time with it...
My advice is make it first complying with standard game rules
as time management for at least two time controls.
Then it should at least has some ideas of how to develop pieces
and how not to blunder Queens or pieces for nothing.
Even a one or two ply search should reveal that is no good idea
to sack a Q vs. pawn in move 5.
It should know the value of all of the piece types even in a
completely different search approach.

Guenther

A few examples you know already.
POS always moved in fractions of a second as reported...

[Event "RWBC PSWBTM RT19"]
[Site "ESPRESSO"]
[Date "2007.01.28"]
[Round "2.2"]
[White "Xadreco_56"]
[Black "POS_112JA"]
[Result "1-0"]
[TimeControl "40/900"]
[Annotator "4. +0.72"]
[Number "9"]

1. d4 d5 2. c4 dxc4 3. e4 Nc6 4. d5 {+0.72/6} Ne5 5. Nc3 {-0.80/5} Nf3+ 6.
Nxf3 {+0.33/5} Qxd5 7. Nxd5 {+11.18/5} Kd7 8. Nb6+ {+9.82/6} Kc6 9.
Nxa8 {+12.20/5} Nf6 10. Qd8 {+13.21/5} Nxe4 11. Bxc4 {+998.80/5} Bg4 12.
Qxc7# {+999.60/5}
{White mates} 1-0

[Site "ESPRESSO"]
[Date "2007.01.28"]
[Round "2.2"]
[White "POS_112JA"]
[Black "Xadreco_56"]
[Result "0-1"]
[TimeControl "40/900"]
[Annotator "3... +1.98"]
[Number "10"]

1. e4 c5 2. Nf3 Nc6 3. Nc3 a6 {+1.98/6} 4. Nh4 Ra7 {+0.10/5} 5. Qh5
Nb4 {+0.97/6} 6. Qxf7+ Kxf7 {+9.05/6} 7. Bc4+ e6 {+8.13/6} 8. Bxe6+
dxe6 {+10.42/6} 9. Nf3 Nxc2+ {+13.47/6} 10. Kf1 Nxa1 {+12.45/5} 11. Ne5+
Kf6 {+13.47/6} 12. Ng4+ Ke7 {+12.45/5} 13. Nd5+ exd5 {+17.54/6} 14. Ne3
dxe4 {+17.54/6} 15. Nd5+ Qxd5 {+22.90/6} 16. a4 Qc4+ {+29.07/6} 17. Kg1
Qxc1# {+999.60/6}
{Black mates} 0-1

Thank you all for your elaborate replies!

Guenther Simon wrote:I once wrote you a bug report a while ago, but your answer was so insufficient and egozentric that I did not care to bother you again.

I am shocked; that so doesn't sound like me.
But if really did that then I'm very sorry and I apologize.

I made yet another engine: Ram 0.0. It is the 'random mover', which randomly selects a move to play from one of the legal moves (i.e. all with equal probability).

Over 50 games POS scored 75% against it. Ram was able to win a couple of games, though... Like this one:

[Event "Computer chess game"]
[Site "FOM-RHKA8J2A5WY"]
[Date "2007.05.28"]
[Round "1.1"]
[White "Ram 0.0"]
[Black "POS 1.14"]
[Result "1-0"]
[TimeControl "300"]
[Number "19"]

1. d3 Nf6 2. f4 h6 3. h4 c6 4. c4 Qa5+ 5. Nc3 Kd8 6. a3 Na6 7. f5 Kc7 8.
Rb1 Kd6 9. e4 Ke5 10. Ra1 Kd4 11. c5 Ke5 12. d4#
{White mates} 1-0

And to Guenther: don't bother to spend CPU time testing NEG 0.1 or Ram! They don't support any time controls either, and always move instantly (i.e. in a few micro-seconds).

H.G.Muller wrote:I made yet another engine: Ram 0.0. It is the 'random mover', which randomly selects a move to play from one of the legal moves (i.e. all with equal probability).
Over 50 games POS scored 75% against it. Ram was able to win a couple of games, though... Like this one:

[Event "Computer chess game"]
[Site "FOM-RHKA8J2A5WY"]
[Date "2007.05.28"]
[Round "1.1"]
[White "Ram 0.0"]
[Black "POS 1.14"]
[Result "1-0"]
[TimeControl "300"]
[Number "19"]

1. d3 Nf6 2. f4 h6 3. h4 c6 4. c4 Qa5+ 5. Nc3 Kd8 6. a3 Na6 7. f5 Kc7 8.
Rb1 Kd6 9. e4 Ke5 10. Ra1 Kd4 11. c5 Ke5 12. d4#
{White mates} 1-0

And to Guenther: don't bother to spend CPU time testing NEG 0.1 or Ram! They don't support any time controls either, and always move instantly (i.e. in a few micro-seconds).

Hi,

I'm going to test this as well. That it looses so much from even a random mover is not what I would expect. Especially since it wins quiet a few games on fics: aprox. 13% and 2% draw.
Graph can be found here: http://www.vanheusden.com/pos/POS-blitz-at-freechess.org.png

You also wrote:

Typically it strips POS completely bare, with about 80% of its own material left.

That's behaviour from pos I expected: it must sound silly but I try to let it focus more on strategic (e.g. blocking) then on killing .

Well, POS did not lose very many games. I just noticed 2 in the first 50. Most of the score of Ram comes from 50-move draws and stalemates. Unfortunately the pgn file is not so easy to scan for checkmates by Ram, as they alternate colors. I could send you the pgn, if you wanted, but I guess you can easily test it yourself. A ramdom mover is not so difficult to make. This one was even not perfect as it doesn't do under-promotions.

Your last remark is puzzling. How could it possibly 'strategic' to do almost exclusively King moves, and position the King in the center?

H.G.Muller wrote:Well, POS did not lose very many games. I just noticed 2 in the first 50. Most of the score of Ram comes from 50-move draws and stalemates. Unfortunately the pgn file is not so easy to scan for checkmates by Ram, as they alternate colors. I could send you the pgn, if you wanted, but I guess you can easily test it yourself. A ramdom mover is not so difficult to make. This one was even not perfect as it doesn't do under-promotions.
Your last remark is puzzling. How could it possibly 'strategic' to do almost exclusively King moves, and position the King in the center?

"non-material-oriented" might be a better description

I'm currently running 100 games with the current non-published version to see what is going wrong.

I'm puzzled by the observation that it moves its king to the center. I have no idea what is causing that.

[... half an hour later or so...]

I'm seeing different results: when I let pos play against itself with one in random-move mode (--brain-mode random), the normal version wins 100% with white and 96% with black.