Ch 6 - Min-Conflicts visualization

[Dragneel7]

134

[redblobgames]

I don't understand what this visualization is trying to show. Can you explain the goals of the visualization? Which concepts is it explaining?

[Dragneel7]

I am trying to show that non-conflict algorithm can be used to solve the problem, to make it more understandable I believe I should add what is happening at each moment, the queen being moved and the how the position is being decided.

[Dragneel7]

The code at presents decides the column of the queen to be checked and the new position in that row on the basis of random function which leads to dnifferent number of moves each time a new animation is run. In the image the array are initail state of the board, the final state, and the number of steps required to reach. So, can we do something like "https://thewalnut.io/app/release/11/#time=10" in this evereything is predefined but we can explain what is happening at each step. If doing as the above website shows -> col_selected = [ 1, 5, 3, 4, 5 ]; row_selected=[ 5, 6, 2, 6, 3 ]; for(i=0;i<iter;i++){ x = x+1; var conflict = conflicts(soln); var total_conflicts = conflict.reduce(add, 0); if(total_conflicts==0){ console.log(soln); console.log(x); break; } col = col_selected[i]; val = row_selected[i]; soln[col] = val;} The following piece of code solves in 6 steps which we can easily show by allowing user to manually click instead of the long no. of steps in previous case. In each state we will show how the particular column and row is selected, thus describing the functioning of min-conflict function. @redblobgames What do you say?

[Dragneel7]

@redblobgames I have changed the visualization a bit so a to make it more interpretable. Please review the PR. Thanks

[redblobgames]

This diagram looks better!

I think showing that the problem can be solved is not that interesting. You can read the same in the book. We want to show the concepts that are hard to show in the book. For the min-conflict algorithm, the main idea is to count the number of conflicts for each possible position. It seems like we can show that visually. I think the other idea is that choosing the min conflict will produce a solution faster than if we choose other possibilities.

One idea for the diagram would be for the computer to choose the column, and then display the number of conflicts for each possible row. Then when they mouse over that row, you can show them the actual conflicts. For example if you say there are 3 conflicts, then when they hover over that space in the board, you can highlight all 3 of the conflict pieces. Then let the user pick any row. If they pick the row with the minimum conflicts, they'll find a solution faster. But let them pick any other row, to see how it takes longer to solve.

A different idea for the diagram would be for the computer to show the comparison of what would happen if you choose the min conflict row or if you choose another row (maybe randomly). For example, if you run the algorithm 100 times with each algorithm (min-conflict and random) you can count how often it finds the solution, and that would show that min-conflict works better than random.

[Dragneel7]

I guess that is better approach, I believe it will be relatively easy to implement the second idea to let user choose any row and then show the number of steps that he has to go in order to reach the solution and give an option of animate in which computer uses the min-conflict algorithm and show the users the no. of steps in this case. Which as you said will help him realize that min-conflict is a better and faster algorithm. Or we can use 2 different boards side by side where one boards uses random algorithm to find the solution and the other follows the min algorithm path and thus show the user what is happening at each step(as is currently being shown) and the total no. of steps required to solve the problem. This is will help in understanding why min-conflict is a better approach. I don't think that doing 100 simulations would be beneficial due to time or no. of steps it may take. I think the second approach of visualization and understanding is more reader friendly and easier to implement. @redblobgames what are your thoughts of the above mentioned 2 ways?

[Dragneel7]

@redblobgames I have implemented the third idea, please review that the following visualization can solve the purpose for the reader.

[redblobgames]

I agree, the visualization you have shows that min-conflict works better than random. I think we should still think about how to visually explain how min-conflict works. Hmm.

[Dragneel7]

Do you have any idea how can we make the visualization more descriptive.

[Dragneel7]

@redblobgames Can you please suggest some ideas for the visualization. P.S. Kindly review the previous PR. Thanks

[redblobgames]

The code in the PR is a bit confusing, as it seems to include unrelated changes to Ch 3. Be sure to go through all your code and make sure it has consistent indentation, spacing, and spelling.

For the visualization, sometimes these things don't work out and we have to rethink them. Sometimes they don't work out and we have to throw them away and start again. I think the visualization you have now says: “min conflict works better than choosing randomly”. For the visualization to be interesting we want to be able to answer: is this a surprising or unexpected result? is it something that does the interaction teach this concept better than if you read that statement in the book? what is the student doing that helps them learn the concept better?

The problem is that the concept “min conflict works better than choosing randomly” does not seem to be very compelling. You would expect that an algorithm would do better than choosing solutions randomly. And there's not much the student is learning by watching it, especially because all the information is presented as numbers in the bottom.

Let's try to figure this out the other direction. I am guessing you want the student to watch the animation, instead of reading the numbers at the bottom. What happens at each step? Every 1.0 seconds, you change the board. In 1 second, the student can see that you changed the board. But it is hard to understand why that move is made. It is too fast for the student to analyze the board, look for all the conflicts, figure out which of the possible moves has the fewest conflicts, and see that the choice was the right one.

What can we do to help the student understand why that move was made?

[Dragneel7]

Like you said maybe we can add an event on hover over a queen which highlights the min-conflict algorithm on the board. Like highlight the conflicting position and show the number of conflicts in that row. @redblobgames Should we allow him to make the move or make the move as decided by the algorithm? This approach will not be feasible with the random board because that board takes more than 200 steps in general to reach the solution. Maybe I can discuss it on the gitter channel and take some suggestions or should I follow what I mentioned above.

[redblobgames]

I think if you're asking the reader to make the move, then you wouldn't have a separate min-conflict and random board. Instead, you would let them decide the move. You can show the conflicts on each row and let them pick any choice. That way the reader can try choosing randomly or choosing min-conflict or choosing any other strategy. Sure, happy to chat on gitter. Sorry I haven't been around every day.

[redblobgames]

Closing for inactivity. Current direction of aima-javascript is to build visual explanations of concepts instead of demonstrations of algorithms. This visualization may be useful for that but it's something to revisit when this project is active again.