4-Beyond-Classical-Search

[redblobgames]

Let's discuss visualizations and code for chapter 4 here. What are the main ideas from the chapter that could be turned into interactive/animated visualizations?

[redblobgames]

For showing a search space, you could use a 1d space in a 2d plot, or a 2d space in a 3d plot — you may look at the three.js library to see if a 3d plot is easy to make in it.

[Ghost---Shadow]

I often just look at the Python branch before approaching a problem. It is always easier to translate from python to javascript than pseudo-code.

Here are the algorithms in Chapter 4 as also listed in the python branch.

4.2 Hill-Climbing
4.5 Simulated-Annealing
4.8 Genetic-Algorithm
4.11 And-Or-Graph-Search
4.21 Online-DFS-Agent
4.24 LRTA*-Agent

Some of these are done but quality control maybe lacking. I am not sure how are you going to implement 3d into these. 3D hill climbing? Possible. What else?

[Rishav159]

Working under GSoC, I have added several visualizations under chapter 4.
The following visualizations are now present:

• Introduction to hill climbing problem: The reader is presented with a hidden state space diagram where only the current state and the already explored states are visible. The reader has 25 moves to try to find the highest peak. This motivates necessary intuition about the problem in the reader.

• Hill Climbing Search: A completely visible state space diagram is presented. The reader can click on any state to start the Hill-climbing search from there. The states from where the global maximum is achievable using this algorithm is marked with a distinct color.

• Simulated Annealing: A state space diagram is presented where the global maxima and the current state is marked. The diagram is continuously annealing with a temperature which can be controlled by the slider. The reader can control the temperature to see the robot switching states in that temperature. The reader is asked to gradually decrease the temperature to see how simulated annealing tries to find the global maxima

• Genetic Algorithm: This was already created earlier. I have not changed anything yet. The reader is presented with 10 organisms initially. The reader can click to create further generations and see how they adapt to their environment.

• Introducing Erratic Vacuum World: It consists of a 5-tile vacuum world which follows the erratic rules as mentioned in the book. The reader can record a sequence of moves and then press 'play' to watch the sequence get executed in the world. The user can notice that same sequence can generate different results when played multiple times due to the erratic nature of the world.

• Vacuum World with no observation: It has 8 5-tile vacuum worlds (no erratic behavior) with randomly generated initial states. Just like before, the user can record a sequence and watch it being executed in all the worlds at once. The user is asked to think of a sequence that can generate the final state regardless of the initial state.

• Online DFS Agent: This was already created earlier. There is a map with a robot exploring it using the online DFS algorithm.

There are few visualizations left. I will try to come back to them during the final month of the GSoC period.

Few ideas for the remaining visualizations in this chapter:

• Searching with Partial Observations: We can recreate figure 4.18 from the book. The visualization will consist of a map with the robot location hidden. The user will be presented with the precepts of the robot in its current state and after executing some actions. The user will have to pin down the location of the robot.

[redblobgames]

Feedback from someone I showed this chapter to:

• Simulated annealing diagram was confusing, as it already found the best value when he hit Restart and it didn't seem to have to search anymore.
• The temperature change was confusing, as it says to change it, but doesn't give you guidance on how much or how quickly.

[Rishav159]

Simulated annealing diagram was confusing, as it already found the best value when he hit Restart and it didn't seem to have to search anymore.

I have not encountered this problem yet as if I press restart, the slider changes back to highest temperature and the diagram keeps searching.
Although, I agree there are several problems with the diagram. The algorithm is difficult to demonstrate using state space diagram like the hill diagram we have used. Also, we have made several inconsistent assumptions (for example, by setting width to 100%, each state is now directly reachable from each state). I will need to rethink the way we are demonstrating the diagram.

The temperature change was confusing, as it says to change it, but doesn't give you guidance on how much or how quickly.

We could simply mention that it needs to be slowly changed, or we could provide some other sort of feedback, but I believe it would not be useful until we follow up on the other flaws of the diagram.

[redblobgames]

Agreed, we can revisit this when/if we redesign the diagram.

[nervgh]

Hi everyone!

I'm reading the book and I've reached this chapter 😸
I see that you've done great work 👍

I could help with something if it needed. But I don't know where start from.
I've created the task list for more comfortable tracking of status of this chapter (I mean as I see it).

• Optimization Problem
• Hill Climbing Search
• Simulated Annealing
• Genetic Algorithm
• Searching with non-deterministic actions
• The erratic vacuum world
• Searching with Partial Observations
• Vacuum World with no observation
• And-Or-Graph-Search
• Online DFS Agent
• LRTA*-Agent

1. Is it status correct? May be I'm wrong...
2. Could we move this task list in the first post of this issue? example

Thank you =)

[nervgh]

@redblobgames , @Ghost---Shadow ping =)

[redblobgames]

@nervgh Let's ask @Rishav159 as he was the last one working on this chapter and can suggest what's missing or needs work

[Rishav159]

@nervgh The reason we do not have a fixed task list is because the tasks are not that well defined. We might need multiple diagrams to demonstrate a concept and sometimes, a concept doesn't really need an interactive visualization at all ! Although, I agree starting with a list like this is a good way to start off.
For this chapter,

• Genetic Algorithm diagram does not seem to explain the concept at all. The entire diagram needs to be redesigned.
• Same goes for Online DFS Agent. Currently, its just an animation without any supporting explanation.
• Simulated Annealing is a hard concept to explain in just a single diagram. We realized this while working on it. There are several parameters that determine a good simulated annealing and it might require something more than just a "Hill representation of state space diagram". I am out of ideas on this one for now. You are welcomed to come up with new ways to demonstrate this algorithm :)
• I have not thought about And-Or-Graph-Search and LRTA*-Search through. It would be interesting to see what you can come up with for this.

Good luck!

[redblobgames]

@Rishav159 Thanks! Good starting point. I agree, we don't know what the page will have so it's hard to make a good task list. A lot of this will require experimenting. Sometimes there won't be any good interactive visualization for a concept (we may not be able to find something that's better than the explanations in the book).