5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thanks. They seem like very modern papers. Surprising! I'll take a look. $\endgroup$
    – zooby
    Commented Nov 11, 2019 at 4:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Omegastick
    Commented Nov 11, 2019 at 6:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – John Doucette
    Commented Nov 11, 2019 at 14:06
  • 1
    $\begingroup$ 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! $\endgroup$
    – zooby
    Commented Nov 11, 2019 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – zooby
    Commented Nov 11, 2019 at 16:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .