Discovering and Searching Loosely Coupled Subproblems in Dou Shou Qi.
Burnett, Joseph W.
2010
- We present a technique for discovering, isolating and searching loosely coupled subproblems in the game of Dou Shou Qi. Subproblem discovery utilizes a minimum weight spanning tree to find clustering structure [10] in a complete graph of causality, which captures the distance between pieces in terms of a lower-bound on time-to-effect. A heuristic extends the duration of the split by isolating ... read moresubproblems, effectively trimming branches of the game tree which do not conform to the clustering structure. Searching loosely coupled subproblems in Go has been explored by Berlekamp [2]. Basic Dou Shou Qi strategy is outlined and used to develop a position evaluation function for the minimax algorithm. Additionally an algorithm to update a minimum spanning tree in O(n) time per outline set of neighborhood updates is proposed, conditional upon its being rooted in some simple transform of a Euclidean or Manhattan metric, and upon a maximum edge weight change which is constantly upper-bound. The minimum spanning tree updating algorithm, which uses simple data structures, improves on the more general result of Frederickson's O(sqrt(|E|)) time per update [5] by allowing n-1 neighborhood updates to occur in O(n) time on a complete graph, effectively in constant time per update.read less
- ID:
- 6m3121216
- Component ID:
- tufts:UA005.036.003.00001
- To Cite:
- TARC Citation Guide EndNote
- Usage:
- Detailed Rights
