3-Solving-Problems-By-Searching

[redblobgames]

3-Solving-Problems-By-Searching

[norvig]

These are looking very nice!

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

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

[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 ok. I will try to reuse project's code as much as I can.

[redblobgames]

@nervgh In your code you have A* skip the node if it's already in the queue. A* should not skip the nodes that are already in the queue. See the last if statement in figure 3.14. If you skip that node then you lose the optimality of A*.

I don't understand what the dividing by 32 does but I will take another look at it when I get more time.

[Rishav159]

If we assume that the starting and end points are known, there are very few instances where bi-directional bfs performs poorly than standard bfs.
From what I can think of right now, bi-directional bfs visits a lot more nodes if the the destination is not reachable from the source node. Other than that, I can't think of any other case where bi-directional bfs performs worse than standard bfs.

[redblobgames]

This chapter is essentially design-complete so I'm closing this issue. There are minor improvements that are filed as separate issues.

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

[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);

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]

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

[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 😺

[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 😺 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.

[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. 😸 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 😸 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" 😸 (less tools/frameworks in this case). The choice is yours.

Anyway thank you for your time ✌️

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

[redblobgames]

@nervgh For formatting, you might try prettier. I think its default settings are similar to the style used in this project. You can run prettier --write at the command line (works like standard --fix).

[nervgh]

@redblobgames

Take a look at the uniform cost search diagram on http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/

By the way, it would be great to have anchors per section (algorithm). It would give readers the ability to make references directly to an algorithm. For example:

• http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#node-expansion
• http://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/#breadth-first-search
• etc.

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

Good. I will try to use it for visualization of a stage of execution:

  ----|---------     // <-- this is our slider
0%..............100%

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

I will keep this thought in my mind, but previously I will plan focus on fixing the bugs, following the project's code style and reducing dependencies (Vue).

prettier --write

I've heard about prettier before, thanks. I think you can add something like this into "Implementation Guide". I mean we should prefer automation over instructions (when we talk about the code style in my opinion).

[redblobgames]

@nervgh I agree, it would be nice to add anchors. Until recently none of the chapters were even close to being complete so we hadn't set up a table of contents or section links. I created #98 to track this.

I agree that automatic code formatting is nice, especially when multiple people are working on the same code. For the most part, it hasn't come up yet because we don't have a lot of people contributing code to the same chapter, and we've let the primary author of each chapter choose libraries and code style. I'll add something to the wiki.

[nervgh]

@redblobgames Hi, Amit. I'm sorry for the long response delay. Everyday tasks (job) take much time. The current status is:

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.
#57 (comment)

fixed

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).
#57 (comment)

I've tried fix this using existing data-set. I made re-weight of the edges and one little change of h(n) function commit

Please, give me your feedback about these problems. Can we consider them as resolved?

[nervgh]

@redblobgames

In your code you have A* skip the node if it's already in the queue. A* should not skip the nodes that are already in the queue. See the last if statement in figure 3.14. If you skip that node then you lose the optimality of A*.

Ok. I will investigate that issue.

I don't understand what the dividing by 32 does

I've played with existing data-set and have thought about how to adapt that. It is the stupid attempt to "scale down" euclidean distance 😸

I'm sorry, Amit, but I'm still like a child in AI 👶
Thank you for your time and patience.

[redblobgames]

@nervgh No worries! Our main goal is not to implement the algorithms (although that's sometimes necessary), but to figure out what the core concepts are that someone new to AI would need to understand. So it'll be helpful to us if you have suggestions on what concepts were most confusing for learning A*. Then someone (you or someone else) can think about how best to show those concepts with the A* diagram(s).

[nervgh]

@redblobgames I had the second edition of "Artificial Intelligence: A Modern Approach" when I wrote my first comment in this thread. That book was translated on my native (Russian) language. What does it mean?

• 2th and 3th editions have different structure between each other. For example, 3th edition contains the information about uniformed and informed search algorithms in one chapter when 2th edition divides this on few ones
• as I mentioned above I have translated 2th edition. It caused some ambiguity about terminology for me. There is one sense but each language operates different words to pass it to a reader

The things like these to make confused me a little.

Now I have 3th edition on original (English) language. I see the book is much better explains many things 👍 Right now I cannot answer on your question. I think I need read it before I could be to say something.

[redblobgames]

@nervgh Aha! I had forgotten about the different editions. Yes, we have been working with the 3rd edition. I think the Java folk are moving to the 4th edition.

[redblobgames]

@Rishav159 Feedback from someone I showed this chapter to:

For bi-directional search, the behavior is the same for any location in the graph. Are there graphs where some locations are good for bi-directional search but other locations are bad? And if so, it might be useful to be able to position the begin/end nodes so that the reader can see some places it's good and some places it's bad.

My guess is that the current diagram is good for introducing the main idea but it doesn't answer the question of whether it's always better than breadth first search or if it's only sometimes better. That might requires a second diagram.

[nervgh]

@redblobgames I read aima3 now and I see that we have not mentioned about of the advantages of "Iterative deepening depth-first search":

Iterative deepening combines the benefits of depth-first and breadth-first search. Like depth-first search, its memory requirements are modest: O(bd) to be precise. Like breadth-first search, it is complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth of the node.

It may cause a reader to the conclusion what only the bi-directional search has advantages vs another uninformed search algorithms.

I've found one very interesting comparison for me:

Iterative deepening search may seem wasteful because states are generated multiple
times. It turns out this is not too costly. The reason is that in a search tree with the same (or
nearly the same) branching factor at each level, most of the nodes are in the bottom level,
so it does not matter much that the upper levels are generated multiple times

For example, if b = 10 and d = 5, the numbers are
N (IDS) = 50 + 400 + 3, 000 + 20, 000 + 100, 000 = 123, 450
N (BFS) = 10 + 100 + 1, 000 + 10, 000 + 100, 000 = 111, 110

Here is the authors' summary about IDS:

In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

[redblobgames]

@nervgh Yes, this is one of the things we may change in the future. We were told that we should make the visualizations for people who are currently studying from the book, so we should not include the explanations that are in the book on the web pages. @Rishav159 and I thought we should include a small amount of explanation. After we get feedback from the authors of the book, we may need to remove the small explanations we have now, or make them longer.

[nervgh]

@redblobgames Thank you for the clarification!

[nervgh]

@redblobgames

A* should not skip the nodes that are already in the queue

fixed

I don't understand what the dividing by 32 does but I will take another look at it when I get more time.

fixed

It looks like the h(n) is admissible and consistent now. Am I wrong one more time? 😸
The paths A->L and A->K assert it (for me).

However, there is 11pm on my clock at the moment and may be I should go to bed 😴 and I need look at that on next day 😅

[nervgh]

@redblobgames

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

The visualization of A* works with the slider from now.

[redblobgames]

@nervgh Looking pretty good!

(Side note: I think one day someone will figure out how to make the javascript code as short as the python version that Peter Norvig wrote (see https://github.com/aimacode/aima-python/blob/master/search.py#L395) — it reuses search functionality instead of each algorithm reimplementing search)

[nervgh]

@redblobgames Thank you! 😺

+1 for reusing and simplification of the code

I want to complete the A* visualization. The checklist for my task I see as follows:

• I should reformat the code using prettier. guideline
• I should rewrite the code without Vue.js. guideline
• I should squash all my commits into a single commit before submitting the pull request. guideline

And I have two questions:

1. Is it all or I've missed something?
2. Can we look at the second item of the checklist above from the other side: can we reduce jQuery instead Vue (in the context of 3 chapter)?

[redblobgames]

@nervgh Yes, please format the code with prettier, and use two.js (and a little bit of jquery) instead of vue.

Although it would be possible to rewrite the entire chapter with vue instead of two.js, it has low benefit compared to other things we could do. This chapter is nearly complete. We have been letting whoever writes the majority of the chapter to choose the library (see issue #47), so vue would best be used in a new chapter rather than rewriting a chapter that already is implemented.

The reader does not care that you used vue vs something else. We want to focus on the things that benefit the reader :-)

[nervgh]

@redblobgames

please format the code with prettier

I think it would be reasonable to add the prettier as the devDependency to this project. I am not sure, do we really use all these (one, two, three) dependencies or we can clean up these?

The reader does not care that you used vue vs something else. We want to focus on the things that benefit the reader :-)

Do you mean cute cats on the page? 😸
"The client does not care what we use behind the scene. He want to have a product which fits his expectations and/or does one thing better than another products on the market" =)

[nervgh]

@redblobgames

I've done two subtasks.

• I've removed Vue and jQuery for the A* visualization. But I'm still thinking than the declarative (functional?) approach was much better than the imperative one (diff) in the context of my task.
• I've formatted my code using prettier. I'm not sure that it has reasonable defaults. Look at the diff (one, two, three), please.

However, I can stay these changes as they are, squash all my commits and submit the pull request if you will approve that.

[nervgh]

@redblobgames I hope I have not said something awful and we could continue working on this task and finalize it in the future 😺

[redblobgames]

@nervgh I'm terribly sorry! I was away for a few weeks and then I forgot to check this when I got back.

1. No, we don't currently use all the dependencies, or even package.json at all. I think the people who set these up would like keep these in there. My involvement in this project is primarily for visualizations and not to choose coding style, libraries, build system, folder structure, web design, etc., so I'm going to leave those things to others.
2. I agree that prettier's defaults aren't necessarily producing the nicest code, and I would hesitate to recommending it to everyone. In this case I thought it would help automate the switch from the style you were using to the style this project is using. For people already writing code in the project's style, prettier may make things worse. The main goal is to match the existing style.
3. I agree that the imperative style you have now isn't as nice as what Vue or D3 would provide, since the construction of the table isn't supported by Two.js. At some point someone may want to revisit the choice of libraries for existing chapters. I think D3 would be the top choice based on the experience of several contributors, and it does seem like D3 is being used by people working on new chapters.
4. Yes, please submit the pull request :-)

[nervgh]

@redblobgames don't worry about it! ✌️ We are humans and we make mistakes all the time. Especially I do 😸 Anybody who does not work that one does not make them! (I am not sure how exactly to say this in English =)

1. I think I could help with that
2. I have not solution right now but I could investigate this problem and try to found something appropriate for us (it has low priority I think)
3. It is done -- #106