A bug is squashing me. HELP!

[Michael Sherwin]

So far all I have is a material searcher. From the initial position it returns a score of either 100 or -100 depending upon the modification or search depth. Never any other value. I update material on the fly in make and unmake. When a search is done the board and all starting data is the same as at the beginning of the search. The only thing that is off is the score returned. I made an endleaf material summation function in place of the on the fly summation. It did not have an effect on the score returned. I must be doing something wrong in the search. But, what?

Code: Select all

void Play() {
  s32 score, i;
   nodes = 0;
  score = RootSearch(-INF, INF, iDepth);
  state = IDLE;
}

Code: Select all

s32 RootSearch(s32 alpha, s32 beta, u32 depth) {
  u32 i;

  if (MoveGen()) return INF - sply;

  AddMoves();

  for (i = first[sply]; i <= last[sply]; i++) {
    MakeMove(&tree[i].move);
    tree[i].score = -Search(-beta, -alpha, depth - 1);
    TakeBack(&tree[i].move);
    if (tree[i].score > alpha) {
      alpha = tree[i].score;
    }
  }
  return alpha;
}

Code: Select all

s32 Search(s32 alpha, s32 beta, u32 depth) {
  u32 i;
  s32 score;
  
  if (!depth) {
    score = Material();
    //return (wtm ? wMat - bMat : bMat - wMat);
    return (wtm ? score : -score); // Qsearch(alpha, beta);
  }

  if (MoveGen()) return INF - sply;

  AddMoves();

  for (i = first[sply]; i <= last[sply]; i++) {
    MakeMove(&tree[i].move);
    tree[i].score = -Search(-beta, -alpha, depth - 1);
    TakeBack(&tree[i].move);
    if (tree[i].score > alpha) {
      if (tree[i].score >= beta) {
        return beta;
      }
      alpha = tree[i].score;
    }
  }
  return alpha;
}

[Michael Sherwin]

Maybe I am not thinking about it correctly. Maybe since there is no Qsearch yet whoever takes last takes best because there is no follow up to the last capture. Idk, I guess that I better do the Qsearch next.

[Henk]

I find it confusing that you don't update a value in main loop but update alpha only.

I would set value to -infinite, update it and return that value as a result.

Might be that is less efficient but I don't go that far for move generation is far more expensive.

First make it work then do optimizations. So you can always go back if optimizations gives bugs.

By the way in my code I even use an extra variable to save the original value of alpha. Needed to implement fail hard strategy.

[Michael Sherwin]

I'm not sure I follow. There is no aspiration window yet, so alpha starts at -INFINITY. So alpha will hold the value of the search. With an aspiration window there might be the need of a best variable because best might not make it to alpha. My understanding of fail hard is that all scores returned are either alpha or updated alpha or beta. In fail soft a value less than alpha or better than beta can be returned. Maybe I do not understand, idk. I just do the best I can!

[Robert Pope]

I think you have your

Code: Select all

if (tree[i].score > alpha) {
      if (tree[i].score >= beta) {
        return beta;

backwards. You need to check for a beta cutoff first. EDIT: Or on second thought maybe it doesn't really have to, but you are adding an extra "if" statement for beta cutoffs.

If you are always returning the same score, I would also try having your function Material() return a random number in [-100,100] instead of an actual material score. That will confirm that the issue isn't with Material() itself.

[elpapa]

So far all I have is a material searcher. From the initial position it returns a score of either 100 or -100 depending upon the modification or search depth.

Well, that should be impossible if you only search a few ply, although I'm not sure what you mean by modification.

If I were you I would add code to collect and print the pv to get a better sense of what's going on.

[Michael Sherwin]

I think you have your

Code: Select all

if (tree[i].score > alpha) {
      if (tree[i].score >= beta) {
        return beta;

backwards. You need to check for a beta cutoff first. EDIT: Or on second thought maybe it doesn't really have to, but you are adding an extra "if" statement for beta cutoffs.

If you are always returning the same score, I would also try having your function Material() return a random number in [-100,100] instead of an actual material score. That will confirm that the issue isn't with Material() itself.

If the test are done separately then the test for beta must be done first and every time. And since Beta cuts are less often alpha would still be checked most of the time anyway. On the other hand if the alpha test fails no beta test is needed. It is probably a tradeoff that has little effect either way.

The random score is interesting. I'm working on Qsearch right now and if that does not solve the issue I'll give the random values a try. But my gut is telling me that in a fixed depth search without Qsearch the side going last makes all last ply captures with impunity and that can not be good for accurate scoring.

[Michael Sherwin]

So far all I have is a material searcher. From the initial position it returns a score of either 100 or -100 depending upon the modification or search depth.

Well, that should be impossible if you only search a few ply, although I'm not sure what you mean by modification.

If I were you I would add code to collect and print the pv to get a better sense of what's going on.

Yes, that is a good idea! By modification I mean like creating an endleaf material summation function and a few other things I have tried. I'm just about to test the Qsearch. Maybe that will shed some light.

[odomobo]

Your code looks fine at initial glance. One issue I see is you claim that your code isn't working, but you aren't giving examples of what you're seeing vs what you expect to see.

With a lack of qsearch, the horizon effect should be really bad. The way it's written, I would expect to see scores overstated by maybe 300 cp for an odd depth, and understated by the same amount with an even depth.

[Michael Sherwin]

+1