New Position representation

[tommadams]

A representation like the following would be smaller and eliminate the need for BoardVisitor and perhaps also GroupVisitor.

class Position {
 public:
  // Returns the color of the chain a c, or Color::kEmpty.
  Color color(Coord c) const { return static_cast<Color>((bits_[c].head_legal_color_size >> 12) & 3); }

  // Returns the number of liberties of the chain at c.
  // Returns 0 if the point at c is empty.
  int num_liberties(Coord c) const { return static_cast<int>(bits_[head(c)].liberties_prev); }

  // Returns the head of the chain or empty region at c.
  // All stones in a chain and all points in an empty region have the same head.
  Coord head(Coord c) const { return is_head(c) ? c : bits_[c].head_legal_color_size & 0x01ff; }

  // Returns the previous stone in the chain or empty region at c, or Coord::kInvalid if this
  // is the head of the list.
  Coord prev(Coord c) const { return is_head(c) ? Coord::kInvalid : bits_[c].liberties_prev; }

  // Returns the previous stone in the chain or empty region at c, or Coord::kInvalid if this
  // is the tail of the list.
  Coord next(Coord c) const { return bits_[c].next; }

  // Returns the size of chain or empty region at c.
  int size(Coord c) const { return static_cast<int>(bits_[head(c)].head_legal_color_size & 0x01ff); }

  // Returns true if the point at c is a legal move.
  bool is_legal_move(Coord c) const { return bits_[c].head_legal_color_size & 0x4000 != 0; }

 private:
  struct Bits {
    // If this point is the head of a chain: holds the number of liberties of the chain.
    // If this point is the head of an empty region: holds 0.
    // Otherwise: the previous point a chain or empty region.
    uint16_t liberties_prev;

    // The previous point a chain or empty region, or Coord::kInvalid.
    uint16_t next;

    //  f e d c b a 9 8 7 6 5 4 3 2 1 0
    // +-+-+---+-----+-----------------+
    // |H|L|C C|X X X|S S S S S S S S S|
    // +-+-+---+-----+-----------------+
    // Packed bit field:
    //  H : If 1, this point is the head of a chain or empty region.
    //  L : If 1, this point is a legal move.
    //  C : This point's color: empty, black, white.
    //  X : Reserved for future expansion.
    //  S : If this point is the head of a chain or empty region: the size of that chain or empty region.
    //      Otherwise: the index of the head of the chain or empty region.
    uint16_t head_legal_color_size;
  };

  uint16_t is_head(Coord c) const { return bits_[c].head_legal_color_size & 0x8000; }

  Bits bits_[kN * kN];
};

[brilee]

When combining chains, would you have to recount the liberties for the new chain? You'd also have to set all the new chain head pointers unless you're using a union find style algorithm

On Fri, Sep 20, 2019, 8:36 PM Tom Madams notifications@github.com wrote:

A representation like the following would be smaller and eliminate the need for BoardVisitor and perhaps also GroupVisitor.

class Position { public: // Returns the color of the chain a c, or Color::kEmpty. Color color(Coord c) const { return staticcast((bits[c].head_legal_color_size >> 12) & 3); }

// Returns the number of liberties of the chain at c. // Returns 0 if the point at c is empty. int num_liberties(Coord c) const { return staticcast(bits[head(c)].liberties_prev); }

// Returns the head of the chain or empty region at c. // All stones in a chain and all points in an empty region have the same head. Coord head(Coord c) const { return ishead(c) ? c : bits[c].head_legal_color_size & 0x01ff; }

// Returns the previous stone in the chain or empty region at c, or Coord::kInvalid if this // is the head of the list. Coord prev(Coord c) const { return ishead(c) ? Coord::kInvalid : bits[c].liberties_prev; }

// Returns the previous stone in the chain or empty region at c, or Coord::kInvalid if this // is the tail of the list. Coord next(Coord c) const { return bits_[c].next; }

// Returns the size of chain or empty region at c. int size(Coord c) const { return staticcast(bits[head(c)].head_legal_color_size & 0x01ff); }

// Returns true if the point at c is a legal move. bool is_legalmove(Coord c) const { return bits[c].head_legal_color_size & 0x4000 != 0; }

private: struct Bits { // If this point is the head of a chain: holds the number of liberties of the chain. // If this point is the head of an empty region: holds 0. // Otherwise: the previous point a chain or empty region. uint16_t liberties_prev;

// The previous point a chain or empty region, or Coord::kInvalid.
uint16_t next;

//  f e d c b a 9 8 7 6 5 4 3 2 1 0
// +-+-+---+-----+-----------------+
// |H|L|C C|X X X|S S S S S S S S S|
// +-+-+---+-----+-----------------+
// Packed bit field:
//  H : If 1, this point is the head of a chain or empty region.
//  L : If 1, this point is a legal move.
//  C : This point's color: empty, black, white.
//  X : Reserved for future expansion.
//  S : If this point is the head of a chain or empty region: the size of that chain or empty region.
//      Otherwise: the index of the head of the chain or empty region.
uint16_t head_legal_color_size;

};

uint16_t ishead(Coord c) const { return bits[c].head_legal_color_size & 0x8000; }

Bits bits_[kN * kN]; };

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/tensorflow/minigo/issues/891?email_source=notifications&email_token=AAKCKFSJLVUG3PY2T7CRKUTQKVUCRA5CNFSM4IY4KQI2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HMZNAWA, or mute the thread https://github.com/notifications/unsubscribe-auth/AAKCKFV2UKF2PGIPRWOM6DLQKVUCRANCNFSM4IY4KQIQ .

[tommadams]

Our current board representation already recounts liberties and updates all chain IDs when joining them :P

[brilee]

oh, okay, so this is just for bitpacking cuteness

On Mon, Sep 23, 2019 at 1:08 PM Tom Madams notifications@github.com wrote:

Our current board representation already recounts liberties and updates all chain IDs when joining them :P

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/tensorflow/minigo/issues/891?email_source=notifications&email_token=AAKCKFWE5YIAOPGL7HMN65DQLDZYDA5CNFSM4IY4KQI2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD7LSIMQ#issuecomment-534193202, or mute the thread https://github.com/notifications/unsubscribe-auth/AAKCKFRFMOOHBSOBEZEHSJ3QLDZYDANCNFSM4IY4KQIQ .

[tommadams]

It's a bit more than that:

• Having a proper linked lists of chains an empty regions will let us iterate over them more quickly.
• Treating empty regions the same as chains means that each empty region will have a unique ID that all points in it share. This would simplify and potentially speed up the finding of vital regions when searching for pass-alive chains.

[tommadams]

A prototype of this ended up only being about 10% faster and the code was less readable, so I'm giving up on this for now.