Winboard Forum

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

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

Volker

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.

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.

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

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.

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 ...

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