How can I code this problem? (C++)

Question

I am writing a simple game which stores datasets in a 2D grid (like a chess board). Each cell in the grid may contain a single integer (0 means the cell is empty). If the cell contains a number > 0, it is said to be "filled". The set of "filled" cells on the grid is known as a "configuration".

My problems is being able to "recognize" a particular configuration, regardless of where the configuration of cells are in the MxN grid.

The problem (in my mind), breaks down into the following 2 sub problems:

1. Somehow "normalising" the position of a configuration (for e.g. "rebasing" its position to (0,0), such that the smallest rectangle containing all cells in the configuration has its left vertice at (0,0) in the MxN grid

2. Computing some kind of similarity metric (or maybe simply set difference?), to determine if the current "normalised" configuration is one of the known configurations (i.e. "recognized")

I suspect that I will need to use std::set (one of the few STL containers I haven't used so far, in all my years as a C++ coder!). I would appreciate any ideas/tips from anyone who has solved such a problem before. Any code snippets, pseudocode and/or links would be very useful indeed.

Answer 1

This may be overkill for a small application, but OpenCV has some excellent image recognition and blob finding routines. If you treat the 2D board as an image, and the integer as brightness, it should be possible to use functions from that library.

And the link: http://opencv.willowgarage.com/documentation/index.html

Answer 2

Sounds like you want to feed your chessboard to a neural network trained to recognize the configuration.

This is very similar to the classic examples of image classification, with the only complication being that you don't know exactly where your configuration thingy will appear in the grid, unless you're always considering the whole grid - in that case a classic 2 layers network should work.

HTM neural networks implementations solve the offset problem out-of-the-box. You can find plenty of ready-to-use implementations starting from here. Obviously you'll have to tweak the heck out of the implementations you'll find but you should be able to achieve exactly what you're asking for to my understanding.

If you want to further investigate this route the Numenta forum will be a good starting point.

Answer 3

you can use a neural network for that job.

if you lookfor neural network shape recognition i think that you can find something usefull. you can find tons of library that may help you but if you have no experiece with NN this could be a little hard, but i think that is the easiest way

Answer 4

Similarity metrics are a massive area of academic research. You need to decide what level of sophistication is required for your task. It may be that you can simply drag a "template pattern" across your board, raster style, and for each location score +1 for a hit and -1 for a miss and sum the score. Then find the location where the template got the highest score. This score_max is then your similarity metric for that template. If this method is inadequate then you may need to go in to more detail about the precise nature of the game.

Answer 5

Maybe you could use some hash function to identify configurations. Since you need to recognize patterns even if they are not at the same position on the board, this hash should not depend on the position of the cells but on the way they are organized.

If you store your 2D grid in a 1D array, you would need to find the first filled cell and start calculating the hash from here, until the last filled cell.

Ex:

-----------------
|   |   |   |   |
-----------------
|   | X | X |   |
-----------------
|   |   | X |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   |   |   | X | X |   |   |   | X |   |   |   |   |   |
----------------+---------------+---------------+----------------
                    |_______________________|
                                |
               Compute hash based on this part of the array

However, there are cases where this won't work, e.g. when the pattern is shifted across lines:

-----------------
|   |   |   | X |
-----------------
| X |   |   |   |
-----------------              Different configuration in 2D.
| X |   |   |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   | X | X |   |   |   | X |   |   |   |   |   |   |   |
----------------+---------------+---------------+----------------
            |_______________________|
               Seems similar in 1D

So you'll need some way of dealing with these cases. I don't have any solution yet, but I'll try to find something if my schedule allows it!

After thinking a bit about it, maybe you could use two different representations for the grid: one where the lines are appended in a 1D array, and another one where the columns are appended in a 1D array. The hash would be calculated with these two representations, and that would (I think) resolve the problem evoked above.

Answer 6

This reminds me of HashLife which uses QuadTrees. Check out the wikipedia pages on HashLife and Quadtrees.

There's also a link at the bottom of the Wikipedia page to a DrDobbs article about actually implementing such an algorithm: http://www.ddj.com/hpc-high-performance-computing/184406478

I hope those links help. They're interesting reads if nothing else.