Graph Search Framework (Concept for a strategic analysis program)
Created on 2024-08-09T20:43:02-05:00
High concept: framework to solve strategy and logistic problems (ex. complex towers of hanoi) by modeling the world as a graph, allowing problems to be defined as script functions that produce graphs and edges.
Build the code up in Nim/Rebol.
Code
- Edge function: write this to take a world state and produce a list of actions that can be taken
- Action function: write this to take a world state, a chosen action, and produce a new world state
- Validation function: write this to verify the world state, such as enforcing constraints in TLA+ (where search fails when the validator vetoes)
- -==--==--
The framework needs to handle getting a list of edges (choices) from the current node (world state.) We persist this data but mostly focus on the tips of the graph search, loading them back when some criteria calls for searching another branch.
It might also be necessary to pause a line of search and try another one, possibly returning to the previous one as well. For example we might ask that no more than 4 actions deep be examined, which in a chess game means after examining two rounds of white-black moves to backtrack and try another line of inquiry.
Externalizing different graph search doctrines (like beam search), as well as having some kind of work queue, possibly also distributing the search across cores and computers.
If we insert some 'validation' function step, we can immitate what TLA+ does as well. Convert temporal algebra to the pair of "given this state, what branches" and "given this state and branch, what outcome" and we can grind out temporal modeling problems.
Tools:
- Dynamic programming. Take hashes of world state and map to (world hash, action) to avoid checking
- World hashing. Zobrist hashes, or hashing world state, recording set of states already explored
Problems:
- Deep trees. Graph search can result in a very large amount of branch points.
- Need to prevent infinite loops when trying out ideas