5

This at first sounds ridiculous. Of course there is an easy way to write a program to solve a wordsearch.

But what I would like to do is write a program that solves a word-search like a human.

That is, use or invent different strategies. e.g. search randomly for the starting letter; go line-by-line;

Probably the AI will eventually find out that going line by line looking for a given starting letter of a word is a good strategy.

Any idea how you would write such a strategy-finding AI?

I think the main "moves" would be things like "move right one letter in the grid", "store this word in memory", "compare this letter with first letter in memory" and a few more.

zooby
  • 2,196
  • 1
  • 11
  • 21

1 Answers1

4

This sounds like a problem that might be solvable with a LSTM-DQN approach, as described in Language Understanding for Text-based Games using Deep Reinforcement Learning by Narasimhan et al., 2015, and then extended to a domain very similar to your problem in Deep Reinforcement Learning for Syntactic Error Repair in Student Programs by Gupta et al., 2019.

The basic idea is to treat the array of letters each of which can be 'circled' or not, plus the position of a cursor as a state. An action is to move the cursor or toggle the state of a letter. You then model the problem as a reinforcement learning problem, with rewards given every time an entire new word becomes 'circled', probably with a caveat about not circling any invalid letters (otherwise, it'll just learn to circle everything).

This is just a guess, but it seems like it's very closely related to your problem, so it's likely to be effective.

John Doucette
  • 9,147
  • 1
  • 17
  • 52
  • 1
    Thanks. They seem like very modern papers. Surprising! I'll take a look. – zooby Nov 11 '19 at 04:55
  • 1
    This kind of AI (reinforcement learning) has only really come into its own recently. The field has existed for a long time, but wasn't been feasible for real problems until [2015](https://www.nature.com/articles/nature14236). – Omegastick Nov 11 '19 at 06:46
  • 1
    @zooby There are other (older) ways you could try to solve this problem, but this is the approach I think is most promising given the modern state-of-the-art. Hope you find it useful. – John Doucette Nov 11 '19 at 14:06
  • 1
    I think yes, it is theoretically a reinforcement leaning problem. I wonder, however, whether such methods would solve the problem in a realistically human timeframe given the amount of combinations involved.... Well, I may have to just try it! – zooby Nov 11 '19 at 16:00
  • 1
    An LSTM in theory should be able to solve the problem, but again I wonder about scaling... I feel like it needs some semantic knowledge somehow. – zooby Nov 11 '19 at 16:02
  • 1
    @zooby This approach will probably require many times more exposure to word-search problems than a human would (keep in mind: it's going to have to learn _English_ from scratch, as well as to take the right actions). The beauty of the approach, to my mind, is that it doesn't need semantic knowledge. This is increasingly true of most of the best approaches to language-related problems, and usually these systems scale _better_ than semantic ones, rather than worse. – John Doucette Nov 11 '19 at 16:33