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 :smile_cat: I see that you've done great work :+1:

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).

• [x] Optimization Problem
• [x] Hill Climbing Search
• [x] Simulated Annealing
• [x] Genetic Algorithm
• [x] Searching with non-deterministic actions
• [x] The erratic vacuum world
• [x] Searching with Partial Observations
• [x] Vacuum World with no observation
• [ ] And-Or-Graph-Search
• [x] 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).

[nervgh]

@redblobgames , @Rishav159 thanks!

I agree that we don't have to have a fixed task list. That might be dynamic =) For instance, we have a chapter which contains few concepts (algorithms). At this point we already know what we should visualize. May be we do not know how to do that, but we know that we should do it. And our task list should mirror it (for example):

• [ ] Implement visualization of Genetic Algorithm using the ... approach (here we know how to do that)
• [ ] Find a way to visualize Simulated Annealing (here we do not know how to do that)

It may be useful for new contributors like me :cactus: :smile_cat:

@Rishav159 thank you for detailing status of this chapter. Now I know where I might start :+1:

[redblobgames]

@nervgh I definitely agree that having these kinds of task lists would be useful for new contributors. It's just that there's no one to maintain those lists (**), so my worry is that the lists will get out of date. So instead we've been letting whoever's working on the chapter keep their own list. For the most part each chapter has been worked on by one person.

** Rishav and I were working on this project for summer 2017. I think Ghost--Shadow was working on it in 2016. Peter's focusing on the pseudocode and python. So there's no one actively on this project right now, and probably won't be until next summer (if it gets in GSoC). I try to check in every few days.

[nervgh]

@redblobgames thank you for this comment! I see that you have done great work :+1:

This project is still curious for me and I am going to continue working on it. But I am moving slowly :turtle: because I am learning English and Math in parallel :book: And I have a work of course =)

I want to be useful but I am not sure where I should moving on. For example, I have a little experience with Math Logic and Prolog language and I might take one or a couple of next chapters "7-Logical-Agents", "8-First-Order-Logic" and "9-Inference-In-First-Order-Logic". But there are chapters before those which are not still (mostly) complete. Where should I focus my efforts? What do you think?

[redblobgames]

@nervgh You have good points about not being able to see the status. Maybe after each chapter is 80% finished the author of that chapter can make a list of the things remaining, and then we can make them into github issues. I can work with @Rishav159 (who did all the work over the summer — I was only the mentor) to put that list into github issues. So far most of the work has been on new chapters and not completing existing chapters but it would be nice to make a list of what is needed if a chapter is nearly complete.

There are lots of visualizations possible and we don't know which ones will be useful/interesting. We don't have to go in chapter order — see issue #27; people have picked a chapter that's interesting to them and are not going in order. If you studied from AIMA, you might be able to look back to see which chapters were confusing, and might be easier to understand with interactive visualizations. If the chapter was not confusing, then the interactive visualizations may not be as useful. For some chapters there may not be any useful visualizations we can think of.

Pick any chapter you liked and think would be easier to understand with some visualizations :)

[ghost]

@Rishav159 @redblobgames Is anyone actively working on chapter 4? I've been looking at the code and have a few ideas on how I would tackle some of the issues.

[nervgh]

@regalhotpocket there are the useful issues. You can track status using those.

I guess Ch 4 is not under active development currently. You may fork at any time and improve these visualizations (via code review / MR).

[ghost]

@nervgh Good to know, thanks. I was actually looking at those issues, and I'll probably work on it tomorrow and post in the discussions to get feedback.

[redblobgames]

@regalhotpocket There isn't much active development on this project anymore. It was part of Google Summer of Code (GSoC) in 2017 and there was active development during the student application process and also during the summer, but now it's a handful of people who want to work on it unrelated to GSoC. So feel free to tackle issues :-)