Courses/CS 460/Fall 2007/Boat strategies
From CSWiki
I think we should use this page to share our findings on boat strategies. SpencerP 19:45, 5 October 2007 (PDT)
Contents |
[edit] Breadth-First Search
- Michael Allen
- Cuong Tham
- Habib Khan
[edit] Oct. 11
I have a Breadth-First search done. However, this search strategy seems to be poor because too many nodes are expanded within about 9 clicks from the boat (The path lengths are only 9 characters long). When the boat discovers that it is going to be hit it has not time to do anything about it. Searching more nodes will make the path lengths longer, but this takes up too much time and memory and the program runs really slow. Unless we come up with a better way of filtering out the poor nodes I do not think a Breadth-First search will be effective.
-Michael Allen
[edit] Oct. 31
I have just finished making a best first search. It works better than the breadth first search, but the boat still has trouble evading a torpedo when it comes at it from behind, any suggestions on how to fix this? This search is a greedy best first search, so I am going to try and make it plan ahead a bit more. I am also going to develop an A* search from this best first search.
-Michael Allen
[edit] Breadth First Problem
I have finished Breadth First algorithm but it has problem that it can not expand tree more than 9 levels and i get too many node exception. Also boat got hit even there is only one torpedo. I am keeping the intermediate nodes and i am thinking to get rid of them so that I can expand tree deeper than 9 levels as Cuong did. Any other suggestion???
[edit] Breadth-first
It's good you did it, though. Aaron Chu's spider search is basically a breadth first search. But instead of expanding one node at a time, it expands N nodes at a time. That is, each expansion step is an N-node sequence. What does that mean? It means that instead of treating the tree as a binary tree, he treats it as an N-ary tree.
Assume N = 5.
- The leftmost "virtual node" takes the following steps: LLLLL
- The second leftmost "virtual node" takes the following steps: RLLLL
- The third leftmost "virtual node" takes the following steps: RRLLL
- etc.
He does it probabilistically rather than explicitly, but the result is similar. (His leftmost node has a 0% chance of generating an R step. His next leftmost node has a 20% chance of generating an R step. Etc.)
How about trying something like that?
Russ Abbott 18:37, 11 October 2007 (PDT)
[edit] Depth-First Search
- Anuj Nagar
- Lalantha sath
[edit] Tree directed search
If you run the current system (which works quite well) you will notice that there are often times when the gold dot (which represents the system's view of the best place to go) flickers in an area that has lots of blue and red nodes. The blue means those nodes have been expanded already. The red means those nodes are dead ends. So if the system spends a lot of time on other nodes in the same general area it might be wasting its time. Since it has only a limited amount of time each tick, perhaps it should be exploring nodes in a more promising area of the tree.
The problem is that the way the system decides which node to expand is based solely on the property of the node. One property it considers is how close the node is to home. Another is how long a path it is from the boat's current position to the node. Both of those are reasonable properties. But they don't take into account the possibility that the node may be in a neighborhood that has other nodes that we already know are dead ends.
So the challenge is to mark the tree so that the fate of other nodes is taken into consideration when we decide which node to expand. A good way to start is to keep in each tree node the number of descendants below that node in the tree and the number of frontier nodes (which means descendants which have not yet been expanded) below that node. If the ratio of frontier nodes to total descendants is low that means that most of the nodes below that node have led to dead ends. So other nodes below that nodes are less likely to be worth expanding.
I just uploaded a version of the system that does an initial version of this. Look at STTreeNode.getTreeDirection(). It is called from STSearch.updateTree() when the STSearch strategy is making a decision about which way to move. It has already expanded the tree and found what it thinks is the best frontier node (called bestNode).
STTreeNode.getTreeDirection() looks at the root of the tree and makes its own decision about the best direction to move based on information about root.left and root.right. It also looks at the bestNode and in some cases selects the bestNode's direction. For example if the bestNode is at Home, STTreeNode.getTreeDirection() simply accepts that direction.
To see when the tree direction is different from the bestNode direction, uncomment the printouts at the bottom of STSearch.updateTree(). Russ Abbott 13:56, 7 October 2007 (PDT)
P.S. This initial version applies only to selecting the direction to move at each tick. There is a second equally important decision, which is to select which node to expand each time a node is expanded. Up to ~2000 nodes are expanded each tick. That is still done without considering information about the tree. It would be useful to apply some of the same considerations to making that decision.
P.P.S. If you are interested in this issue, it can probably be turned into an MS project.
[edit] Best-first Search
My version of best-first search is completed. It took me a while, but I finally fixed the null pointer exception that troubled me the past few weeks.
It turns out quite nicely. Though I haven't counted it one by one, I could say the success rate is around 80% with TorpedoCount set to 5. Besides that, I added a few parameters to the repast UI:
BfSpread: this controls the shape of the tree. To see how this value affects the shape of the tree, try some values between 1 to 9. The optimal values, as I tested, are 4, 5, and 6.
DrawBestPath: this option turns on or off the drawing of best path.
Another thing is I changed TreeToTickLimitRation to 20 (default is 3) to make the tree longer. Default value will also work but it's difficult to see how the tree is being built on each level.
Jar file: Media:BoatTorpedoes-best-first.zip
Source: Media:BoatTorpedoes-best-first-Src.zip
To run it, open run.bat in a text editor, update repastPath to your repast lib directory, make sure that repast.jar and all other jar files are in this directory. Dlb click run.bat.
--Ctham 23:17, 21 November 2007 (PST)
