0

I know that with regression it is possible to generate a mathematical function based on experimental data. I was wondering, maybe there is a way to generate something more complex. I have a single player logical game which is hard to solve:

There are 37 glass globes in holes:

    |o|o|o|
  |o|o|o|o|o|
|o|o|o|o|o|o|o|
|o|o|o|o|o|o|o|
|o|o|o|o|o|o|o|
  |o|o|o|o|o|
    |o|o|o|

You have to remove one globe at the beginning (I started with the middle one):

    |o|o|o|
  |o|o|o|o|o|
|o|o|o|o|o|o|o|
|o|o|o| |a|b|o|
|o|o|o|o|o|c|o|
  |o|o|o|o|d|
    |o|o|o|

After that you can step over a single globe in horizonatal or vertical direction (I stepped here with "b" over "a", so I removed "a" from the playground):

    |o|o|o|
  |o|o|o|o|o|
|o|o|o|o|o|o|o|
|o|o|o|b| | |o|
|o|o|o|o|o|c|o|
  |o|o|o|o|d|
    |o|o|o|

Now I stepped again (with "d" over "c"):

    |o|o|o|
  |o|o|o|o|o|
|o|o|o|o|o|o|o|
|o|o|o|b| |d|o|
|o|o|o|o|o| |o|
  |o|o|o|o| |
    |o|o|o|

The aim of the game that only a single globe should remain. Now that is extremely hard to achieve, I have less than 1% success rate and I don't have the winning strategy.

Is it possible to generate an algorithm, which can solve the problem by many different scenarios (so which has a strategy)?

I was thinking on genetic algorithms or neural networks, so something which can learn the basics from me and after that develop itself by gaming more, but I have no experience with these methods, so I don't know where to start, and which one would work. I am aware that it is possible to solve the problem manually, but from that I would not learn anything about artificial learning...

  • 5
    This is known as peg solitaire. Once you known the name of the game, you can find lots of solutions (and problem assignments) for it. Backtracking is a classic approach as is going backwards (start form the solution and go backwards). Once you realize how to solve the problem for the general case you will realize that machine learning is completely unnecessary for this problem. – user40980 Dec 3 '14 at 17:22
  • @MichaelT Thanks! At least I know the name of the game. I know that it is possible without machine learning, but I want to learn how to solve the problem that way... – inf3rno Dec 3 '14 at 17:41
  • 1
    @inf3rno have you taken any classes in artificial intelligence? They should cover the basics of GAs and how to create a basic program that implements one. – user22815 Dec 3 '14 at 18:07
  • @Snowman I studied biotechnology. Software engineering is just a hobby for me, but it can be handy by modeling biological systems and probably by predicting new biochemical pathways or discovering regulation mechanisms. It is much harder to solve these kind of problems manually, and I think this little game is a good starting point to learn something useful. It is easy to check, and a regular PC is enough to run it... Can you suggest something about how to start with GA in the current scenario, or generally? – inf3rno Dec 3 '14 at 21:39
  • Honestly, the Wikipedia article has plenty of references including some books. I took a cursory look through a few of the links and I would hazard to guess that someone who can study biotechnology should be able to grasp that material as well. Unfortunately I do not have several days to review the material in-depth to find the best references, but I hope that helps point you in the right direction. – user22815 Dec 4 '14 at 2:41
3

It's possible that heuristics exist which improve your success rate, and if they exist, it's possible that you can program something that will find them.

But for a game this small you're almost certainly better off programming a complete search and looking at the solutions that pop up. Then, when you compare what works and what doesn't, your human brain will start to do its thing and pattern-match until you have a better idea of which features of a strategy are relevant to success and which aren't.

  • Ofc. my human brain can do that work too, but this question is about learning new skills in programming, and not about figuring the problem out on my own... – inf3rno Dec 3 '14 at 17:47
  • What do you think, how is it possible to find those heuristics in an automated way? – inf3rno Dec 3 '14 at 17:47
  • 1
    An exhaustive search is clearly more efficient for a problem of this size. However, I think using a GA to solve this problem is interesting because it will likely be more efficient for larger problem spaces. For example, a board that is a thousand pegs wide. – user22815 Dec 3 '14 at 18:05

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.