in check test

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

in check test

Postby Anonymous » 07 Jul 2005, 18:17

hi everyone,

quite a few sites tell me to forget about the in check test during search, but there's a couple of things i dont entirely get. i understand that i for a certain move, if one of the children nodes is a move that allows the king to be captured, then the search for that move can be stopped. but does that mean that we have to do incheck test for the leaf nodes? and then i don't really see the gain of leaving out the test when i implement iterative deepening. i'm sure there's something quite obvious i don't see here :) thx to anyone that enlightens me hehe

also, as an aside, is there a good way to generate valid castling moves? do we need to do the incheck test for every square the king will pass by? i can't seem to read about a good procedure anywhere.

Thanks for the help!!
Wing, newbie :)
Anonymous
 

[Moderation]

Postby Volker Pittlik » 07 Jul 2005, 18:24

Please read http://volker-pittlik.name/wbforum/viewtopic.php?t=3028 and change your username ASAP.

Volker
User avatar
Volker Pittlik
 
Posts: 1026
Joined: 24 Sep 2004, 10:14
Location: Murten / Morat, Switzerland

Re: in check test

Postby Pradu » 07 Jul 2005, 18:47

quite a few sites tell me to forget about the in check test during search.


This is probalby to improve the speed of the engine. Since you don't search many of the generated moves, you will have no need to check if they are legal or not until they are actually made in the search.

but does that mean that we have to do incheck test for the leaf nodes


Yes - we don't want the leaf node to be an illegal position.

and then i don't really see the gain of leaving out the test when i implement iterative deepening


Can you clarify this statement?

is there a good way to generate valid castling moves


What I do is call a seperate function called generateCastlingMoves().
If the board position shows the ability to castle for the side, a castling move that we define hard coded for each side is then just added to the move list.

do we need to do the incheck test for every square the king will pass by? i can't seem to read about a good procedure anywhere.


Yes you do. Using bitboards is one way of tackling the problem.
Last edited by Pradu on 10 Jul 2005, 19:53, edited 1 time in total.
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA

Re: in check test

Postby Anonymous » 07 Jul 2005, 20:06

Sorry about that, Volker
not used to enter a full name as a username in forums.. usually there's a "display name" of some sort
My apologies...


and then i don't really see the gain of leaving out the test when i implement iterative deepening


Can you clarify this statement?
[/quote]

What i mean is that, during iterative deepening, i will start at ply 2, then 3, 4 etc... And for each of those, i will have to evaluate the leaf nodes with incheck(). So essentially, I will have evaluated incheck() for every single node at every ply i've searched at the end anyways.
Anonymous
 

Re: in check test

Postby Tord Romstad » 07 Jul 2005, 23:17

Wing Lee wrote:hi everyone,

quite a few sites tell me to forget about the in check test during search,

Which sites are these? It seems like a bad idea to me, and I am pretty sure almost all programs do an in check test at all nodes. I don't see any good reason to skip the test. Testing whether the side to move is a very cheap operation.

also, as an aside, is there a good way to generate valid castling moves? do we need to do the incheck test for every square the king will pass by? i can't seem to read about a good procedure anywhere.

Just do it in whatever way you think is most natural, and don't worry about speed. Castling moves are just a tiny minority of all the moves your program generates during the search, and even if you generate them in a very slow and inefficient way it will not slow down your program noticably. FWIW, here is my code for generating castling moves:

Code: Select all
  if(!SearchStack[Ply].check) {
    if(OO_POSSIBLE(Side)) {
      int e1=E1+Side*A8, f1=F1+Side*A8, g1=G1+Side*A8;
      if(Board[f1]==EMPTY && Board[g1]==EMPTY &&
         !is_attacked(f1, XSide) && !is_attacked(g1, XSide))
        (ms++)->move = (KING<<17)|(e1<<7)|g1;
    }
    if(OOO_POSSIBLE(Side)) {
      int e1=E1+Side*A8, d1=D1+Side*A8, c1=C1+Side*A8, b1=B1+Side*A8;
      if(Board[d1]==EMPTY && Board[c1]==EMPTY && Board[b1]==EMPTY &&
         !is_attacked(d1, XSide) && !is_attacked(c1, XSide))
        (ms++)->move = (KING<<17)|(e1<<7)|c1;
    }
  }

'Side' is the side to move, 'XSide' is the other side. The OO_POSSIBLE and OOO_POSSIBLE macros simply test whether the side to move still has the right to castle kingside or queenside. As you can see, I simply look at the squares between the king and rook and check that they are empty and not attacked by the opponent, and generate a castling move if everything is OK.

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: in check test

Postby Pedro Castro » 08 Jul 2005, 00:43

At the time of making a generator of moves you have two possibilities, that single it makes the legal moves or that also it makes moves where the king can be in check. Normally it is chosen second, in that case when you are in the search, at the time of making the move you must verify that each move is legal. To delay the verification of if the king is had left in check from the generation of the moves until the search gives a greater speed to the program, they have already explained it previously.

You can observe this in program TSCP. In the search, when it makes the move verifies in the funtion makemove if it remains in check.

If that is important that the verification if a square is attacked it is as rapidly as possible, since there is to prove it for many moves, and indeed the TSCP verification is not very fast, one better verification would give at least a 50% more of speed at the time of search for the moves.
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: in check test

Postby Anonymous » 09 Jul 2005, 17:50

Well, I was thinking, if I ordered the moves so that the captures are at the top of the move list (or right after hash moves), then i would find out very fast if there's a king capture and can stop searching the illegal move. Also, the SEE would give the capture a pretty high score, so it would be first of all captures too. Hopefully, the savings for skipping the incheck test will overweigh the losses of searching additional nodes ...
Anonymous
 

Re: in check test

Postby Pallav Nawani » 09 Jul 2005, 18:30

Wing Lee wrote:Well, I was thinking, if I ordered the moves so that the captures are at the top of the move list (or right after hash moves), then i would find out very fast if there's a king capture and can stop searching the illegal move. Also, the SEE would give the capture a pretty high score, so it would be first of all captures too. Hopefully, the savings for skipping the incheck test will overweigh the losses of searching additional nodes ...


When you are generating the moves, at that time itself you should flag a king capture and return immediately. The fact that a king capture is possible means that the current position is illegal. There is no need to generate any more moves, no need to search any moves at all.

On the other hand, I will just note that I tried this idea in Natwarlal's qsearch long ago, and I did not find any benefit. Yes, the NPS increased, but it was compensated by rubbish nodes that the program was now searching. It may work for you, who knows? But the benefit will likely be very small.

Pallav
User avatar
Pallav Nawani
 
Posts: 147
Joined: 26 Sep 2004, 20:00
Location: Dehradun, India


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 2 guests