3-Solving-Problems-By-Searching

[redblobgames]

Let's discuss the visualizations for chapter 3 here.

[redblobgames]

One of the questions was about whether we need to write the code twice, once for visualization and once to display. When the visualization code is similar to what you would've written without visualization, let's display it, but otherwise writing a second copy of the code is a lower priority.

Sometimes it will be possible to use the same code. Here's an idea from @Ghost---Shadow : what if we write graph search the ordinary way (Search/graphSearch.js) and then instrument the problem and frontier objects so that they record the operations? (We may also need to instrument explored.) Then we can run graph search once and animate the operations over time. For example if we want to display the frontier, we can instrument the frontier object with a wrapper:

function traceFrontier(frontier) { 
 return {
    history: [],
    indexOf: function(e) {
        return frontier.indexOf(e);
    },
    pop: function() {
        let node = frontier.pop();
        this.history.push({node: node, operation: 'pop'});
        return node;
    },
    push: function(node) {
        this.history.push({node: node, operation: 'push'});
        frontier.push(node);
    },
    concat: function(elements) {
        elements.forEach((e) => this.push(e));
    }
  };
}

Then the visualization can have a slider that extends from 0 to history.length, displaying all the state of the frontier at any point in its history.

[Rishav159]

As suggested by @redblobgames I will be working to implement the visualization about explaining the node expansion concept. The user will have to click the nodes to expand them. We can ask the user to reach a specific goal state by expanding nodes or something like that.

[Ghost---Shadow]

Essentially it is recording the state sequence like a video. It is not truely interactive, I had used it in the AC3 visualization because I was having some difficulty inserting handles. It was because AC3 has a recursive nature.

Let me elaborate. It is easier to have separate independent codes for logic and visualization if the logic is state oriented. i.e. There is some function like iterationStep or getNextState which takes the last state and some parameters as argument and generates the next state. If the algorithm is recursive, it becomes quite difficult.

[redblobgames]

@Ghost---Shadow Good point — it simplifies things when the interaction is a recording/animation (maybe with a slider) (this is the style of interaction I used on my A* page) but it won't handle interaction in the middle of the algorithm, like what @Rishav159 is working on first. The best approach will depend on the type of visualization.

[Rishav159]

@redblobgames Now that the node expansion visualizations are completed for now, should I move on to BFS algorithm?

[redblobgames]

Yes, Breadth First Search and Depth First Search are both algorithms for choosing which node to expand next without looking at edge weights, and I think they could both work well with the graph visualization you just built.

[Rishav159]

What changes should I make to the already implemented visualizations? Also, I guess a graph which is just like the Romania map given in the map would help.

[redblobgames]

Try implementing breadth first search and depth first search using the node expansion visualization at the top of the page. That way there's a set of diagrams that works together with the concepts you've already presented (that there's a graph, and that there's a search order):

• this is what node expansion is all about; you can choose the order
• this is all the search algorithm sees; you can choose the order
• this is how breadth first search chooses the order
• this is how depth first search chooses the order

For the other algorithms there will be additional concepts. Depth limited search needs the additional concept of search depth. Iterative deepening builds on that same concept. Uniform cost search introduces the concept of priority assignment along with a priority queue, and greedy best first and A* build on that.

[Rishav159]

Okay. I am working on it.

[Rishav159]

I just came across cytoscape. It's a javascript library used for visualizations of trees and graphs. What do you guys think?

[Jeet1994]

@Rishav159 will be great idea, except that we already have d3.js, which, in my opinion has a better documentation than crytoscape.

[Rishav159]

@Jeet1994 Documentation-wise, Yes, but I think cytoscape is more suitable and easy for building graphs (nodes and edges) which are the gist in this chapter.

[Ghost---Shadow]

I have yet to taste the full potential of d3.js but this looks nice, quite focused. Lets wait for the opinion of @redblobgames.

[Rishav159]

@Ghost---Shadow Yes, we will wait for @redblobgames for his opinion. I just think using Cytoscape.js, the graphs will be much more elegant and visually pleasing which is the point of the visualizations. Converting existing visualizations in this chapter to Cytoscape shouldn't be that difficult.

[redblobgames]

Cytoscape is a nice library for graphs, especially large complex graphs that you want to edit in the browser. There are also nice libraries for charts such as highcharts. D3 is a general purpose tool but it also gives us full control over appearance and interaction (more than two.js), which is useful when we're doing custom visualizations that don't match what other people are making. See the d3 gallery for the wide variety of custom visualizations that people build.

Specialized tools will let us build something more quickly for that one type of problem, and will also offer more advanced features than we are willing to build ourselves. A general tool will take more work to get started but it will let us build many different visualizations, including things that no specialized tool offers. Both approaches are useful :)

My guess is that given how many different types of visualizations we want to build for AIMA (looking at chapter 2, chapter 4, chapter 6), a general purpose tool (two.js or d3.js) will be more useful than learning and using many different libraries. At the beginning of gsoc we can try implementing some visualizations with several different libraries to get a sense for this.

[Rishav159]

@redblobgames Okay. So, for now, I am leaving Cytoscape just as a potential library to use during the GSoC.

[Jeet1994]

@Rishav159 I agree. However, working with presently stable libraries will be a better option, from a development point of view.

[redblobgames]

@Jeet1994 @Rishav159 Yes, we can discuss visualization libraries in #47 and other technologies in #1

[Rishav159]

Regarding the depth-limited search, the book only contains the description and pseudocode for the tree search and not graph search. So I guess the visualization should also only be made for tree kind of graphs and not graphs in general? I am asking this because the rules for a graph search is not present in the book and it will become ambiguous if used in visualization.

[redblobgames]

@Rishav159 if I remember right, the depth is the depth in the search tree which is a subset of the graph so you can equally well apply depth limited search to graph search. Put a different way, if you look at depth first search in a graph, each node will be visited in a "tree like" way, and you can keep track of the depth in that tree. (I'm not sure if I explained this well)

[Rishav159]

@redblobgames I understood that concept. Let me try with an example Suppose in this graph, my initial node is A, and the DFS moves along A-D-F-J-N-K-I-E and so on... When the node 'K' is expanded, the node 'I' goes into the frontier with a depth of 6 from the initial node. If the depth limit is 5, the node 'I' will never be expanded even if it actually is only 3 steps away from the initial node 'A'. Now, this is normal considering the dfs search tree, but it might prove to be counter-intuitive for the users as the book doesn't have this kind of explanation. The book shows the traversal directly in a search tree and doesn't show how that tree was formed. This might confuse the users. The user can get confused about the depth of a node in the search tree and depth as a distance from the initial node. Does that make sense?

So to be consistent with the book, we might show the traversal in a search tree directly. What do you think? @redblobgames

[redblobgames]

I think if you expand the frontier nodes < depth instead of ≤ depth then I would not go into the frontier from K, and then it could go into the frontier from E, but you're right, we should be consistent with the book's algorithms and explanations.

[Rishav159]

@redblobgames I will change the graph to make it a tree and I can mention that it's a dfs search tree. Would that be fine?

[redblobgames]

@Rishav159 try it and see how it feels! :) What is the main concept we want to show for depth limited search? A comparison between depth-limited and regular dfs? Or maybe a slider that controls the depth limit instead of using an animation. There are lots of possibilities.

For a slider you can use <input id="depth-limit" type="range" min="0" max="20" oninput="yourfunction()"> and then in yourfunction() use let depthLimit = parseFloat(document.getElementById("depth-limit").value);

[ghost]

Hi, I am planning to work on implementing A Star Search. Is these any other issue I need to worry about before implementing A Star Search?

[Rishav159]

Next up is Bi-directional search. The important concept to display here is : " b^d/2 + b^d/2 is much less than b^d". This means nodes generated when running two BFS (one from source and one from destination" will generate much smaller nodes than one BFS (from the source). We can visualize this by showing two bfs searches side by side. One with a normal bfs and other with bidirectional search (2 bfs from source and destination). We can show the number of nodes generated below the two visualizations to convey that concept. What do you think ? @redblobgames

[redblobgames]

@Rishav159 I agree, showing side by side would be useful. I think this is primarily an animation unless we can think of something where the reader can meaningfully interact with it. I guess you could let the reader choose the start and end nodes.

It might be useful to show a graph with a large number of nodes for this. The book describes a million nodes; that may be too much, but let's estimate how many we can show. Suppose the diagram is 300px X 300px. That's 90,000 pixels. How small can we make a node? Maybe it is a circle of radius 3, and then we need to make sure there's some space around it, so let's say circles are 5 pixels apart. That would mean we can fit 300px ÷ 5px = 60 circles on a side, or 60 X 60 = 3600 circles total. So we can probably show at least 1000–3000 nodes in a graph in the 300px X 300px diagram. It's not the 1,000,000 nodes mentioned in the book but it's a lot bigger than the graphs we have so far on the page.

Do you still have that code for making a random graph? Does it make planar graphs? You could try making a 1000 node graph with that. Alternatively, I might have some code lying around to make a large planar graph.

If 1000 isn't enough, I also have some larger graphs from some video games (Baldur's Gate, Dragon Age, etc.). For this page I drew the map with 1 pixel for each graph node, and it's a total of 137,375 graph nodes but it takes up 800px x 800px. There are probably some other graphs in that dataset that we can use that would fit into our 300px sized box.

[Rishav159]

I do have the code for making the random graph. I might need to change it a little bit as our graph representation has changed a little. But my approach was to randomly generate a node and see if it has a minimum amount of gap from other nodes. It worked fine for small number of nodes but it might get very slow for large number of nodes. I will have to figure out some other way of doing that. If you already have some code for doing that, I will like to take a look. Thanks

[redblobgames]

Randomly generating a node and seeing if it has a minimum gap is poisson disc generation; it can be sped up with a quad tree or other spatial index. I haven't yet written code for that; I've used a jittered grid instead because it's easy and I'm lazy ;) (see initialSeeds here)

Connecting those points together can be done with a voronoi algorithm such as Fortune's. d3 includes code for this, based on Raymond Hill's implementation. (The same Raymond Hill who wrote uBlock Origin!). d3's voronoi code turns out to be pretty good.

I think we don't need to build or update this graph at run time so it could be a small standalone program that generates the graph and then writes it out in json format. That also means it doesn't matter if it's slow so you could use your existing code and not worry about quad trees or other optimizations.

Alternatively you could use the graph you already have for the other examples, and work on bidirectional search first, and then after the algorithm and visualization are in place, we can come back later and try larger graphs not only for bidirectional search but maybe other visualizations too.

[Rishav159]

Alternatively you could use the graph you already have for the other examples, and work on bidirectional search first, and then after the algorithm and visualization are in place, we can come back later and try larger graphs not only for bidirectional search but maybe other visualizations too.

This seems fine. I would try to implement bidirectional in the existing graph and later I can use some technique to create a bigger graph once and store it in JSON format.

[Rishav159]

I made the bi-directional bfs with the default graph we have been working so far. Now that i tried increasing the number of nodes, the poisson disc generation method is currently able to build 500 nodes very fast but rendering them is very slow. The svg elements are not created again but the current code still updates the color of each and every node as well as edge. This must be making it slow. To counter this, I don't think we can reuse the draw functions we have written in the helpers.js. Also, I might need to experiment with the color combination as small nodes need darker color to be able to be identified.

[redblobgames]

@Rishav159 Since this chapter uses two.js, and two.js supports canvas output, is that something that would be easy to try out?

We don't yet know whether 500 nodes will make a good visualization so I would first try to see if it looks useful before investing much effort into making it fast.

[Rishav159]

@redblobgames I am sorry if its a stupid question, but what does it mean to support canvas output? I googled it and it looks like you want me to provide an image or a gif of the visualization without actually rendering it in the browser. Is that correct? Or am i missing something?

[redblobgames]

@Rishav159 not a stupid question :) The web is kinda of a mess. There are three different graphics systems supported by browsers — svg, canvas, and webgl.

With svg we are creating 500 <circle> objects on the page, plus probably thousands of <line> objects. That might be why it's slow. With canvas we create just one image and draw the circles and lines onto that image.

<canvas> is often faster than <svg>, but svg has the advantage that we can attach mouse events to the individual , which was really useful for most of the diagrams on the page. With canvas we can only attach the mouse click to the <canvas>. For this diagram I think we're not expecting to attach mouse clicks to the circles so canvas might work.

Two.js offers a choice of which system to use. I haven't tried this yet but when you construct a Two object where you pass in the height and width you also pass in a type: new Two({type: Two.Types.canvas, …}). You won't be able to attach onclick, onmouseover, etc. to the circles.

[Rishav159]

@redblobgames Okay got it. I will try to do this

[redblobgames]

Alternatively, if you haven't started a canvas implementation yet, you might try just 20-30 nodes and see if bidirectional search makes sense with that

[Rishav159]

I am currently trying to generate a random planar graph using poisson disc sampling technique. I have already implemented the algorithm for bidirectional search but not yet made a visualization for it. As you mentioned earlier, it will only make sense when there are lots of nodes in the graph. I wanted to demonstrate the concept that b^d is much less than 2*b^(d/2). It will be much clearer if I could show side by side both bidirectional and bfs search and also the number of nodes each one of them generated. Also, this particular diagram will be very different from the others that are present in this chapter. I could reuse some of the graph classes I made earlier, but they include additional properties like cost, parent etc which are not required. Hence, trying to reuse that code doesn't make sense to me. While I am at it, I want to use d3.js for this one unlike the other diagrams which use two.js. d3 also supports canvas and it has much better documentation and community support.

For now, I am facing some difficulty trying to get the graph generation properly. After I complete it, I will try to see how much time does graph generation take. If it is too much, I will randomly generate one and save it as JSON so it can be reused(as opposed to generating a new graph everytime)

[nervgh]

Good day!

Thank you for your work!

I see that A*-search is not implemented yet. I can propose my simple implementation of this algorithm. If you will find this useful it will be great :smiley_cat:

[redblobgames]

@nervgh thanks! We are mostly working on visualizations and not worried so much about the code. Norvig's A* code is pretty simple (see the python version) and it lets us reuse the graph search for other visualizations.

If you are using your A code in a real project you may want to use a better priority queue. Changing from O(N) operations to O(log N) operations or O(1) operations can make a big difference in A performance.

Are you interested in making visualizations for AIMA-javascript? Right now ch 3 has two different styles of diagrams (small number of nodes, using two.js, and large number of nodes, using d3.js) and either could be a useful starting point for an A* visualization.

[nervgh]

@redblobgames thank you for your informative comment!

If you are using your A code in a real project you may want to use a better priority queue. Changing from O(N) operations to O(log N) operations or O(1) operations can make a big difference in A performance.

Yes, it is. I had leave one reminder for myself.

Are you interested in making visualizations for AIMA-javascript? Right now ch 3 has two different styles of diagrams (small number of nodes, using two.js, and large number of nodes, using d3.js) and either could be a useful starting point for an A* visualization.

I have not so much time but I think yes. Why not :smiley_cat: How I can start working on it? Should I know something besides the Contribution Guide?

[redblobgames]

@nervgh Cool! Yes, the contribution guide, the implementation guide linked from there, and the code in chapter 3 are the things to look at. You'll find that the code is less structured than in many other projects, in part because it's more like a hundred tiny projects than one big project, and in part because it's experimental — we don't know which diagrams will work well, and we often have to make several different diagrams before we find one we like.

[nervgh]

@redblobgames thanks, I've read those docs. The best way of data representation (visualizations) is the hard choice.

I can try explain my approach (roadmap) for visualization of the A*-search algorithm:

• If we need graph representation I can use visjs,
• If we need matrix (table) representation like that I can use Vue.js for mapping data to the view
• For both cases I will plan use my simple implementation of A*-search which I mentioned above
• If we need random dataset we can generate it. Otherwise we can hardcode some simple dataset
• We should visualize the algorithm step by step using some convenient delay (setInterval)
• We should give to a reader the "Repeat" button
• We should visualize which nodes belong to frontier, expanded and enknown/expanded sets respectively

I think I can construct some simple demo and present (discuss) it to (with) you.

[redblobgames]

@nervgh Take a look at what's already implemented for chapter 3 — we already have graph data structures, random datasets, visualizations (of frontier, expanded, and unexplored areas), and a slider+button UI. Uniform cost search is similar to A, so I think the best thing to do will be to adapt that code to show how A differs from uniform cost search.

[nervgh]

@redblobgames ok. I will try to reuse project's code as much as I can.

[Rishav159]

Hey @nervgh, I wrote most of the code for this chapter. I apologise in advance for its bad condition! I'm still new to this. If you need help understanding any part of the code, I can help you with it.

[nervgh]

@Rishav159 good day. Don't worry about the quality of your code. I think that is not worst than my English skills. :smile_cat: Thank you for your suggestion of the help. I'll let you know if I need it.

[nervgh]

@redblobgames I've pushed some visualization of A*-search algorithm into 57-Solving-Problems-By-Searching. Please, see that and say your think about it. I mean we can modify that as we need.

[redblobgames]

@nervgh Looks nice. Thoughts:

1. If you merge the master branch you will have a slider class to play with. We've found the slider to be more useful as it lets the reader see things step by step at their own pace instead of at the fixed speed of setInterval
2. The heuristic is not admissible or consistent. You can see this by searching from A to O. It will find the path A-D-E-I-K-N-O (g=19) but the path A-B-C-D-F-J-N-O is shorter (g=12). One of the properties listed in ch 3 is that the f value should be nondecreasing along the path. We should probably use an admissible heuristic although I admit I haven't actually thought about what that would be for this example (maybe we should switch to the example in the book).
3. Sometimes I see the same node in the priority queue more than once. Although there are some variants of A* that allow that, the version explained in the book does not allow a node to be in the priority queue more than once. You can see this in the uniform cost search pseudocode — it checks if a node is already in the priority queue before adding it.
4. For the code, please follow the style of code already in the chapter as much as feasible. I know, Vue.js is cool, but we are using Two.js and D3.js and not Vue.js for this project. Ideally we would be using only one framework per chapter. Chapter 3 is a little messy already in that we have both d3.js and two.js visualizations; at some point we're going to want to go back through and clean that up. But it'd be a shame to add yet another framework into this chapter, and create more cleanup work in the future.

[nervgh]

@redblobgames thank you for your review.

1. What does the "slider class" mean? Is it css or js class? Could you give me a link to the line of code? If you mean \<input type="range"> so I've added step forward button because I did not implement step backward functionality. Only play/pause, step forward and reset buttons available currently.
2. "The heuristic is not admissible or consistent". Yes, it is :smile_cat: Sorry, but I had not ideas how to implement that using existing dataset. "(maybe we should switch to the example in the book)" Ok. I will look at that one more time.
3. "Sometimes I see the same node in the priority queue more than once". Hmm.. I think it is the bug. I will try to fix that. Thanks.
4. ... 4.1. About the code style. Sorry, I have not found something about it. I prefer to follow the standard style guide because I can just do standard --fix that will ensure consistent code style for some lines/files. There are a lot of famous projects which follow it. 4.2. About the frameworks. My goal was to creating the demo as fast as it possible. I mean the development is the iterative process. At first I write the code. After that you review it. Next I refactor this code and so on. I chose the Vue because I use it since 2015. I think it is pretty well for a quick demos at the one hand and it helps me "write less and do more" at another side. It allows me quite simply to map data on the view. For example, it is hard to render state like that without the template engine and a data-driven tool. But when I manage projects I have same opinion as yours -- "less (simple) it better" :smile_cat: (less tools/frameworks in this case). The choice is yours.

Anyway thank you for your time :v:

[redblobgames]

@nervgh Take a look at the uniform cost search diagram on http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/ — we used to have it animate on page load but now use a slider so that the reader has control over the speed of the process.

Another dataset that may be useful is the bidirectional search diagram on the page. That one (drawn with canvas instead of svg because it has so many nodes) would let you show the "contour line" aspect of A. Breadth first search expands uniformly in all directions but A expands much more quickly towards the goal and slowly in other directions.

For code style & frameworks: yes, there are some good styles and frameworks out there (I do like Vue) but usually the most important thing in a project is to be consistent. There are lots of different style guides (none of them are "standard" even though that's what one of them calls itself) and lots of different frameworks (d3 seems to be the most popular visualization framework and most new contributors are using that now). We've discussed what to do for aima-javascript (#1, #47) and decided for now we will compromise by having each chapter be consistent, but not try for consistency across chapters. Chapter 3 is primarily two.js for visualizations and a tiny bit of helper code in jquery and d3. It wouldn't be terrible to convert everything over to a different framework but it's a lot of work and would be something we can discuss separately (maybe in #47). So I think we'd want to make things consistent with the rest of chapter 3 (code style and framework).