[Ur-Quan]

Дальнейший текст будет слегка математизированным.
Итак, пусть у нас имеется хотя бы небольшая база понятий, содержащая правильные и неправильные ответы на вопрос. Игрок вводит ответ, и наша задача определить, какое из понятий он имел в виду.
Сама база должна постепенно расширяться с ростом числа вопросов. Изначально же она будет содержать достаточно скромное число понятий.
База B := пара (V, Q), гдее V - множество понятий vi, которые мы пока будем понимать в виде строк, и Q - множество связей между ними: Q = {(vi, vj)| vi, vj принадлежат V}. В итоге у нас выходит этакий семантический граф. На данном этапе мы пренебрежём связями между понятиями и обратим внимание на сами понятия.
Игрок может ввести и осмысленное слово, но если оно будет отсутствовать в базе, то всё равно должно будет преобразовано в одно из имеющихся там понятий. Грубо говоря, нам надо спроецировать введённое игроком на множество понятий. Если в результате мы получим понятие, являющееся правильным, то ответ игрока засчитывается. Если мы получим неправильный ответ, то, возможно, стоит попробовать какой-нибудь другой метод или проверить семантику.
Проекция определяется просто - это то понятие, расстояние от которого до введённого игроком слова минимально. Иными словами, пусть игрок ввёл строчку s. Тогда проекция P(s) = {v| d(s, v) <= d(s, w) для любого w из V}. Вообще, таких понятий может быть много. Будем исходить из либерального подхода: при попадании хотя бы одного правильного ответа в это множества ответ игрока засчитывается. Однако при этом мы должны гарантировать, что ответ игрока всё же хоть немного похож на правильный. Необходимо ввести предельное расстоние dmax, определяющие границы правильного понятия. Если расстояние между введённым игроком словом и любым из правильных понятий больше, чем dmax, то ответ не может быть засчитан.
Как же определить расстояние между словами? Необходимо учесть, что игрок может случайно нажать не на ту клавишу или нажать на лишнюю клавишу, или вообще пропустить букву. Всё это должно быть засчитано.
Наиболее удобным вариантом для определения "похожести" двух слов считаю нахождение самой длинной одинаковой подпоследовательности букв, входящей в оба слова. Вот, например, выделена общая подпоследовательность в понятиях "Медный всадник" и "Меднй всаадник". Чем длинне такая подпоследовательность, тем понятия сильнее похожи. Например, в данном примере ответ вполне можно принять, несмотря на то, что полного совпадения нет.
Расстояние вводится по формуле
d(s1, s2) = max (длина s1, длина s2) - длина общей подпоследовательности. При этом вроде бы выполнены все свойства расстояния. Таким образом, мы можем вычислить расстояние между введённым ответом и каждым из понятий и найти минимальное. Мы и получим понятие для анализа.
Надо позаботиться лишь об одном - чтобы программа не стала засчитывать всё подряд. Если ответ игрока неверен, то он не должен оказаться слишком близко к правильному. Это обеспечивается просто тем, что база вводится уже с некоторым достаточным числом понятий.