Disjoint Set Algorithm


Table of contents

This algorithm is part of Housebot's implementation. So far it's the only go engine that uses it. jhouse

Base Computer Science Algorithm

See [ext] here for the theoretical foundation for this page. It's effectively a data structure for efficient mergers of groups and comparison if two items are in the same or different groups.

Allowing Undo

Housebot allows undo's by adding an extra field to the data structure. The path compression is restricted to not cross an undo boundary. A boundary is simply defined to be a node with a boolean flag set. Housebot uses a function object for retaining the required undo/commit information.

Allowing Stone Capture

Given the parent storage structure, any intermediate node being deleted could actually be used in the lookup of the parent of other nodes. Here are candidate solutions:

  • When placing a new stone on the board, do not make it's group be its own parent. Instead give it a distinct parent (aka allocate a parent for it). Then, when stones merge, the new stones' parent will be this other node that was created instead of something that can later be deleted. This scheme relies on memory management (such as exists in Java or maybe a shared_ptr from boost for C++).

Disjoint Set Algorithm last edited by on December 29, 2009 - 11:14
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library