4
$\begingroup$

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importants of heuristics in it. George Katona (an early psychologist) published in the 1940s a paper about human learning and teaching. He mentioned the so called Katona-Problem, which is a geometric task.

Squares

Katona style problems are the ones where you remove straws in a given configuration of straws to create n unit squares in the end. In the end, every straw is an edge to a unit square. Some variations include 2x2 or 3x3 sizes of squares allowed as well as long as no two squares are overlapping, i.e. a bigger square 2x2 can't contain a smaller square of size 1x1. Some problems use matchsticks as a variation, some use straws, others use lines. Some variations allow bigger square to contain smaller one as long as they don't share an edge viz. https://puzzling.stackexchange.com/questions/59316/matchstick-squares

  • Is there a way we can view it as a graph and removing straws/matchsticks as deleting edges between nodes in a graph?

  • If so, can I train a bot where I can plugin some random, yet valid conditions for the game and goal state to get the required solution?

Edit #1: The following problem is just a sample to show where I am getting at. The requirement for my game is much larger. Also, I chose uninformed search to make things simpler without bothering about complex heuristics and optimization techniques. Please be free to explore ideas with me.

Scenario #1:

Consider this scenario. In the following diagram, each dashed line or pipe line represents a straw. Numbers and alphabet denote junctions where straw meet. Let's say, my bot can explore each junction, remove zero, one, two, three or four straws such that resultant state has

  • no straw that dangles off by being not connected to a square.
  • a small mxm square isn't contained in a larger nxn square (m
  • Once straw is removed, it can't be put back.

Initial configuration is shown here. I always need to start from top left corner node P and optimization... the objective is to remove straws in minimum hops from node to node using minimum number of moves, by the time goal state is reached.

       P------Q------R------S------T
       |      |      |      |      |
       |      |      |      |      |
       E------A------B------F------G
       |      |      |      |      |
       |      |      |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

Goal 1 : I wish to create a large 2x2 square.

At some point during, say BFS search (although it could be any uninformed search on partially observable universe i.e. viewing one node at a time), I could technically reach A, blow out all edges on A to create the following.

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

That is one move.

Goal 2 : I want to create a 3x3 square instead.

I can't do that in one move. I need the record of successive nodes to be explored and then possibly backtrack to given point as well if the state fails to produce desired result. Each intermediate state might produce rectangles which are not allowed (also, how would one know how many more and which straws to remove to get to a square) or dangle a straw or worse get stuck in an infinite loop as I can choose to not remove any straw. How do I approach this problem?

Edit 2:

For validation, figures 3, 4 and 5 are given below.

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F      G
       |             |      |      |
       |             |      |      |
       J------C------D------H      I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N      O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X      Y

The above figure (3) is invalid as we can't have dangling sticks TG,GI etc.

       P------Q------R------S------T
       |      |                    |
       |      |                    |
       E------A                    G
       |                           |
       |                           |
       J                           I
       |                           |
       |                           |
       K                           O
       |                           |
       |                           |
       U------V------W------X------Y

The above figure (4) is invalid as we can't have overlapping squares

       P------Q------R      S      T
       |             |             
       |             |            
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

Figure (5) is valid configuration.

$\endgroup$
  • 1
    $\begingroup$ I can give you specific examples and sample problems if needed. I just need to know the approach for concise state space representation as I need to make an android game out of this. $\endgroup$ – GundamOfOasis Aug 28 '18 at 20:13
  • 1
    $\begingroup$ Welcome to SE:AI! (Took the liberty of editing for readability, and adding some tags. I wish there were some formal, online sources talking about this matchstick problem. If you know of any reliable sources of info on it, please feel free to link.) $\endgroup$ – DukeZhou Aug 28 '18 at 20:32
  • 1
    $\begingroup$ Yes you can do that, looks quite straightforward....But if you want to achieve results in a acceptable time you may need to define some complex heurestics $\endgroup$ – DuttaA Aug 29 '18 at 3:56
  • $\begingroup$ @DuttaA, is there a way I can contact you other than commenting here? As mentioned earlier I am building a game and I could really use some advice from you. $\endgroup$ – GundamOfOasis Aug 29 '18 at 8:10
  • $\begingroup$ A welcome from me too. I wrote a small introduction about George Katona because this helps to motivate the group for finding better answers. If you want, you can take my suggestion back. I see that you have tried out the edit button as well. $\endgroup$ – Manuel Rodriguez Aug 29 '18 at 11:47
2
$\begingroup$

Welcome to AI.SE @GundamOfOasis!

Your intuition is right: this is fundamentally a problem for combinatorial search.

You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need to add a function that can determine whether a given state is valid or not, in addition to the usual function that checks whether it is your goal sate or not. Before adding each node to the queue of your search algorithm, check whether it is a valid state. If it isn't, don't add it.

The second issue you raise is that your search might enter an infinite loop. Since it is possible to remove zero edges from a state, this is a serious concern. There are two approaches to solving this. First, you can try storing all states that you have already visited in a fast data structure like a Hash Table. Before adding a node to your queue, check if it's already been processed. If it has been, don't add it. This may work, but the memory requirements grow exponentially in the number of moves required for a solution. It's sometimes worth it, but I think you can likely skip it for this problem.

A better approach if you're worried about speed is to switch your algorithm to something like iterative deepening, which has the good properties of BFS, but with much lower memory requirements; or to A* search if you can come up with an admissible heuristic for your domain (a good starting point: counting the number of junctions you'd need to remove sticks from to finish, if the robot could teleport, would be admissible).

Hope this helps!

Edit: Here's some pseudo-code for filtering out invalid moves:

function valid_state(State s){
    for stick in s.remaining_sticks:
        if stick is vertical:
           1. let side = walk up from the middle of stick until it becomes possible to turn right.
           2. let side += walk down from the middle of stick until it becomes possible to turn right.
           3. From the first junction above stick where we can turn right, try to walk *side* steps to the right.
           4. Then try to walk side steps down.
           5. Then try to walk side steps left.
           6. Repeat previous 5 steps but for the nearest junctions where we can turn left instead of right.
        else:
           Do exactly what's in the if above, but substitute "left" for "up" and "right" for "down".      
    if we could walk in a square successfully for every stick, this is a valid state, so return true. Otherwise, return false.     
}
$\endgroup$
  • 1
    $\begingroup$ Hello John. Thanks for the welcome. I want to keep this simple and let's go with BFS since I mentioned that in the question and it actually illustrates my problem with combinatorial uninformed search. You see, if I wanted to make a 2x2 large square, I could remove all edges from A, what if I wanted a 3x3. I need to essentially remove all edges from B,C and D as well. But since I am processing node by node, after removing all from A, if I remove all from say B, temporarily, it would result in invalid state as now I have a rectangle and not square. My question : How to define a move on a node? $\endgroup$ – GundamOfOasis Aug 29 '18 at 13:17
  • 1
    $\begingroup$ The problem starts with the state representation itself. My approach, currently, is to observe each junction as a node with 0:4 edges at any given time, where edges are the straws in this case. Second, the universe/environment is partially observable i.e. the bot can't teleport, it can operate on current state i.e. node. It can remove 0:4 edges. The moves cause the environment to change. My belief is that (I am relatively new to AI), the configuration of environment shouldn't be a part of state if environment is not fully observable. So, each move causes a new state and new environment. $\endgroup$ – GundamOfOasis Aug 29 '18 at 13:25
  • 1
    $\begingroup$ This presents an interesting scenario when defining moves (or successor functions but that's too long and technical). What constitutes an atomic move for a bot starting at P, processing one node at a time? Correct me if my assumptions are wrong as this is just a puzzle I saw somewhere that inspired me to create a game. I hope it's not bothering anyone. For me, it's a fun brain teaser and a valid scenario to teach machines about... geometry? $\endgroup$ – GundamOfOasis Aug 29 '18 at 13:31
  • 2
    $\begingroup$ @GundamOfOasis As it says in the answer, if you want to use uninformed search, you can just define a function that tells you whether a move is valid or not, and use that to filter the addition of new states to the queue in BFS. Is your question about how to write that function? That might be better suited for the stackoverflow main site. $\endgroup$ – John Doucette Aug 29 '18 at 13:54
  • 1
    $\begingroup$ Just for completion sake, is it too much to ask for a pseudocode for the same? The statement 'just define a function that tells you whether a move is valid or not, and use that to filter the addition of new states to the queue in BFS' doesn't necessarily answer 'How to define a move on a node?' or ' What constitutes an atomic move for a bot starting at P, processing one node at a time?'. Please note that I am well aware of the algorithm, it's the successor function (now that we agreed on the state representation) that bothers me. A set of moves that generates one valid state from another. $\endgroup$ – GundamOfOasis Aug 29 '18 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.