Development of Shen Yu

[algerbrex]

I genuinely cannot find out what's wrong. I think I may have to rewrite the search routine.
What I ended up doing was stripping my search down to a beancounter and a basic alpha beta search. Nothing fancy.
It ended up outputting that white was a knight up from startpos.
This is awkward...

Hmmm, you sure you've double checked the eval? If you have nothing but negamax + alpha-beta, and even qsearch, things should be working fine. Assuming your eval is at most material + PSQT. I'd just make it material and check again just to be sure. Like I mentioned earlier, that score has to be coming from somewhere...

[hgm]

The PV is the most important debugging information, and examining it should always be the first step in debugging. That is irrespective of what type of search you use.

In fact you should print the list of moves and their scores in every node of the PV. So that you can see why a wrong move is chosen as the best, and whether that is the fault of the chosen move having too high a score, or the good move that should have been chosen instead of it getting too low a score. Continue this along the branch with the wrongly scored moves, and you wil reach the leaf with the faulty eval. (Or a node where the good move is not searched at all.)

This way it never takes more than a few minutes to find the source of the error.

[AAce3]

I genuinely cannot find out what's wrong. I think I may have to rewrite the search routine.
What I ended up doing was stripping my search down to a beancounter and a basic alpha beta search. Nothing fancy.
It ended up outputting that white was a knight up from startpos.
This is awkward...

Hmmm, you sure you've double checked the eval? If you have nothing but negamax + alpha-beta, and even qsearch, things should be working fine. Assuming your eval is at most material + PSQT. I'd just make it material and check again just to be sure. Like I mentioned earlier, that score has to be coming from somewhere...

I switched out my eval to beancounter, as I said. I might just have to rewrite the search routine.

The PV is the most important debugging information, and examining it should always be the first step in debugging. That is irrespective of what type of search you use.

In fact you should print the list of moves and their scores in every node of the PV. So that you can see why a wrong move is chosen as the best, and whether that is the fault of the chosen move having too high a score, or the good move that should have been chosen instead of it getting too low a score. Continue this along the branch with the wrongly scored moves, and you wil reach the leaf with the faulty eval. (Or a node where the good move is not searched at all.)

This way it never takes more than a few minutes to find the source of the error.

You're probably right. I'll do that next.

[AAce3]

Firstly, I verified that all these things were correct and I didn't forget any minus signs.

Code: Select all

fn eval() {
	(whitematerialvalue - blackmaterialvalue) * if tomove == WHITE{ 1 } else { -1}
}
...
fn alphabeta(alpha, beta, depth){
	...
	score = -negamax(-beta, -alpha, depth - 1);
	if score > alpha{
		alpha = score;
	}
	if alpha >= beta{
		break;
	}
	...
}

The strangest thing was that when I removed the beta "break," i.e. just plain minimax, it returns a correct score. Something is seriously wrong and I cannot figure out why it's behaving so strangely.

Here is the full code:

Code: Select all

pub fn negamax(
        &self,
        mut alpha: i16,
        beta: i16,
        depth: u8,
        data: &mut SearchData,
        ply: u16,
        pvline: &mut List<Move>,
    ) -> i16 {
        if depth == 0 {
            return self.evaluate();
        }

        data.nodecount += 1;
        let mut moves_generated = MoveSorter::new(self, 0);

        let mut best_pvline = List::new();
        let mut best_score = i16::MIN;
        while let Some(action) = // fetches the best action from move sorting using killer and history heuristics
            moves_generated.next(&data.history, &data.killers.table[ply as usize])
        {
            let mut newpvline = List::new();
            newpvline.push(action);

            let newb = self.do_move(action); // copy make creates another board instance
            let score =
                -newb.negamax(-beta, -alpha, depth - 1, data, ply + 1, &mut newpvline);

          
            if score > best_score {
                best_score = score;
                best_pvline = newpvline;
            }
            
            if score >= beta{
               break;
            }

            if score > alpha {
                alpha = score;
            }
        }
        for i in 0..best_pvline.length {
            pvline.push(best_pvline[i as usize]);
        }

        best_score
    }

[JVMerlino]

Well, it appears to me that you need to switch the order of those two checks. In other words, it should be:

Code: Select all

            if score > alpha {
                alpha = score;
            }
            
            if score >= beta{
               break;
            }

Most simple engines actually do something like this:

Code: Select all

            if score > alpha 
            {
                alpha = score;
	        if score >= beta
        	       return beta;
	    }

...with other bookkeeping, such as storing the PV, updating history, storing the hash value, etc., inserted in the proper places...

[AAce3]

It shouldn't matter though, shouldn't it? The code I posted is mostly identical to fail soft alpha beta, and in fact when I made it into

Code: Select all

if score > best_score {
                best_score = score;
                best_pvline = newpvline;

                if score > alpha {
                    alpha = score;
                }
                
                if best_score >= beta {
                    break;
                }
            }

It didn't end up changing any of the results.
The reason why I don't update my killers, history, etc. is because I'm trying to figure out what's wrong with alpha beta in a vacuum.

[AAce3]

I'm truly at my wit's end here. If any of you can help me figure this out I will be incredibly grateful.

Code: Select all

pub fn negamax(
        &self,
        depth: u8,
        mut alpha: i16,
        beta: i16,
        data: &mut SearchData,
        ply: u16,
        pvline: &mut List<Move>,
    ) -> i16 {
        if depth == 0 {
            return self.evaluate();
        }

        data.nodecount += 1;
        let mut moves_generated = MoveSorter::new(self, 0);

        let mut best_pvline = List::new();
        let mut best_score = -CHECKMATE;
        while let Some(action) = // fetches the best action from move sorting
            moves_generated.next(&data.history, &data.killers.table[ply as usize])
        {
            let mut newpvline = List::new();
            newpvline.push(action);

            let newb = self.do_move(action);
            let score = -newb.negamax(depth - 1, -beta, -alpha, data, ply + 1, &mut newpvline);

            if score > best_score {
                best_score = score;
                best_pvline = newpvline;

                if score > alpha {
                    alpha = score;
                }
                if score >= beta{
                    break;
                }
            }
        }
        for i in 0..best_pvline.length {
            pvline.push(best_pvline[i as usize]);
        }

        best_score
    }
    
pub fn evaluate(&self) -> i16 {
        let eval = self.beancount();
        if self.tomove == WHITE{
            eval
        } else {
            -eval
        }
    }
    
pub fn beancount(&self) -> i16{
        let mut score = 0;
        score += self.get_pieces(PAWN, WHITE).count_ones() as i16 * 100;
        score -= self.get_pieces(PAWN, BLACK).count_ones() as i16 * 100;

        score += self.get_pieces(KNIGHT, WHITE).count_ones() as i16 * 315;
        score -= self.get_pieces(KNIGHT, BLACK).count_ones() as i16 * 315;

        score += self.get_pieces(BISHOP, WHITE).count_ones() as i16 * 325;
        score -= self.get_pieces(BISHOP, BLACK).count_ones() as i16 * 325;

        score += self.get_pieces(ROOK, WHITE).count_ones() as i16 * 500;
        score -= self.get_pieces(ROOK, BLACK).count_ones() as i16 * 500;

        score += self.get_pieces(QUEEN, WHITE).count_ones() as i16 * 900;
        score -= self.get_pieces(QUEEN, BLACK).count_ones() as i16 * 900;
        

        score
    }

Perhaps you can help me find something that I can't. I think I'm going a little crazy trying to debug this.

[hgm]

Well, that is normal. Since you kept staring at the code rather than debug it along the lines I suggested, it takes weeks rather than minutes.

[AAce3]

I did end up printing the PV but I couldn’t figure out why it was behaving strangely. In all of there pv lines black took on a2 with a knight which got recaptured by the rook, leading to the appearance that white was up by a knight. That did not happen when I disabled beta cutoffs.

[AAce3]

I finally fixed it. It turns out that because I was setting beta and alpha to be the max value for i16 and min value for i16 respectively at the search initialization, there were some integer overflow/underflow errors. Alpha is thus -32768 and beta is 32767, so when I negated alpha to place as beta it actually overflowed because there is no representation of 32768 in 16 bit integer, it overflows back down to -32768 (I think).