Thinker output

[Zach Wegner]

To the shell, the book search and the tree search are just "strategies" (in design pattern speak). So, even if I implement a PV collection in the tree search, would I want to expose that? That means the book search would have to return a PV also? That means that any "search strategy" always include a PV. I could design it that way, but that would be a very bad design. That may not be a big deal to others, but it is to me.

But how much does the shell know? Do you pass back a move? A score? Does it handle time management? If you want your shell to be truly modular, it must only pass moves/positions/time controls in and out, as those are the only features which are universally appropriate. Pretty useless shell if you ask me.

IMO a PV is independent enough of the search implementation that it should be passed, much more so than the score. You could even look up a PV by following book moves if you wanted. But at the very least a PV of one move (the move you are playing) should be necessary.

[Zach Wegner]

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

I never understood this [ply][ply] nonsense. It was in TSCP, which was one of the first programs I ever saw. When I changed from the approach I just described to the two-dimensional array, I use [ply][0]. When you back up a PV, you store the current move in [ply][0] and copy the next ply's starting at [ply][1]. Saves an add.

[sje]

Some example code for linked list PV usage in a C++ mate finder:

Code: Select all

void MateTask::MateFinder(const Pos& matepos, const ui matedistance, Analysis& analysis)
{
  Window window;
  Score score;
  MoveList PV;

  window.SetFullWidth();
  pos = basepos = matepos; distance = matedistance; nodecount = 0;
  score = MateAttack(window, 0, ((distance * 2) - 1), PV);
  analysis.PutScore(score); analysis.PutNodeCount(nodecount);
  analysis.RefMoveList() = PV; analysis.EnsureMarking(pos);
  if (score.IsMating()) TensorTaskPtr->SSToWatch(analysis.FmtAnalysis() + "\n");
  mns.RecycleList(PV);
}

Score MateTask::MateAttack(const Window window, const ui ply, const ui depth, MoveList& PV)
{
  Window scanwindow(window);
  Score score(window.GetAlfa());
  MoveList BestPV;
  GMVec gmvec;

  nodecount++;
  if (ply == 0) pos.GenerateFull(gmvec);
  else
  {
    if ((depth == 1) && pos.NotInCheck()) pos.GenerateChks(gmvec); else pos.GenerateFull(gmvec);
  };
  if (depth > 1) {gmvec.MarkChecks(pos); gmvec.MoveChecksToFront();};

  const ui limit = gmvec.GetCount();
  ui index = 0;

  while (!score.IsMating() && !scanwindow.IsFailHigh(score) && (index < limit))
  {
    const Move move = gmvec[index];
    Window trywindow = scanwindow;
    MoveList SubPV(mns.NewNodePtr(move));
    Score tryscore;

    pos.Execute(move);
    trywindow.DownShift();
    tryscore = MateDefend(trywindow, (ply + 1), (depth - 1), SubPV);
    tryscore.UpShift();
    pos.Retract();

    if (tryscore.GetSV() > scanwindow.GetAlfa().GetSV())
    {
      scanwindow.PutAlfa(tryscore); score = tryscore;
      if (window.IsInside(tryscore)) {mns.RecycleList(BestPV); BestPV.JamAssign(SubPV);};
    };
    mns.RecycleList(SubPV); index++;
  };
  if (limit == 0) score = (pos.InCheck() ? CheckmatedScore : EvenScore);
  while (BestPV.GetHead()) PV.Append(BestPV.DetachHead());
  return score;
}

Score MateTask::MateDefend(const Window window, const ui ply, const ui depth, MoveList& PV)
{
  Window scanwindow(window);
  Score score(window.GetAlfa());
  MoveList BestPV;

  nodecount++;
  if (depth == 0) {score = pos.IsCheckmate() ? CheckmatedScore : EvenScore;}
  else
  {
    GMVec gmvec;

    pos.GenerateFull(gmvec);

    const ui limit = gmvec.GetCount();
    ui index = 0;

    while (score.IsLosing() && !scanwindow.IsFailHigh(score) && (index < limit))
    {
      const Move move = gmvec[index];
      Window trywindow = scanwindow;
      MoveList SubPV(mns.NewNodePtr(move));
      Score tryscore;

      pos.Execute(move);
      trywindow.DownShift();
      tryscore = MateAttack(trywindow, (ply + 1), (depth - 1), SubPV);
      tryscore.UpShift();
      pos.Retract();

      if (tryscore.GetSV() > scanwindow.GetAlfa().GetSV())
      {
        scanwindow.PutAlfa(tryscore); score = tryscore;
        if (window.IsInside(tryscore)) {mns.RecycleList(BestPV); BestPV.JamAssign(SubPV);};
      };
      mns.RecycleList(SubPV); index++;
    };
    if (limit == 0) score = (pos.InCheck() ? CheckmatedScore : EvenScore);
    while (BestPV.GetHead()) PV.Append(BestPV.DetachHead());
  };
  return score;
}

[CThinker]

The ways that other engines collect PV arrays look very hacky to me. They either allocate a square array, but use only half of it, or, allocates PV arrays on the stack on each call to a search function. Neither is acceptable to me. So, until I device a really clean solution, I am not inclined on polluting the Thinker code.

One idea from Vincent is to make an array pv_stack[MAX_PLY * MAX_PLY / 2]; and then keep a pointer to the first and last entry into it for each ply. Whenever you get a new PV, you save it starting at the first pointer, and then save the last entry. You then pass the entry past the last move (also you need a marker to signify the end of a PV) to the next ply.

ZCT used to do this but I got rid of it because of the copying of PVs in SMP. One CPU could be searching a node with current PV of length 1, then another CPU backs up a PV of length 3. You either have to truncate it or shift the current PV forward in the array to make room for it.

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

Yup, I am aware of this approach, but it does not appeal to me. Half of that array is unused.

[CThinker]

To the shell, the book search and the tree search are just "strategies" (in design pattern speak). So, even if I implement a PV collection in the tree search, would I want to expose that? That means the book search would have to return a PV also? That means that any "search strategy" always include a PV. I could design it that way, but that would be a very bad design. That may not be a big deal to others, but it is to me.

But how much does the shell know? Do you pass back a move? A score? Does it handle time management? If you want your shell to be truly modular, it must only pass moves/positions/time controls in and out, as those are the only features which are universally appropriate. Pretty useless shell if you ask me.

IMO a PV is independent enough of the search implementation that it should be passed, much more so than the score. You could even look up a PV by following book moves if you wanted. But at the very least a PV of one move (the move you are playing) should be necessary.

Yes, the shell only gets back a move and a score, once the search is done. The input to the search strategies only include an address to a "cancel" flag (the shell sets this when there is input that causes the search to be terminated) and a time limit (not a time control).

The shell is actually not that simple because it understands the xboard protocol. The shell is "game-aware" (e.g., time control, ponder-state). The search strategies are not.

The whole thing is like this:

while (there are search strategies)
{
get the next strategy;
use the strategy until the strategy returns empty move;
}

The beauty of this is that you can add another search strategy with very little effort (you just put it in the list, at the correct order). For example, you can have a middle-game-only search. Or you can have an slow book search (one that goes over network) plus a fast book search (in-memory book). You just queue-up all of them in the appropriate order.

I'm not aware of engines out there that are designed to accommodate an arbitrary number of search strategies. Perhaps Rybka.

Cheers...

[sje]

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

Yup, I am aware of this approach, but it does not appeal to me. Half of that array is unused.

Let's see...

maxply = 64; maxply * maxply = 4,096; move size = 4 bytes; total storage = 16 KB; wasted = 8 KB

RAM price per high quality, fast GB = US$32

8 KB / 1 GB = (ca) 7.6e-6

Cost of wasted RAM: about 1/40 US penny.
----

The [maxply][maxply] technique is not bad, and I think that many engines use it. I don't because I don't want any fixed maxply numbers in my program.

[CThinker]

Some example code for linked list PV usage in a C++ mate finder:

Code: Select all

void MateTask::MateFinder(const Pos& matepos, const ui matedistance, Analysis& analysis)
{
  Window window;
  Score score;
  MoveList PV;

  window.SetFullWidth();
  pos = basepos = matepos; distance = matedistance; nodecount = 0;
  score = MateAttack(window, 0, ((distance * 2) - 1), PV);
  analysis.PutScore(score); analysis.PutNodeCount(nodecount);
  analysis.RefMoveList() = PV; analysis.EnsureMarking(pos);
  if (score.IsMating()) TensorTaskPtr->SSToWatch(analysis.FmtAnalysis() + "\n");
  mns.RecycleList(PV);
}

Score MateTask::MateAttack(const Window window, const ui ply, const ui depth, MoveList& PV)
{
  Window scanwindow(window);
  Score score(window.GetAlfa());
  MoveList BestPV;
  GMVec gmvec;

  nodecount++;
  if (ply == 0) pos.GenerateFull(gmvec);
  else
  {
    if ((depth == 1) && pos.NotInCheck()) pos.GenerateChks(gmvec); else pos.GenerateFull(gmvec);
  };
  if (depth > 1) {gmvec.MarkChecks(pos); gmvec.MoveChecksToFront();};

  const ui limit = gmvec.GetCount();
  ui index = 0;

  while (!score.IsMating() && !scanwindow.IsFailHigh(score) && (index < limit))
  {
    const Move move = gmvec[index];
    Window trywindow = scanwindow;
    MoveList SubPV(mns.NewNodePtr(move));
    Score tryscore;

    pos.Execute(move);
    trywindow.DownShift();
    tryscore = MateDefend(trywindow, (ply + 1), (depth - 1), SubPV);
    tryscore.UpShift();
    pos.Retract();

    if (tryscore.GetSV() > scanwindow.GetAlfa().GetSV())
    {
      scanwindow.PutAlfa(tryscore); score = tryscore;
      if (window.IsInside(tryscore)) {mns.RecycleList(BestPV); BestPV.JamAssign(SubPV);};
    };
    mns.RecycleList(SubPV); index++;
  };
  if (limit == 0) score = (pos.InCheck() ? CheckmatedScore : EvenScore);
  while (BestPV.GetHead()) PV.Append(BestPV.DetachHead());
  return score;
}

Score MateTask::MateDefend(const Window window, const ui ply, const ui depth, MoveList& PV)
{
  Window scanwindow(window);
  Score score(window.GetAlfa());
  MoveList BestPV;

  nodecount++;
  if (depth == 0) {score = pos.IsCheckmate() ? CheckmatedScore : EvenScore;}
  else
  {
    GMVec gmvec;

    pos.GenerateFull(gmvec);

    const ui limit = gmvec.GetCount();
    ui index = 0;

    while (score.IsLosing() && !scanwindow.IsFailHigh(score) && (index < limit))
    {
      const Move move = gmvec[index];
      Window trywindow = scanwindow;
      MoveList SubPV(mns.NewNodePtr(move));
      Score tryscore;

      pos.Execute(move);
      trywindow.DownShift();
      tryscore = MateAttack(trywindow, (ply + 1), (depth - 1), SubPV);
      tryscore.UpShift();
      pos.Retract();

      if (tryscore.GetSV() > scanwindow.GetAlfa().GetSV())
      {
        scanwindow.PutAlfa(tryscore); score = tryscore;
        if (window.IsInside(tryscore)) {mns.RecycleList(BestPV); BestPV.JamAssign(SubPV);};
      };
      mns.RecycleList(SubPV); index++;
    };
    if (limit == 0) score = (pos.InCheck() ? CheckmatedScore : EvenScore);
    while (BestPV.GetHead()) PV.Append(BestPV.DetachHead());
  };
  return score;
}

Thanks for the code. I have already mentioned this approach. That to me is a lot of stack allocation. In most cases, you barely use a fraction of that local PV array. And if you implement that as a dynamic list, that would be slow.

Also, imagine putting that much code in MicroMax, and it would not be MicroMax anymore. In the end, the PV array is "statistics". If you have a really simplistic engine and a really clean design, why clutter the code?

It looks like this thread should now be moved to the programming sub-forum.

[sje]

Thanks for the code. I have already mentioned this approach. That to me is a lot of stack allocation. In most cases, you barely use a fraction of that local PV array. And if you implement that as a dynamic list, that would be slow.

A PV is implemented as a list and it's not slow at all due to storage recycling; total allocation costs are too low to be measured. It's fast as well; remember that only links are changed; move data is never copied.

[CThinker]

I like the approach I use, which is a pv[maxply][maxply]

At any depth, you only store into pv[ply][ply] for a terminal move. As you back up you only back up a part of this array. When you back up from 10 to 9, you copy everything from pv[10][0 to endofpv] and then save the current move in pv[9[[9] to go along with the partial PV being backed up... This is executed _very_ few times and costs nothing as a result.

Yup, I am aware of this approach, but it does not appeal to me. Half of that array is unused.

Let's see...

maxply = 64; maxply * maxply = 4,096; move size = 4 bytes; total storage = 16 KB; wasted = 8 KB

RAM price per high quality, fast GB = US$32

8 KB / 1 GB = (ca) 7.6e-6

Cost of wasted RAM: about 1/40 US penny.
----

The [maxply][maxply] technique is not bad, and I think that many engines use it. I don't because I don't want any fixed maxply numbers in my program.

To me, every line of code counts. Every run-time memory byte counts.

When you move into other platforms where memory usage is premium (not the memory cost, but run-time usage), you can see why the Thinker implementation pays off. Check out this comparison of Pocket PC engines by Alexandr. You will be surprised.
http://raitpref.hotbox.ru/ct001-r.htm

This explains why I'm not worried when Bob said that the Nintendo DS has slow processor and small memory. The Thinker port to that platform will do just fine (I think).

Sometimes I get the feeling that nobody cares about code elegance anymore.

[Graham Banks]

Sometimes I get the feeling that nobody cares about code elegance anymore.

Whilst I can understand where you're coming from from a programming point of view, program features are important to users.