Position flipping

[ibid]

It can also be used during opening book generation when (position, move) pair data are all stored using a White-to-move convention; this allows retrieval of "reversed" opening data.

As a aside, this is especially useful in variants like giveaway/suicide chess when computing and storing complex forced wins. For example, 1. f4 loses to e5. So 1. e3 f5 will lose to e4...

Even further aside, doing this resulted in a wonderful bug. I store enough of the tree so that when the book is left, the resulting position can be solved in under 10 million nodes via proof number search. Which worked wonderfully until one day it got a hit with a color flip, used 50 million nodes, ran out of memory, panicked, played a random move and managed to lose the game. This would be when I learned that PN search can be very sensitive to the order moves are generated in, since this effectively provides a tiebreaker for when proof numbers are equal. Now my engine always thinks it is playing white, it is just that sometimes black moves first... :)

-paul

[sje]

Now my engine always thinks it is playing white, it is just that sometimes black moves first...

Symbolic plays only the color it started with (absent user intervention), but when building or probing the book, it's always WTM.

But book access doesn't need all of the data in a Position instance flipped. Actually all it needs is the main hash from a WTM viewpoint. To do this, the program looks at the board in a flip way without actually flipping any of the data. Then, the program folds in the hashes for flipped values of the castling bits and the en passant target. So the WTM hash can be quickly generated from a BTW position.

The speed increase from the above is noticeable only when building a book from scratch.

The main Position::Flip() is called only as a result of the user flip command. This Flip() can do about a million flips per second depending on how many moves have been played so far, so it's too fast for a user to notice.

The BookMove class inherits from the Hash, Move, and WLD (win/lose/draw counts) classes. The book itself is a linear array of instances of BookMove, sorted by Hash. All of the fields are stored using the WTM viewpoint.

Because memory is so cheap and the book really isn't that big, Symbolic loads the entire book data into memory at start time. The in-memory book is probed with a simple binary search, so access is fairly fast. Indeed, it is so much faster than hitting a book file that the book can be probed several ply deep (not just at the root) with no measurable amount of delay. Because the book is constant once loaded, it can be accessed without a mutex.

As the book is dynamically allocated, it can be easily switched from the contents of one file to another if so directed. I suppose I could program multiple simultaneous books, but I don't see the need.

[bob]

I have a procedure "tested" that uses a flip and flop command (flop mirrors left to right at the d/e file point, flip mirrors using the 4/5 rank point. tested computes the static eval, then flips and computes, then flops and computes, then flips again to give the 4th option and computes again. All 4 scores must match. This detects the occasional black/white asymmetry, or the left/right asymmetry.

Interesting. I had never thought of a flop() like Crafty's, but I can see where it would be useful. Alas, a flop() must destroy castling availability data, so it has no inverse.

Symbolic does have ReflectX0(), ReflectY0(), and ReflectXY(). But they are used only for tablebase index generation and are not user commands.

A Position class instance in Symbolic contains a Board class instance as a member To flip the board, the following is used:

Code: Select all

void Board::Flip(void)
{
  Board otherboard;

  for (Sq sq = (Sq) 0; sq < SqLen; IncrSq(sq))
    otherboard.PutMan(sq, OtherMan(GetMan(OtherSq(sq))));
  *this = otherboard;
}

I will have to look, but I used to clear castling flags in the tested code. My eval does have a developmental bonus that penalizes losing castling rights without actually castling...

catching the a/h file asymmetries has saved a lot of headaches since without castling rights factored in, there is no difference between a and h if everything is mirrored.

[sje]

As posted above, Symbolic's book is WTM only (hashes, moves, results). This means a very slight slowdown when probing with a BTM position because of the need for some kind of flipped hash key.

But what if two (WTM/BTM) copies of the same book data were present, each from a different file? This would eliminate the need for flipping of both the input key hash and the output move and WLD vector. If the need for super fast book probing is high enough, then maybe the extra cost of memory might be worth the trade.

[sje]

If a chess program has the capability to run a search deterministically (no randomness, single threaded, stops at fixed limit of a node count or iteration, not time), then a position flip could be used to verify the search color-blindness.

Run a deterministic search with a position, then run the same search with the flipped position. All search results should be identical.

[asanjuan]

After flipping 17.000 fen positions, I could catch 3 more bugs in my eval yesterday. The curious thing is that the bugs where so ridiculous...

Now my eval is simetric. Thanks for the tip.

[sje]

Two more inexpensive testing techniques:

1. 32 bit vs 64 bit

A well written program in C/C++ which runs on a 32 bit platform should also run on a 64 bit platform, and vice versa subject to any resource constraints.

2. Little-endian (Intel/AMD) vs big-endian (PowerPC)

A good C/C++ program should perform well independent of the underlying endian aspect of the host architecture. A common trouble area is the representation of the external opening book data file. Symbolic addresses this by making sure that all external data is represented in big-endian format, so its opening book is the same for both Intel/AMD and for PowerPC. A second issue is handling bit scanning; bits should be extracted for a 64 bit word in the same order independent of the endian sense.

I regularly test Symbolic on all four combinations of the above as part of the development process. This testing has also shown some compiler and header differences which can be treated once identified.

[sje]

When building or accessing a WTM only opening book, it can be useful to generate a hash of the flip of a BTM position without having to do all the work of actually flipping the position.

Here's how Symbolic does it:

Code: Select all

void Position::CalcFlipHash(Hash& hash) const
{
  Bitboard bb = bbdb.GetMerge();
  Sq sq;
  
  hash.Reset();

  while (IsSqNotNil(sq = bb.NextSq()))
    hash.FoldHashManSq(OtherMan(board.GetMan(sq)), OtherSq(sq));

  for (Castling castling = (Castling) 0; castling < CastlingLen; IncrCastling(castling))
    if (cabs & BX(castling))
      hash.FoldHashCastling(OtherCastling(castling));

  if (IsSqNotNil(epsq))
    hash.FoldHashEpsq(OtherSq(epsq));
}

[bob]

Two more inexpensive testing techniques:

1. 32 bit vs 64 bit

A well written program in C/C++ which runs on a 32 bit platform should also run on a 64 bit platform, and vice versa subject to any resource constraints.

2. Little-endian (Intel/AMD) vs big-endian (PowerPC)

A good C/C++ program should perform well independent of the underlying endian aspect of the host architecture. A common trouble area is the representation of the external opening book data file. Symbolic addresses this by making sure that all external data is represented in big-endian format, so its opening book is the same for both Intel/AMD and for PowerPC. A second issue is handling bit scanning; bits should be extracted for a 64 bit word in the same order independent of the endian sense.

I regularly test Symbolic on all four combinations of the above as part of the development process. This testing has also shown some compiler and header differences which can be treated once identified.

I also use a constant format for book, based on writing individual characters, so that endian is not an issue. Did this a long while back as I burned myself a few times when moving back and forth from the PC to a Sun Sparc, or a Sparc to a Dec alpha. I got tired of starting round 1 of a tournament with a broken book.

[sje]

I also use a constant format for book, based on writing individual characters, so that endian is not an issue. Did this a long while back as I burned myself a few times when moving back and forth from the PC to a Sun Sparc, or a Sparc to a Dec alpha.

The routines to use are from the ntohl() and htonl() family. But there is no guarantee that there will be local support for eight byte integers. (Or doubles, either, I suppose.)

I wrote my own:

Code: Select all

bool ReadNet64(std::ifstream *ifsptr, ui64& value)
{
  bool okay = true;
  ui index = 0;

  value = 0;
  while (okay && (index < QwrdByteLen))
  {
    char byte;

    ifsptr->read(&byte, 1);
    if (*ifsptr)
    {
      value |= ((ui64) (ui8) byte) << ((QwrdByteLen - 1 - index) * ByteBitsLen);
      index++;
    }
    else
    {
      value = 0;
      okay = false;
    };
  };
  return okay;
}

bool WriteNet64(std::ofstream *ofsptr, const ui64 value)
{
  bool okay = true;
  ui index = 0;

  while (okay && (index < QwrdByteLen))
  {
    const char byte = (char) (value >> ((QwrdByteLen - 1 - index) * ByteBitsLen));

    ofsptr->write(&byte, 1);
    if (*ofsptr)
      index++;
    else
      okay = false;
  };
  return okay;
}