Автоматический зачёт ответов

Автоматический зачёт ответов

Попробуем разобраться с зачётов ответов на вопросы без участия человека. Возможно, это позволит выработать какие-то общие правила для зачёта ответов вообще.

• вопрос, требующий ответа;
• база знаний, помогающая нам определять правильные ответы;
• набор правил, позволяющих дать ответ на вопрос, верен ли ответ;
• собственно ответ игрока.

1. Орфографический - вы написали ответ неправильно, но невооружённым глазом видно, но он верен (например "сабака" при правильном "собака");
2. Семантический - написали вы ответ по правилам русского языка, он не совпадает с авторским, но вы имели в виду то же самое ("Советский союз" вместо "СССР") или почти то же самое ("РСФСР" вместо "СССР", тут с зачётом надо быть аккуратнее).

Что касается орфографии, то тут сразу же можно выделить три подхода:

1. Жёсткий подход. Вы написали слово по правилам орфографии, и оно не совпадает с авторским ответом. Значит, вы имели в виду что-то совсем другое. Такой ответ не может быть засчитан с позиции орфографии ("СЕНТО" при ответе "СЕАТО").
2. Мягкий подход. Вы написали слово, которое есть в словаре, но оно мало отличается от авторского ответа. Так что, вообще говоря, ваш ответ можно и засчитать ("шубы" вместо "губы").
3. Сложный подход. Ваше слово есть в словаре, и оно засчитывается лишь тогда, когда понятно, что вы не могли ответить именно это. Например, если вопрос про части тела, а вы отвечаете "шубы", то, скорее всего, имелись в виду "губы", и надо засчитывать. Если же между вашим словом и авторским ответом есть сильная ассоциативная связь ("СЕНТО" и "СЕАТО" - два союза), то засчитывать ваш ответ нельзя.

Пока речь шла об ответах в виде одного слова. А что делать, если авторский ответ или ответ, данный игроком, состоит из ряда слов? Как тогда быть?
Здесь тоже можно подходить по-разному. Можно работать с каждым словом по отдельности, а можно со всей фразой целиком. Второе предпочтительнее, так как позволяет учитывать ситуации с разным количеством слов в авторском ответе и в ответе игрока. В любом случае ответ игрока должен быть преобразован в какую-то стандартную форму.

Если ответ игрока отсутствует в словаре, то необходимо найти слово из словаря, максимально похожее на ответ. Если был дан ответ "слан", то наиболее похожим словом из словаря будет "слон".
Отдельной проблемой являются также формы слов. При авторском ответе "мороз" можно дать ответ "мороза", и он должен быть засчитан. При этом речь идёт о правилах склонения и других способах изменения формы сова, которые также должны быть учтены.

Если орфографический подход не позволил принять ответ, на смену ему приходит семантический. Принять в таком случае ответ - куда более нетривиальная задача.
В настоящее время у меня есть идея сделать что-то вроде словаря синонимов, в котором будут указаны тождественные конструкции. Скажем, "РФ" = "Российская Федерация", "А.С. Пушкин" = "Александр Сергеевич Пушкин". Но это довольно-таки поверхностный подход.
По идее, между любыми двумя понятиями можно установить степень их связи (ассоциации между ними) и вид иерархии.

Понятие - это смысловая единица, которая воспринимается как единое целое. Может быть словом, словосочетанием, выражением, даже предложением. Скажем, понятиями будем считать следующие элементы списка: "слон", "колесо обозрения", "ни рыба ни мясо", "А судьи кто?". Авторский ответ представляет собой совокупность понятий, которые удовлетворяют вопросу. Не должно быть понятий, которые подходят в качестве ответа, не входят в авторский ответ или не являются семантически близкими к нему.
Игрок же даёт ответ не в виде понятия, а в виде строки, которая может содержать и несколько понятий. Это уже проблемы игрока; думаю, что его ответ стоит всё же считать одним понятием.
Наш словарь состоит из понятий и связей между ними. Понятное дело, что сразу такой словарь не создать, но он может расширяться с появлением новых вопросов и ответов.
На данный момент мне видятся три вида связей:

1. Иерархия "целое - часть". Нос - часть человека. Крыло - часть птицы. Это связывает понятия между собой.
2. Иерархия "общее - частное" . Пушкин, Достоевский, Толстой - всё это частные случаи писателей. Здесь лежит ключ к автоматической генерации неправильных ответов. Если авторский ответ "Пушкин", то неправильным является любой другой писатель. С помощью этой иерархии понятия объединяются во множества. "Пушкин" будет принадлежать разным множествам, таким как "поэты", "русские" и пр.
3. Ассоциация. Степень смысловой связи между понятиями. Чем она выше, тем выше вероятность, что вы ответили верно. Например, степень ассоциации между понятиями "СССР" и "Советский Союз" можно считать равной 1, то есть они тождественны. Это - возможный критерий семантического зачёта ответов.

Продолжение следует :)
Пока же хотелось послушать ваше мнение на этот счёт.

добавлено через 7 минут
Хм, мы это вроже обсуждали уже.
Вот, например, вопрос:
"Сколько колец...?" Набираю ответ: "16 17 18 19 20 21". И засчитано. Каково?
"Этот русский писатель..." Пишу: "Чехов Толстой Достоевский". Тем самым, вероятность ответа увеличивается в несколько раз. А как быть с темой "От 2 до 5"?

С описательными ответами - да, плохо, но в случаях, когда пакет составляется на основе уже готового пакета, вопросы приходится оставлять без изменений.

Короче это можно сформулировать так: "Как за две недели работы и сто рублей денег сварганить искусственный интеллект?".
ПМСМ, как бы ни плевался Анатолий Рафаилович, при ограниченных ресурсах лучше правил "Умного казино" ничего не придумаешь.

Другая игра. Эффект присутствия рубит на корню. Мне больше по душе идея постепенного внесения зачитываемых ответов на КАЖДЫЙ вопрос. Предварительное тестирование в закрытом кругу и т.д. Вопросы с описательными ответами исключаются.

Глобальные словари синонимов нежизнеспособны. Синоним, являющийся явным зачётом на один вопрос, может быть явным незачётом на другой. СССР=Советский Союэ? А если тема - "4 буквы"?

Это всё имеет смысл делать только для очень серьёзного продвижения игры. ПМСМ, как водится.

Так кого обманывать-то?

Это уж во всяком случае менее проблематичная ситуация, чем предлагавшаяся возможность править счёт вручную.

А сжульничать при желании можно всегда. Например, выиграл кнопку, поставил паузу, чтобы время на обдумывание не тикало - и думай, сколько влезет, ещё в Яндекс можно слазить...

ЗАМ, в числе наших планов (смотри соответствующую ветку) и создание и поддержка компьютерной версии СИ. Так что может быть, что усилия Володи перестанут быть частным делом, если он сам не будет возражать, конечно. Тогда ваши ремарки и правки могут оказаться весьма полезны.

Я сейчас пишу пакет для этой игры.Описательных ответов практически нет.Стараюсь сделать их как можно однозначнее.Разве только в одном месте - сложная иностранная фамилия.Там я предлагаю несколько вариантов написания.Если спрашивается какой-либо человек, литературный персонаж и т.п. принимаются в равной степени фамилия и имя/фамилия.

Искусственный интеллект мы вряд ли изобретем,поэтому лучше полагаться на естественный.Либо автор,либо разработчик,либо третье лицо составляют множество принимаемых ответов,учитывая все альтернативы.По крайней мере на первых порах.

Кстати, вопрос,который я снял из пакета(показалось неоднозначным).

Студенты Мельбурнского текстильного колледжа установили мировой рекорд,изготовив костюм за 1 час 34 минуты 33 секунды.Первые секунды рекорда ушли на этот процесс.

Ответ:Поимка овцы.

Я задался вопросом,какие ответы надо принимать.


Владимир,извините за задержку.Обещал давно,но никак не могу закончить.Пришлось вводить "Сборную солянку" и две мои подправленные темы с чемпионата Москвы.Но до Нового года обязательно пришлю.

В Молчанов , так о том и речь. Огромных успехов Володе вообще и игре в частности - кто же против-то! Я так только за, и пятью руками притом. Кроме того - слышал я краем уха, что тестированием игры озаботился некто Максимов К. Вот тут-то мы все и поймём, как же мы ни фига не понимаем...

Snip1 , тоже дело хорошее. Однако, ПМСМ, не самое хорошее - игра всё-таки телевизионная. Мне кажется, тут надо не писать вопросы кому-ни-попадя (и уж особенно Байраму - из пушки на Луну у него с мыса Канаверел летали, убивать). И ты в данном случае тоже называешься кто-ни-попадя, и я, и мы все. А надо взять и тщательно подобрать подлинные вопросы из телеСИ - и именно с однозначными ответами, и составить несколько таких пакетов, и комментарии в "настоящем стиле ПБК" (да хоть и опять же подлинных подобрать), и всё такое. Есть, например, игра "О, счастливчик!" (ещё не "миллионер" - а может, и "миллионер" уже есть) с подлинными же вопросами - смотрится вполне, вполне...

"КХСМ" есть. Насчёт подлинности - не знаю. С живым Галкиным. Так по выбору же ответов там, э-э-э, полегче будет. А здесь именно в зачёте проблема.

Nikolaev N. ,
правила "Умного казино" входят в действующие. А попробовать улучшить хочется :)

grzegorz ,
правда, я не очень представляю вопрос, на который необходим столь точный ответ...

Strel ,
обманывать можно только себя, да. Это можно реализовать, но только как переходную меру. Уж слишком неточно.

В Молчанов ,
ни в коем случае не буду возражать, я только за! Тем более, что это может помочь увеличению популярности телеигры.

Snip1 ,
ничего страшного нет. Когда напишете - тогда и выйдет. Описательные вопросы на данный момент действительно лучше исключать.

зам. ,
дык где бы эти подлинные вопросы раздобыть? Там база получится приличная, на десятилетия хватит.
Да, и кто будет всё это обрабатывать? :)

"Зверёк на известном портрете" - в зачёт и фуро, и горностай. "Бочка в японской бане" - это фуро. Но не горностай:)
Вопросы, в которых один из возможных синонимов насмерть рубится в формулировке...

Раздобыть-то не проблема - особенно если редакция не против. Да и без её содействия тоже - бери вон обзор-протоколы Фатимы и нет проблем. А вот обработка - да, работа огромная, кропотливая и квалифицированная. Я бы позанималСИ - если бы других дел не было...

Зачёт ответов. Орфография

Дальнейший текст будет слегка математизированным.
Итак, пусть у нас имеется хотя бы небольшая база понятий, содержащая правильные и неправильные ответы на вопрос. Игрок вводит ответ, и наша задача определить, какое из понятий он имел в виду.
Сама база должна постепенно расширяться с ростом числа вопросов. Изначально же она будет содержать достаточно скромное число понятий.
База 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) - длина общей подпоследовательности. При этом вроде бы выполнены все свойства расстояния. Таким образом, мы можем вычислить расстояние между введённым ответом и каждым из понятий и найти минимальное. Мы и получим понятие для анализа.
Надо позаботиться лишь об одном - чтобы программа не стала засчитывать всё подряд. Если ответ игрока неверен, то он не должен оказаться слишком близко к правильному. Это обеспечивается просто тем, что база вводится уже с некоторым достаточным числом понятий.

Возникла у меня одна забавная мысля.
И, похоже, я могу предложить т.н. внешнее решение для обсуждаемой проблемы.

Суть вот в чем.
Человек в эту игрушку играет для себя - вот он и должен быть главным судьей своих собственных ответов. Если ему зачем-то хочется себе подсуживать, самолюбьице щекотать - так и флаг в руки.
А ежели не захочется, вздумается быть честным - так тем более хорошо-с.

Короче, так.
После сдачи ответа программа объявляет, зачтен ли он. Если зачтен - быть по сему. А вот если не зачтен - на панели игровой есть особая кнопочка:
Ткнешь в нее мышкой - ответ будет зачтен.
Можно, кстати, предусмотреть такую возможность и после ответа "соперников".

"Соперников" - это как? Тыкать кнопку типа "это Друзь и имел в виду"? То есть зачесть им побольше, чтобы в финале было поинтереснее?

Была у меня аналогичная мысль, но более примитивная: каждый раз отдавать право определения верности ответа игроку, но Анатолий Рафаилович придумал гораздо лучше и элегантней.

А кстати, вопрос к Володе - как насчёт игры по сети (для начала - по локальной, например)?

Дело даже не в этом. Если уж программой и рэндомом предусмотрено, что ответ он даёт неправильный, так значит, неправильный.

Кто-то что-то похожее предлагал, ну раз таких пожеланий много - отчего бы и не сделать... Но это слишком грубый способ :) Всё-таки хочется, чтобы пореже приходилось бы прибегать к такому методу исправления и работал бы автоматический зачёт. Это будет крайняя и переходная мера, к тому же она не может быть использована в многопользовательской игре.
Пусть такая кнопка будет опциональной: можно вывести, можно убрать.
А вот тут уже правильно заметили, что соперники всегда выбирают точную верСИю - или правильную, или нет.

добавлено через 34 секунды
Ой, далеко до этого ещё... :)

Не думаю, что автоматический зачет лучше. Как раз "Безумное казино" продемонстрировало всю слабость этого подхода: для него требуются особые вопросы - такие, ответ на которые не просто однозначен, но и однозначно формулируется (в том числе однозначно с точки зрения орфографии и вариантов написания). Это ОЧЕНЬ обедняет игру.

Увы, вы забываете, что возможна ошибка и у самого автора вопроса.
Если "соперник" ответил правильно (например, дуально) - почему бы не дать возможность играющему зачесть этот ответ? В телеигре такое бывало, а уж в спортивном свояке авторские ошибки и неточности - просто нередки.

В общем, кнопка "Зачесть - и все!" мне представляется не опциональной, а самонужнейшей.
Пусть игрок сам решает, хочется ему ею пользоваться или нет.

Во избежание злоупотреблений можно ограничить число использований этой кнопки за одну игру. Как видеопроверки в теннисе.

Анатолий Рафаилович, просто в ситуациях с неправильным ответом компьютерного игрока подразумевается, что он должен ответить неправильно. А потом ему уже назначается како-то из "неправильных" ответов. Поэтому в случае дуали необходимо просто подставить другую верСию в уме :) Ведь он должен-таки ошибиться :)
К тому же, это усложнит управление. Необходимо будет ещё уточнять после нажатия кнопки, кому надо перезачесть. А так будет очень просто: нажал кнопку - тут же вопрос был пересмотрен.
Кстати, возможно нужно сделать так, что при правильном ответе игрока и несовпадении этого ответа с основной авторской верСИей, эта верСИя появлялась бы на экране. При этом игрок может решить, что его ответ как раз-таки является неправильным, и использует заветную кнопку для достижения обратного эффекта :)
Да и неправильные верСИи обычно подбираются такие, чтобы дуалей не было. Так что, думаю, этим-то можно пренебречь. А впоследствии просто убрать дуаль.

При всём этом я продолжу улучшение критериев автоматического зачета, дабы уменьшить частоту использования этой кнопки, чтобы она применялась лишь в исключительных, особо вопиющих случаях :)

добавлено через 1 минуту
Да это уж бесполезно - если уж один раз произвёл апелляцию, то прецедент имеется. Значит, пожалуйста, апеллируй ещё.
Да и вдруг слишком много несправедливых незачётов будет?:rolleyes:

добавлено через 2 минуты
Да, Григорий, омонимы дело портят :) Ну а если вести речь о тождественных понятиях?
Скажем, вопрос про СССР в теме "4 буквы". И игрок смело жмёт и называет "Советский Союз!". Зачесть или нет?

Вот поэтому я и радуюсь, что до сих пор не вёл игр и не сталкивался с такими проблемами:)
Рассуждения, могущие быть полезными. СССР, Советский Союз, Союз Советских Социалистических Республик - явные синонимы при вопросе "Эта страна..." в теме "Спорт". А если "Закончите цитату:"Мой адрес - не дом и не улица, мой адрес - ...", то СССР - явный незачёт. Если в базе к каждому слову указаны логические синонимы, то в описании вопроса должно появиться поле "Незачёт" и там логические синонимы из базы, которые на этот вопрос не засчитываются.

Да, понятие "логический синоним" транзитивным не является.

Не исключено, что такой незачёт можно сделать не абсолютным, а вероятностным. С вероятностью p на вопрос A ответ B зачтём. Моделирование колебаний ведущего:)

О строках и подстроках

Итак, пусть игрок перед ответом вводит фразу "Я думаю, что это...". Или даёт слишком длинный ответ ("Памятник Петру Первому "Медный всадник"). Исходя из обычного сравнения строк и даже с учётом проектирования ответ не может быть засчитан. Тут нужно выработать более общую методику.
Strel и ещё кто-то предлагают искать ответ по наличию подстроки. Скажем, ищем в ответе игрока корень искомого слова и, если он там обнаружен, засчитываем ответ.
В терминах проекций мы получим следующее. Ищется наиболее длинная общая подпоследовательность в авторском ответе и в строке. Затем длина этой подпоследовательности делится на длину авторского ответа. если полученный результат оказался равен единице, то, очевидно, ответ обнаружен в строке целиком. Если результат меньше единицы, то ответ обнаружен лишь частично.
Несомненно, надо делать анализ ответа более ЛИБЕРальным для того, чтобы избегать несправедливых незачётов. Но при этом ни в коем случае не должно возникать несправедливых же зачётов.
Поэтому если в строке наравне с правильным ответом обнаружено и наличие заведомо неправильного, то ответ должен быть незачтён. Вопрос лишь в том, что считать заведомо неправильным и как это указывать...
В настоящее время нет возможности указать ВСЕ возможные неправильные ответы. Поэтому ввод анализа на наличие подстроки представляется мне пока сомнительным и ненадёжным. Впрочем, как скажете...

У меня в новой версии в первой игре было пять, но думаю, это скорее исключение, чем правило.

По-моему, всё же идея здравая, и ограничение нужно. Вот кто-нибудь играет-играет, а потом думает: дай-ка нажму, что я про это и говорил - и нажмёт. Ух ты! Вот же как надо побеждать! И давай давить каждый раз и хохотать. А мы ему на шестой раз - опа! и говорим: "Хватит испытывать наше терпение, ответ мы всё равно не засчитываем!" И он понимает, что не такие дурачки авторы. И снова играет с интересом, нажимая лишь тогда, когда это действительно необходимо.

Strel ,
если человеку интереснее играть, засчитывая себя всё подряд - то это не лечится ограничением :)

Саша, растешь!

Да лечится же ж.

По-моему на сегодняшний день простого поиска подстроки или варианта, предложенного Ur-Quan`ом (поиск максимальной подстроки) достаточно. Нормальный игрок будет играть честно. Вот в сетевой игре нужно быть более строгим, но не забывать и о скорости реакции компьютера. Вряд ли кому-то доставит удовольствие ждать даже 3 секунды после каждого ответа, пока компьютер обойдёт огромный граф или базу данных.

В общем-то, идея здравая. Не настолько же всё плохо, чтобы применять кнопку каждый раз :)

Еще раз повторяю: каждый играет для себя.
Хочется ему хоть каждый ответ себе зачесть - да на здоровье. :)
Кому это мешает?

А тот, кто хочет реально себя оценивать, - и так злоупотреблять не будет.

И волки сыты...

Пришла мне в голову одна весьма интересная мысль.
Размышления были следующими: сделаешь зачёт ответов пожёстче - сразу будут жаловаться на незачёт падежных форм; сделаешь зачёт помягче - будут сетовать на то, что программа всякую ерунду принимает.
И вот какое придумалось улучшение: необходимо уделять больше внимания совпадениям в начале слов, нежели в конце. Связано это с естественным строением русского языка: если два слова отличаются лишь ближе к концу, то, скорее всего, это две формы одного и того же слова.
Только, разумеется, старый зачёт надо тоже сохранить в силе, т.е. при опечатке в первых буквах слова всё равно ответ должен засчитываться. Просто при приближении к концу слов образца (авторского ответа) зачёт становится либеральнее.
Поскольку количество слов в авторском ответе и ответе игрока в общем случае различается, то сравнивать по-прежнему нужно строки, а не слова. Однако изменения коснутся вот чего.
Раньше за каждый совпадающий символ общей подпоследовательности начислялось 1 очко. Число набранных очков и составляло длину этой подпоследовательности. Затем это число делилось на длину образца, и делался вывод о том, можно ли принимать.
Теперь за каждую совпавшую букву будет даваться разное число очков в зависимости от её позиции в авторском ответе. Возможны два подхода (на примере "Медного всадника"):
1.
2.
Все очки, полученные за совпадения, суммируются. Затем определяется максимально возможное число очков. После этого первое делится на второе и снова сравнивается с допустимой мерой совпадения. Как видите, совпадения в начале слов теперь играют бОльшую роль. Пробелы, как всегда, в сравнении не участвуют.
Какой из подходов лучше - насчёт этого надо подумать. Мне более симпатичен первый, ведь в нём уменьшается роль маленьких слов. например, во втором подходе за совпадения первых букв в словах "и" и "медный" даёт одинаковое число очков - 1, хотя первое слово вроде поценнее будет. Впрочем, надо ещё подумать: ведь первый подход при этом будет требовать и более точного совпадения с длинными словами.

Не только о числах

Продолжаем, если это кому-нибудь интересно :) Может, подскажете чего-нибудь ещё :)

Выяснилось, что с числами такой метод зачёта не работает. Ведь, скажем, 1839 год сильно похож на 1899, и программа засчитает такой ответ, хоть и не должна. Если назначить цифрам слишком большие веса, то также получится не очень хорошо - "15 сентября" будет засчитываться при ответе "15 декабря". Тут нужно придумать что-то другое.
Например, возможен такой подход: цифры проверяются отдельно старым способом (на точное совпадение), а вся остальная фраза - на частичное совпадение. При этом ответ засчитывается, если при обоих сравнениях получен утвердительный ответ.

Также нехорошо оказалось то, что правильный ответ может быть найден и в беспорядочном наборе букв. Например, правильный ответ "Крутой", а даётся ответ "Вокруг света". Ясно что буква "т" в ответе никакого отношения к правильному ответу не имеет, и её учитывать не стоит. Поэтому должен существовать некий механизм отбрасывания лишних совпадений. Можно опираться на три подхода:

1. Отбрасывать короткие совпадения.
2. Отбрасывать совпадения, расположенные слишком далеко от остальных.
3. Комбинированный подход: отбрасывать совпадения, расстояние от которых до остальных в определённое число раз превосходит их длину.

В качестве эксперимента можно попробовать следующий метод: отбрасывать одиночные совпадения, рядом с которыми на расстоянии 2-х символов нет больше ни одного совпадения (такие символы, скорее всего, совпали случайно).

С вариантами ответов получатся, например:
Алексей Николаевич Толстой, А.Н. Толстой, А. Н. Толстой, Ал-й Николаевич Толстой, Алексей Ник. Толстой, Алексей Н. Толстой, Ал-й Ник. Толстой, Толстой Алексей Николаевич, Толстой А.Н., Толстой А. Н., Толстой Ал-й Николаевич, Толстой Алексей Ник. и т.д.

И все – правильные?

В большинстве своём они будут считаться правильными. Вот с перестановками слов не всё так гладко.
Но вообще, существует же общеприянтая форма "А.Н. Толстой"; в крайнем случае, можно предусмотреть засчитывание только её :)

На тему Алексеев Николаевичей :)

Ранее в игре использовались метасимволы, чтобы записать большое число вариантов ответа. Например, "Орлов*" означало и "Орлов", и "Орлова", и "Орловский". Но в связи с использованием новых критериев зачёта эти метасимволы больше не нужны.
Будет только одна конструкция, указывающая, что некоторые слова в ответе идут в произвольном порядке. Это фигурные скобки. В случае с А.Н. Толстым правильный ответ лучше всего записать в форме "{А.Н.} {Толстой}". Такая запись как раз и означает, что "А.Н." и "Толстой" могут идти в ответе игрока в любой последовательности, но желательно присутствие обеих компонент.
Разберём теперь важный пример. Пусть в ответе нужно указать 3 части света, и авторский ответ таков: "{Азия}, {Африка} и {Европа}". Игрок же отвечает "Европа, Азия, Африка". Как проверить правильность ответа?
Можно попробовать перебрать в авторском ответе все возможные комбинации частей света (получится шесть вариантов) и сравнить ответ игрока с каждой из них. При этом совпадение хотя бы с одним из вариантов ведёт к зачёту ответа. Но это достаточно утомительный подход. Думаю, что можно поступить гораздо более эффективным образом.
Можно сначала попытаться отыскать отдельные элементы (части света) в ответе игрока и определить, который из них встречается раньше остальных, какой - чуть позже, а какой - самым последним. Это и обеспечит выбор единственного варианта авторского ответа, который и будет использоваться при проверке правильности ответа игрока.

Боюсь ломиться в открытые ворота. Может, стоит использовать модификации расстояния Левенштейна?

Григорий, почитав про это, понял, что почти это и использую :)
Просто всё сведено не к трудоёмкому поиску числа операций для замены и удаления, а к поиску наибольшей общей подпоследовательности.