Q1. Why HDA?
HDA is the simplest. In order to evaluate the efficiency of new hash method, simpler algorithm would be better. For example, other state-of-the-art algorithm like PBNF is only applicable to shared memory environment.
HDA* has fewer parameters amongst the state-of-the-art methods. We believe this hash method should be applicable to TDS, parallel implementation of IDA*, used in Shogi programs.
Q2. How applicable is SZ?
We currently tested only on combinatorial domain dependent implementations. But we believe this method is applicable to domain independent plannings as there are little to no domain dependent optimization on SZ. The method to implement SZ is similar to parallel structured duplicate detection.
Q3. Isn't SZ just an abstraction?
One of the important factor of SZ is to XOR components. By this mechanism, SZ effectively distributes nodes evenly. Abstraction do not have this mechanism so that it fails to distributes the search space.
Q4. Is Zobrist state-of-the-art?
Yes. It was the fastest method for HDA*. Also it is the state-of-the-art method for TDS in puzzle domains.
Q5. Is there any situation that SZ would not work?
At least it can revert back to Zobrist, so it does not get worse than state-of-the-art. If the state space is too small, then the instance is not for HDA* from the first.
Q6. What is the overhead of HDA* with SZ?
Sending nodes take time. Expanding nodes is very fast especially in grid and sliding tiles. Compare to that transferring nodes around does cost some time. Also the issue is cache efficiency. In sequential execution, most of the nodes are in cache. But in parallel execution, node may be transferred to other threads which they do not have the node in their cache. In fact the number of cache misses in HDA* is higher than sequential A*. However, we believe these kind of problem rise huge only in those kind of simple problem but not in realistic problems.
Q7. Why in shared memory environment?
To make it simple. We would like to factor out hardware topology. And also, results in shared memory would also be true for distributed system. Moreover, in distributed memory system, SZ should work better than in shared memory because it reduces communication overhead which is higher in distributed system.
Q8. What about memory limitation?
Yes, HDA* consumes a lot of memory but it can parallelize to distributed system. About SZ, it is applicable to other parallel methods like TDS. TDS is memory efficient search algorithm.
Q9. Why those domains have different speedup? How does it affect SZ?
Node expansion per second is the biggest factor. Generally if big, then efficiency goes up. In detail, if big then search overhead become more unforgiving. If short then communication overhead is the thing.
Q10. What is the difference from Parallel Window IDA?
PWIDA is parallelization of IDA* where as HDA* is that of A. A stores expanded nodes in closed list but IDA* does not. Therefore A* is memory bounded search, faster but more memory consuming. IDA* is linear memory but repeatedly expands identical nodes. That is the difference.
Q11. Why no abstraction for Grid-Pathfinding?
The result of the distribution is same as SZ. This is because the state is consist of only two features, x&y.
Q1. Why HDA? HDA is the simplest. In order to evaluate the efficiency of new hash method, simpler algorithm would be better. For example, other state-of-the-art algorithm like PBNF is only applicable to shared memory environment. HDA* has fewer parameters amongst the state-of-the-art methods. We believe this hash method should be applicable to TDS, parallel implementation of IDA*, used in Shogi programs.
Q2. How applicable is SZ? We currently tested only on combinatorial domain dependent implementations. But we believe this method is applicable to domain independent plannings as there are little to no domain dependent optimization on SZ. The method to implement SZ is similar to parallel structured duplicate detection.
Q3. Isn't SZ just an abstraction? One of the important factor of SZ is to XOR components. By this mechanism, SZ effectively distributes nodes evenly. Abstraction do not have this mechanism so that it fails to distributes the search space.
Q4. Is Zobrist state-of-the-art? Yes. It was the fastest method for HDA*. Also it is the state-of-the-art method for TDS in puzzle domains.
Q5. Is there any situation that SZ would not work? At least it can revert back to Zobrist, so it does not get worse than state-of-the-art. If the state space is too small, then the instance is not for HDA* from the first.
Q6. What is the overhead of HDA* with SZ? Sending nodes take time. Expanding nodes is very fast especially in grid and sliding tiles. Compare to that transferring nodes around does cost some time. Also the issue is cache efficiency. In sequential execution, most of the nodes are in cache. But in parallel execution, node may be transferred to other threads which they do not have the node in their cache. In fact the number of cache misses in HDA* is higher than sequential A*. However, we believe these kind of problem rise huge only in those kind of simple problem but not in realistic problems.
Q7. Why in shared memory environment? To make it simple. We would like to factor out hardware topology. And also, results in shared memory would also be true for distributed system. Moreover, in distributed memory system, SZ should work better than in shared memory because it reduces communication overhead which is higher in distributed system.
Q8. What about memory limitation? Yes, HDA* consumes a lot of memory but it can parallelize to distributed system. About SZ, it is applicable to other parallel methods like TDS. TDS is memory efficient search algorithm.
Q9. Why those domains have different speedup? How does it affect SZ? Node expansion per second is the biggest factor. Generally if big, then efficiency goes up. In detail, if big then search overhead become more unforgiving. If short then communication overhead is the thing.
Q10. What is the difference from Parallel Window IDA? PWIDA is parallelization of IDA* where as HDA* is that of A. A stores expanded nodes in closed list but IDA* does not. Therefore A* is memory bounded search, faster but more memory consuming. IDA* is linear memory but repeatedly expands identical nodes. That is the difference.
Q11. Why no abstraction for Grid-Pathfinding? The result of the distribution is same as SZ. This is because the state is consist of only two features, x&y.