Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old December 12th 03, 09:45 PM
Tommy
 
Posts: n/a
Default going deep...

Hello,

My chess engine (rotated bitboards, 1MNps), can, on average, with 5 secs
per move, go to level 4 with minimax, 6 with alphabeta + MO.
When I use a quiescence search it goes back to 5 on average and, because of
this, even though eveluation are more accurate, the version with quiescence
is not really stronger than the version without. I quickly attempted null
move forward pruning, but it goes to level 7, sometimes 8, and it becames
less strong.
I wonder how is it possible to go as deep as 10 or more levels.
Next week I will be ready to try transposition tables, but I doubt they will
make a *big* difference....they will in endings, but I am not sure in
middlegames.

In particular, what I would like to know is:
- is level 6 with AB+MO (with 5 secs) average, or is it bad?
- is level 5 with Quiesc normal? (going one ply less)

This week I made my evaluation function much more accurate (before it was
only doing material balance and not much more), now program plays much more
like a human (moves are more reasonable) and it improved from 1100 Elo to
1300 (FICS blitz 1 10) .... Of course this is *not *making me happy....

What am I missing? Advices? Suggestions?

Thanks a lot for all the help you are giving me,

Tommy




  #2   Report Post  
Old December 13th 03, 03:20 AM
Noah Roberts
 
Posts: n/a
Default going deep...

Tommy wrote:
Hello,

My chess engine (rotated bitboards, 1MNps), can, on average, with 5 secs
per move, go to level 4 with minimax, 6 with alphabeta + MO.
When I use a quiescence search it goes back to 5 on average and, because of
this, even though eveluation are more accurate, the version with quiescence
is not really stronger than the version without. I quickly attempted null
move forward pruning, but it goes to level 7, sometimes 8, and it becames
less strong.


Something is wrong. It should only become weaker in zugzwang positions.
Check to see if the null move is in your PV. Null move is not as
useful as a TTable.

I wonder how is it possible to go as deep as 10 or more levels.
Next week I will be ready to try transposition tables, but I doubt they will
make a *big* difference....they will in endings, but I am not sure in
middlegames.


Transposition Tables make a huge difference. First off, just the nature
of the TTable is enough to get you a ply or two. Second you use the
TTable and iterative deepening to correct your move ordering and
probably gain 2-3 ply.

In particular, what I would like to know is:
- is level 6 with AB+MO (with 5 secs) average, or is it bad?
- is level 5 with Quiesc normal? (going one ply less)


It is quite normal for quiescence to slow you down. It is of course
still possible that your q-search is broken since I can't tell without code.

This week I made my evaluation function much more accurate (before it was
only doing material balance and not much more), now program plays much more
like a human (moves are more reasonable) and it improved from 1100 Elo to
1300 (FICS blitz 1 10) .... Of course this is *not *making me happy....


The improvement is not making you happy?

Did you think it would be easy to come up with a good evaluator that was
both fast and strong?

It is hard to get your engine running efficiently enough to get 10+ ply.
Mine sees 6 in a reasonable amount of time with AB, Move ordering, a
ttable, and iterative deepening.

One thing you might be able to do is only evaluate material unless the
difference is beneath some threashold, then do a full evaluation. You
can get more stages than 2 also. For instance, if a quick eval is
within the ab window or only out by a small amount you reevaluate with
more accuracy but if more accuracy can't put it inside the window then
no need to do it. I plan on implementing this strategy in my own engine
but have not yet.

NR

  #3   Report Post  
Old December 13th 03, 08:15 AM
Werner Mühlpfordt
 
Posts: n/a
Default going deep...

In article ,
"Tommy" writes:

This week I made my evaluation function much more accurate (before it was
only doing material balance and not much more), now program plays much more
like a human (moves are more reasonable) and it improved from 1100 Elo to
1300 (FICS blitz 1 10) .... Of course this is *not *making me happy....


From the speed and depth you describe you should be ~1600 FICS without
Nullmove, but with quiescence. If your qsearch did not really _boost_
your rating, something in severely wrong.

Two questions:
- how many % of your nodes do you spend in q-search?
- with the rating you presently have, you program must make some
ugly blunders still. Can you give an example for such? This
may help to track down the area that needs investigation.
- wild guess: may it be your q-search does not yet do decent MO?
Does it prune recaptures that do no bring you back to alpha?

I doubt that anything you do to the eval will help a lot,
since there seems something wrong within search.

Werner
  #4   Report Post  
Old December 13th 03, 12:41 PM
Tommy
 
Posts: n/a
Default going deep...


"Noah Roberts" wrote

Something is wrong. It should only become weaker in zugzwang positions.
Check to see if the null move is in your PV. Null move is not as
useful as a TTable.


Probably it is wrong, I did the Null-Move very quickly just to test it....

Transposition Tables make a huge difference. First off, just the nature
of the TTable is enough to get you a ply or two. Second you use the
TTable and iterative deepening to correct your move ordering and
probably gain 2-3 ply.


Wow, that is much more than I expected. This is good news ;-)

It is quite normal for quiescence to slow you down. It is of course
still possible that your q-search is broken since I can't tell without

code.

Yes, of course, you would need the code....

I have implemented the q-search by producing captures only + promotions.
It also checks for checks and in that case produces all possible moves for
just one ply.
I have also implemented a standing-pat.
I tested and seems to work, but it does not make my program stronger.....

This week I made my evaluation function much more accurate (before it

was
only doing material balance and not much more), now program plays much

more
like a human (moves are more reasonable) and it improved from 1100 Elo

to
1300 (FICS blitz 1 10) .... Of course this is *not *making me happy....


The improvement is not making you happy?


Well, the improvement is certainly making me happy, but 1300 is a bit
disappointing...

Did you think it would be easy to come up with a good evaluator that was
both fast and strong?


No, certainly not!
My program was doing 1M nodes per second, now it is doing 600 and it gained
only 200 Elo points!!!

It is hard to get your engine running efficiently enough to get 10+ ply.
Mine sees 6 in a reasonable amount of time with AB, Move ordering, a
ttable, and iterative deepening.


I see... how many Elo points can an engine acheive with 6 plies?

One thing you might be able to do is only evaluate material unless the
difference is beneath some threashold, then do a full evaluation. You
can get more stages than 2 also. For instance, if a quick eval is
within the ab window or only out by a small amount you reevaluate with
more accuracy but if more accuracy can't put it inside the window then
no need to do it. I plan on implementing this strategy in my own engine
but have not yet.


That is a good idea!

Thanks a lot,

Tommy



  #5   Report Post  
Old December 13th 03, 01:58 PM
Alexander Belov
 
Posts: n/a
Default going deep...

Maybe better idea to make fast but imprecise evaluation of positions
occured from one position with some moves and reevaluate with
full precision for several top (say 3 top) and thus "most promising" moves.

"Tommy" wrote in message
...

"Noah Roberts" wrote
One thing you might be able to do is only evaluate material unless the
difference is beneath some threashold, then do a full evaluation. You
can get more stages than 2 also. For instance, if a quick eval is
within the ab window or only out by a small amount you reevaluate with
more accuracy but if more accuracy can't put it inside the window then
no need to do it. I plan on implementing this strategy in my own engine
but have not yet.


That is a good idea!

Thanks a lot,

Tommy





  #6   Report Post  
Old December 13th 03, 04:17 PM
Tommy
 
Posts: n/a
Default going deep...

"Werner Mühlpfordt" wrote in message
...


From the speed and depth you describe you should be ~1600 FICS without
Nullmove, but with quiescence. If your qsearch did not really _boost_
your rating, something in severely wrong.


Umh....

Two questions:
- how many % of your nodes do you spend in q-search?


Well, thanks for asking...
I have now amended the code so that I can have what you ask...
It is amazing: 80% of the nodes are in the q-search!

All the times that it reaches the maximum depth for the current iteration
alphabeta calls "QuiescenceEvaluation", that is why it does 80% of nodes,
"leaves" are more numerous than nodes.... Also beacuse a few of these leaves
are not real leaves and will actually be tried at deeper depths (until a
stand pat or a quiet node).

- with the rating you presently have, you program must make some
ugly blunders still. Can you give an example for such?


Well, it depends on the opponent.
With opponents 1500 Elo it does not make bad blunders. It usually loses
from opponents 1300 but mainly due to the poor openings and poor endings.
Not major mistakes!

However, when the opponent is really strong my computer program starts
playing horrible chess and it also becomes suicidal !!! And... it is a pain
to watch!
Have a look at this game against Crafty, this should clarify....

[Event "Computer chess game"]
[Site "******"]
[Date "2003.12.13"]
[Round "-"]
[White "tomchess"]
[Black "Crafty-19.3"]
[Result "0-1"]
[TimeControl "120+10"]

1. Nc3 e5 2. e3 Nf6 3. Nf3 e4 4. Ng5 d5 5. Qe2 Be7 6. Qb5+ Nc6 7. Nxf7 Kxf7
8. Nxe4 Nxe4 9. d3 Bb4+ 10. c3 Nxc3 11. bxc3 Bxc3+ 12. Bd2 Bxa1 13. e4 Re8
14. Be2 Nd4 15. Bh5+ g6 16. Bxg6+ hxg6 17. Qb1 dxe4 18. dxe4 Qh4 19. O-O
Ne2+ 20. Kh1 Qxh2+ 21. Kxh2 Rh8+ 22. Bh6 Rxh6#
{Black mates} 0-1


When it plays not so strong opponents it does not behave so badly, this is a
game againsta a 1700 Elo point opponent....
Ok tomchess loses, but in the endings, and.... I do not really care for now!
(this game is a bit atypical since this time tomchess plays better openings
that the opponent, this usually never happens!)

[Event "ICS rated blitz match"]
[Site "freechess.org"]
[Date "2003.12.13"]
[Round "-"]
[White "tomchess"]
[Black "********"]
[Result "0-1"]
[WhiteElo "1246"]
[BlackElo "1704"]
[TimeControl "60+19"]

1. Nc3 e6 2. d3 d5 3. e4 Nf6 4. e5 Nfd7 5. Nf3 c5 6. Bg5 Be7 7. Bxe7 Kxe7
8. Qc1 Re8 9. Qg5+ Kf8 10. Be2 Qxg5 11. Nxg5 h6 12. Nf3 a6 13. d4 Nc6 14.
dxc5 Ncxe5 15. Nxe5 Nxe5 16. f4 Ng6 17. Bf3 Nxf4 18. g3 Ng6 19. Rd1 Bd7 20.
Bh5 Ne5 21. Be2 g6 22. a3 Kg7 23. b3 Rac8 24. b4 Bc6 25. Rd4 Red8 26. h3 f6
27. g4 Nf7 28. Bf3 Ne5 29. Bg2 Nc4 30. Rh2 Nxa3 31. Bf3 Nb5 32. Nxb5 Bxb5
33. Rhd2 Re8 34. Kf2 Bc6 35. Re2 e5 36. Rd1 d4 37. Bxc6 Rxc6 38. Rxd4 Kf7
39. Rd1 Re7 40. Red2 f5 41. Rd8 Rce6 42. gxf5 gxf5 43. Rh8 Kg7 44. Ra8 Rg6
45. Rb8 f4 46. Rdd8 Kf6 47. Rbc8 Kf5 48. Rd6 Rxd6 49. cxd6 Rd7 50. Rf8+ Ke4
51. Rf6 h5 52. Rh6 Kd5 53. Rxh5 Rxd6 54. c4+ Ke4 55. Rh7 Rd4 56. b5 Rxc4
57. Rxb7 Rc2+ 58. Ke1 axb5 59. Rb6 Rh2 60. Rh6 Ke3 61. Kd1 Rb2 62. Rh5 Ke4
63. Kc1 Rh2 64. Rh7 f3 65. Rh4+ Ke3 66. Rh5 e4 67. Rd5 f2 68. Rf5 Ke2 69.
Rf6 Rxh3 70. Rf4 e3 71. Kc2 Rf3 72. Rb4 Rf5 73. Rb1 f1=Q 74. Rxf1 Kxf1 75.
Kc1 Rd5 76. Kb2 e2 77. Kc1 e1=Q+ 78. Kb2 Qe3 79. Ka1 Rd2 80. Kb1 Qe1#
{tomchess checkmated} 0-1


and when it plays with beginners it of course goes straight to mate and it
is dangerous:

[Event "ICS rated blitz match"]
[Site "freechess.org"]
[Date "2003.12.11"]
[Round "-"]
[White "tomchess"]
[Black "********"]
[Result "1-0"]
[WhiteElo "1226"]
[BlackElo "1068"]
[TimeControl "60+8"]

1. d4 f6 2. e4 c6 3. Bd2 h5 4. Be2 Rh6 5. Bxh5+ Rxh5 6. Qxh5+ g6 7. Qxg6#
{******** checkmated} 1-0


This
may help to track down the area that needs investigation.
- wild guess: may it be your q-search does not yet do decent MO?


Not very good, it does something very similar to "least valuable attacker,
most valuable victim"....

Does it prune recaptures that do no bring you back to alpha?


what do you mean? A standing pat?

if(player==MINIMAX_WHITE){
alpha=max(alpha,value);
if(value=beta) return value;
}else{
beta=min(beta,value);
if(value=alpha) return value;
}

that is what I do... here expressed it in minimax+alphabeta version (not in
negamax+alphabeta, I find the first version clearer to talk about!).


I doubt that anything you do to the eval will help a lot,
since there seems something wrong within search.


Yeah, probably... I hope to discover what....

Thanks a lot for you help! I appreciate!

Tommy




  #7   Report Post  
Old December 13th 03, 06:32 PM
Werner Mühlpfordt
 
Posts: n/a
Default going deep...

In article ,
"Tommy" writes:
"Werner Mühlpfordt" wrote in message
...
Does it prune recaptures that do no bring you back to alpha?


what do you mean? A standing pat?

Not exactly. The reasoning is like this: If the static eval of a
node is low enough that the material captured in a move will
still not make the eval reach alpha, the move will not even
be executed. Example: your static says you're down a rook,
while alpha says you're not worse than down a pawn. Then you
can forget about captures of pawns, bishops, and knights.
Without moving. Pawn promotion while capturing a queen is a
different story ;-)

Werner
  #8   Report Post  
Old December 14th 03, 01:04 PM
Alexander Belov
 
Posts: n/a
Default going deep...

Something wrong with this logic.
In this situation your opponent pawn can attack your queen.
If you consider capturing this pawn, this position can become
better than alpha, because you remove the treat (depending
on q-search consequencies) while if you not consider
capturing this pawn you can decide that your opponent leads
in this position because it can capture you queen. So you
just drop a chance to come into the normal position.
(All this depends on evaluation function).

"Werner Mühlpfordt" wrote in message
...
Not exactly. The reasoning is like this: If the static eval of a
node is low enough that the material captured in a move will
still not make the eval reach alpha, the move will not even
be executed. Example: your static says you're down a rook,
while alpha says you're not worse than down a pawn. Then you
can forget about captures of pawns, bishops, and knights.
Without moving. Pawn promotion while capturing a queen is a
different story ;-)

Werner



  #9   Report Post  
Old December 14th 03, 06:26 PM
David Richerby
 
Posts: n/a
Default going deep...

Tommy wrote:
I see... how many Elo points can an engine acheive with 6 plies?


How long is a piece of string? It depends on how good your static
evaluation is.


Dave.

--
David Richerby Carnivorous Dangerous Car (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a high-performance luxury car but
it could explode at any minute and it
eats flesh!
  #10   Report Post  
Old December 14th 03, 07:07 PM
Werner Mühlpfordt
 
Posts: n/a
Default going deep...

In article ,
"Alexander Belov" writes:
Something wrong with this logic.
In this situation your opponent pawn can attack your queen.

I assume you mean: actually does attack the queen. The mere
possibility to do so would not be seen in q-search (at least
typically).

If you consider capturing this pawn, this position can become
better than alpha, because you remove the treat (depending
on q-search consequencies) while if you not consider
capturing this pawn you can decide that your opponent leads
in this position because it can capture you queen. So you
just drop a chance to come into the normal position.

Just the fact that my queen is attacked does not affect
the static eval that I use. Or maybe: not yet. I carry on
with q-search in such a position, and don't evaluate.

(All this depends on evaluation function).

Very true. If static eval does contain terms like "if your
queen is attacked by a pawn, then subtract val(q)-val(p)",
then the described logic is not applicable.

With an eval that does not contain attacks, the situation
might be like this: you are a rook down statically (your
opponent has just captured a rook), but already found a
recapture that puts alpha to -1 only (because it takes
the rook with a pawn that finally gets captured).
In this situation, don't even consider a move that does not
capture at least a rook.

Werner
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 06:31 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017