Задача от Родригеса. Логическая игра в числа.
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Задача от Родригеса. Логическая игра в числа. - 2010-05-18 20:12:57.920000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Задам и я задачку, по примеру Денатурата.
В школе мы играли в одну интересную игру, в "числа". Резались на уроках исписывая тетради с последней страницы. Как обстояло дело в других школах/городах/годах я не знаю, поэтому постараюсь поподробнее описать правила игры.
Итак. Играют двое. Каждый игрок загадывает четырехзначное число, состоящее из цифр от 1 до 9, причем цифры в числе не повторяются. Задача игроков - угадать число соперника за меньшее количество ходов. Игроки по очереди называют друг другу варианты , причем повтор цифр так же не допускается, в ответ получают от соперника два числа, например 2/1 первое показывает, сколько цифр совпало вообще, а вторая - сколько из них стоит а своих местах. Если число угаданно правильно, то ответ соответственно будет 4/4. Игрок , угадавший число соперника быстрее выигрывает. Если оба игрока угадали число соперника за одинаковое кол-во попыток, то засчитывается ничья.
Каждый игрок в своей тетради записывает два столбца.
Вверху левого столбца - свое загаданное число, под ним попытки соперника и ответы на них, в правом столбце - место под число соперника и , ниже , свои ходы и полученные на них ответы.
Запись партии выглядит так (пример):
Как видно из примера соперник угадал наше число раньше, на пятом ходу.
Задача - написать программу, которая в минимальном варианте выдает пользователю варианты и получает ответы. Алгоритм программы должен быть таким, что бы угадать загаданное число максимум с 7-й попытки (типично 5-6). Разрешается использование любых языков (не экзотических), консоль приветсвуется, эргономичность и красивый вывод столбика тоже, но они не главное - главное алгоритм, по которому будет р-ть программа.
В качестве опций можно добавить выбор варианта игры - с нулем и без нуля, а так же двухстороннюю игру, то есть программа загадает число, а игрок будет его угадвывать , делая ходы по очереди с программой.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-19 15:18:57.183333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Чёт никакой активности в теме, а задачка то ничего. Видимо, начать все боятся :) Ну начну я.
Чтобы найти оптимальный алгоритм, нужно как минимум поиграть в игру и понаблюдать за закономерностями. Те закономерности, которые сразу заметил я, позволяют вывести следующие полезные правила:
1) если сдвигать число последовательно, например, влево, а на место освободившегося элемента подставлять ещё не использованные элемент (1234 << 1 == 2345) можно заметить момент "выдвижения" или "вдвижения" цифры, которая есть в загадываемом числе. То есть, по аналогии с примером:
1234 2/0
2345 1/0
из последнего делаем вывод, что 1-ца была значащей цифрой, а 5-ка - нет. Точно также, если расклад такой:
1234 2/0
2345 3/0
то можно сделать вывод, что 1 - незначащая, а 5 - значащая.
2) аналогично значащим и незначащим цифрам в числе можно вести учёт актуальных и неактуальных позиций для каждой цифры. То есть, изначально все позиции для цифры (1, 2, 3, 4) - актуальные, т.к. она может распологаться на любой из них, однако с учётом движения цифр и логических правил, этот список можно уменьшить до одной позиции.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-19 19:47:51.806666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
нужно как минимум поиграть в игру и понаблюдать за закономерностями.
А кто не дает? Главное кого нибудь заинтересовать игрой.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-19 20:11:17.780000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Родригес
quote:
нужно как минимум поиграть в игру и понаблюдать за закономерностями.
А кто не дает? Главное кого нибудь заинтересовать игрой.
Походу быстрее будет написать такого "игорока", чем привлечь реального человека))
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-19 20:31:44.716666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
Походу быстрее будет написать такого "игорока", чем привлечь реального человека))
Не парься , вот моя программа, которую я искусственно углупил методом лоботомии (вырезал две процедуры) для тренировки. http://slil.ru/29165156
Используются цифровые клавиши, Enter и BackSpace.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-21 02:30:35.036666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Тэкс, сегодня уже не успеваю проверить свои идеи, поэтому просто topic up, может кто-нибудь ещё всё-таки пошевелит мозгами, а то чего то зашухарились :)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-22 16:42:36.023333
|
|
|
Як Истребитель
Сообщений: 410
Оценки: 0
Присоединился: 2010-01-27 19:48:58.473333
|
Слышал про такую игру, только называлась она "Яйца и курицы". 4 шара, каждый может принимать 9 значений-картинок.
Что касается алгоритма - вот так сходу только это придумал:
1. Увеличиваем каждую цифру последовательности на 1 (1111, 2222…..)
2. Если оказалось, что одна или более цифр попали, но стоят не на своих местах, останавливаем инкремент и переставляем их до полного попадания.
3. Идём дальше, не трогая попавшие цифры, и смотрим в п.2.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-22 16:58:47.970000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Як Истребитель, не пали - сейчас все побегут гуглить.
quote:
Аа оке, поправил =)
благодарю.
quote:
1. по правилам цифры не повторяются.
quote:
2.
3.
и сколько же ходов будет?
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-22 17:07:09.120000
|
|
|
Як Истребитель
Сообщений: 410
Оценки: 0
Присоединился: 2010-01-27 19:48:58.473333
|
Аа оке, поправил =)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-22 18:27:45.213333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Як Истребитель
Слышал про такую игру, только называлась она
у игры с десяток названий и две основных разновидности. алгоритм, впрочем, везде один и тот же
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-23 20:29:35.206666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Что же так туго то? Толи действительно сложная задача, толи не имея такого авторитета на форуме как Денатурат моя задача не привлекает решателей?
Задание не такое уж сложное на мой взгляд - ее решение было моей самой первой программой вообще, не считая всяких хелловордов с книг. Учился программировать одновременно с написанием программы.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-23 20:52:12.830000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Родригес
Что же так туго то?
у тебя превратное представление об уровне посетителей этого форума. представленная задача достаточно сложна, чтобы отсеять 95% читающих, и недостаточно практична, чтобы потешить ЧСВ ещё 4%
оставшийся 1% составляют люди, для которых эта задача не представляет сложности, и которые (скорее всего) не хотят мешать остальным показать себя (вроде rgo или _ruzmaz_). впрочем, есть надежда на kreol и Як Истребитель
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-25 00:43:20.286666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
На kreol надежды нету. По крайней мере ближайшую неделю-две :)
Могу только наспех предложить два направления решения.
Первое - по ограничениям: составляем для каждой цифры список возможных позиций, двигаем цифры и постепенно вычёркиваем те, которые по каким то причинам не подходят. Какие ограничения примерно понятно, не понятно какой должен быть алгоритм изменения числа.
Второе - генетические алгоритмы, т.е. выбираем число и начинаем его менять в сторону улучшения. Но навскидку там количество шагов очень быстро превысит число 7. Вообще, насколько я понимаю, число 7 в данном случае - это математически вычесленное значение, а не эмпирический факт? Просто в таком случае и первый и второй подход точно не прокатят, ибо они скорее эвристические.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-25 06:52:07.626666
|
|
|
Як Истребитель
Сообщений: 410
Оценки: 0
Присоединился: 2010-01-27 19:48:58.473333
|
На меня маааленькая есть) Если помогут довести до ума рекурсивное решение, которое я сделал на том алгоритме.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-25 19:15:13.686666
|
|
|
FriLL
Сообщений: 2539
Оценки: 335
Присоединился: 2007-08-11 17:14:26.703333
|
Я почти написал но слишком много попыток получается, не могу научить программу "догадываться"
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-25 19:32:08.133333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
много это сколько?
quote:
ORIGINAL: kreol
Вообще, насколько я понимаю, число 7 в данном случае - это математически вычесленное значение, а не эмпирический факт?
7 в даном случае экспериментально полученный результат. Не исключаю, что и 6 возможно, но я не сумел улучшить. Среднее около 5,15.
Упс! Поправка. Оказывается мой алгоритм может при неблагоприятном стечении выдать и 8 ходов. До этого прогонял - не было.
Задание то же, но решение за 8 ходов допускается. Впрочем, Даже если получите больший рез-т, то хорошо.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-26 17:20:48.390000
|
|
|
nicea
Сообщений: 25
Оценки: 0
Присоединился: 2009-05-09 19:41:22.990000
|
Родригес, ты выработал какой-то определенный алгоритм для поиска?
Мне удалось лишь составить некоторое количество правил при каких совпадениях как лучше переставлять числа для определения их значимости, но всё это приводит к огромному количеству if-ов. Пока даже не знаю как это всё правильно реализовать.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-26 17:43:27.716666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
Родригес, ты выработал какой-то определенный алгоритм для поиска?
Да.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-28 17:57:10.676666
|
|
|
doopy
Сообщений: 29
Оценки: 0
Присоединился: 2010-05-27 17:06:41.296666
|
а что, если вот такой алгоритм(код писать влом):
1. Сначало подставляем числа 1234 - запоминаем какие на месте, какие просто совпали
2. Тоже самое, что и в 1, но числа уже 5678(9 добавится по ходу решения)
3. Числа которые на месте, расставляем по своим местам.
4. Так как мы запоминали какое число где стоит(допустим было 4567, но 4 должно быть 2-ым числом, значит переставляем на 2 место)
5. Если не хватает числа, то возвращаемся к нашей 9.
В общем написано запутанно, но если разобраться, то будет понятно. А если еще поработать над 4 пунктом, то уместимся в рамки семи ходов. :)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-28 17:59:19.650000
|
|
|
Як Истребитель
Сообщений: 410
Оценки: 0
Присоединился: 2010-01-27 19:48:58.473333
|
doopy, мне понравилось, +2 :)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 03:58:53.323333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: doopy
1. Сначало подставляем числа 1234 - запоминаем какие на месте, какие просто совпали
Мы не знаем, какие на месте и какие совпали, мы знаем сколько на месте и сколько совпало.
В общем-то, остальная часть решения рушится из-за данного неверного суждения.
Тут либо куча логических правил, которая будет постепенно подбирать всё лучшее и лучшее число, либо некая магическая формула, которая будет резко уменьшать количество возможных вариантов.
В первом случае необходимо ввести некую меру "лучшести" числа. Классически, если брать какие нибудь шашки или шахматы, критерий улучшения очевиден (большее количество своих фигур и меньшее фигур противника), а исходов множество. Здесь же исход всего один, и улучшение цифр ответа (1/2 ==> 2/2) не означает приближения к результату. По крайней мере, это неочевидно :)
Во втором случае нам нужно получить функцию, которая будет принимать на вход все возможные варианты и ответ игрока, и в соответствии с этим вариантом убирать все неподходящие ответы. По идее, такая функция при рекурсивном вызове должна очень значительно редуцировать количество оставшихся вариантов, ибо я совсем не уверен, что за 7 рекурсивных вызовов можно уменьшить A = n! / (n - k!) = 9! / (9 - 4)! = 3024 вариантов до одного. В принципе, при простейшем случае мы пытаемся угадать у игрока новое число просто взяв его "от балды" из оставшихся вариантов. Можно попробовать применить таки какие-то логические правила для того, чтобы отбрасывать каждый раз ещё больше чисел.
Первый вариант решения нужно либо как-то замутно писать на прологе, при этом динамически добавляя правила, либо организовывать какие-то эффективные структуры данных. Какие именно пока что без понятия, поэтому кодировать нет смысла. А вот второй вариант решения вроде как просто реализуется, поэтому чуть позже попробую его замутить.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 06:18:28.096666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
Тут либо куча логических правил, которая будет постепенно подбирать всё лучшее и лучшее число, либо некая магическая формула, которая будет резко уменьшать количество возможных вариантов.
В первом случае необходимо ввести некую меру "лучшести" числа. Классически, если брать какие нибудь шашки или шахматы, критерий улучшения очевиден (большее количество своих фигур и меньшее фигур противника), а исходов множество. Здесь же исход всего один, и улучшение цифр ответа (1/2 ==> 2/2) не означает приближения к результату. По крайней мере, это неочевидно :)
Надо думать о мощности множества чисел, которые могли быть загаданы. Каждый ответ даёт нам информацию, которая позволяет нам уменьшить это множество. Чем сильнее уменьшение, тем полезнее ответ. Можно перебрать все варианты ходов, для каждого варианта сосчитать сумму "полезностей" всех возможных ответов. Нет, не просто сумму, надо "полезность" ответа умножать на вероятность этого ответа, и такие произведения суммировать.
Получится алгоритм-брутфорс. Но мне кажется, на современном железе, с этим алгоритмом вполне можно будет играть – не настолько уж и жёстко он будет тормозить. Теоретически, дело за малым, надо придумать как оценить "полезность" ответа. Мне кажется, это будет что-то в стиле log (A[k] - A[k+1]), где A[k] – это мощность множества возможных загаданных чисел после k-того шага. Но я не уверен, что там надо ставить минус, а не деление. Да и вообще я не уверен в этой формуле, просто это первое, что пришло в голову.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 08:27:09.760000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Можно перебрать все варианты ходов, для каждого варианта сосчитать сумму "полезностей" всех возможных ответов. Нет, не просто сумму, надо "полезность" ответа умножать на вероятность этого ответа, и такие произведения суммировать.
Понимаешь, в чём фишка, способ хороший, но его минус в том, что он вероятностый. А всегда есть вероятность, что нужный нам ответ получит по нашим расчётам наименьшую "полезность". Например, ответ 0/0 может дать нам больше информации и привести к правильному решению быстрее, чем ответ 3/3. Соответственно, нет какой-то конкретной методики определения "хорошести" текущего шага (за исключением уменьшения возможных вариантов). Мне кажется, здесь пока не дойдёшь до конца, не сможешь определить, сколько ещё идти, а учитывая, что по условию можно сделать максимум 7 ходов, вариант вероятностного решения не вызывает у меня доверия.
Соответственно, с уверенностью процентов на 90 можно сказать, что алгоритм должен давать более-менее фиксированное улучшение на каждом шаге. Единственный вариант измеререния этого улучшения, как мне кажется, это именно уменьшение наборов возможных чисел. И тут главный вопрос в том, как изменять числа таким образом, чтобы отбрасывать за раз сразу значительное количество вариантов.
Есть ещё идея, что вместо того, чтобы отбрасывать какие-то числа (то есть создавать кучу правил, ставить ограничения и т.д., а потом прогонять через него все числа) можно просто использовать пересечение множеств. А множества формировать как все возможные варианты чисел при данном ответе игрока. Например, если мы загадали число 1234, и игрок нам дал ответ 1/1, то набор возможных вариантов будет формироваться следующим образом:
1) предположим, что в исходном числе была цифра 1. Тогда набор всех возможных вариантов можно описать как 1xxx, где xxx - это все возможные размещения цифр 5-9. A(xxx) = 5! / (5 - 3)! = 60. То есть, если в исходном числе было число 1, то всего возможно 60 вариантов ответов;
2) проделаем ту же процедуру для цифр 2, 3 и 4, и для каждого из них получим свой набор из 60 чисел. Итого, 4 * 60 = 240.
Таким образом, по одному ответу мы смогли уменьшить количество вариантов от 3024 до всего лишь 240. Если повторить эту процедуру 5-6 раз, пересечение всех полученных множеств, вполне возможно, даст одно единственное значение, которое и будет ответом.
Итого, не проверенный на практике алгоритм таков:
1) выбираем наугад любое число;
2) сообщаем это число игроку и получаем от него ответ;
3) исходя из выбранного числа и этого ответа формируем набор всех возможных вариантов и находим его пересечение с набором, вычисленным на предыдущей итерации. Если пересечение содержит всего одно число, значит мы закончили работу. Иначе запоминаем его;
4) из "пересечённого" набора выбираем наугад любое число и идём на шаг номер 2.
Теоретически, должно находить ответ за 5-10 шагов. Практически, нужно проверять :)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 13:54:49.330000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
quote:
ORIGINAL: rgo
Можно перебрать все варианты ходов, для каждого варианта сосчитать сумму "полезностей" всех возможных ответов. Нет, не просто сумму, надо "полезность" ответа умножать на вероятность этого ответа, и такие произведения суммировать.
Понимаешь, в чём фишка, способ хороший, но его минус в том, что он вероятностый. А всегда есть вероятность, что нужный нам ответ получит по нашим расчётам наименьшую "полезность". Например, ответ 0/0 может дать нам больше информации и привести к правильному решению быстрее, чем ответ 3/3. Соответственно, нет какой-то конкретной методики определения "хорошести" текущего шага (за исключением уменьшения возможных вариантов). Мне кажется, здесь пока не дойдёшь до конца, не сможешь определить, сколько ещё идти, а учитывая, что по условию можно сделать максимум 7 ходов, вариант вероятностного решения не вызывает у меня доверия.
Если мы не будем учитывать вероятности, то лучше от этого не будет. Но если тебе не нравится слово вероятность, то можно перефразировать иначе. Для лучшего выбора следующего хода, то есть такого хода, который даст нам максимум информации, в общей ситуации нам надо знать какое число было загадано, так? Но эта игровая информация от нас скрыта. Что делать? Мы можем для каждого возможного числа найти лучший ход. Но для разных загаданных чисел, вообще-то, лучшие ходы будут разными. Надо искать компромисс.
Ты предлагаешь дальше алгоритм:
quote:
ORIGINAL: kreol
Итого, не проверенный на практике алгоритм таков:
1) выбираем наугад любое число;
2) сообщаем это число игроку и получаем от него ответ;
3) исходя из выбранного числа и этого ответа формируем набор всех возможных вариантов и находим его пересечение с набором, вычисленным на предыдущей итерации. Если пересечение содержит всего одно число, значит мы закончили работу. Иначе запоминаем его;
4) из "пересечённого" набора выбираем наугад любое число и идём на шаг номер 2.
Это пораженческий алгоритм. Компромисс ты ищешь выбирая _случайное_ число. Но это же не компромисс, а непонятно что. Лучше уж вероятности посчитать. Они конечно не избавят от тотального невезения, когда несмотря ни на что, мы будем делать худшие ходы. Но зато, нам чаще будет везти. И кроме того, если всё-таки существует самый лучший ход, который даст максимум информации вне зависимости от того, какое число загадано, то мой вероятностный подход не упустит возможности сделать лучший ход из доступных =)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 14:09:15.480000
|
|
|
doopy
Сообщений: 29
Оценки: 0
Присоединился: 2010-05-27 17:06:41.296666
|
quote:
Мы не знаем, какие на месте и какие совпали, мы знаем сколько на месте и сколько совпало.
В общем-то, остальная часть решения рушится из-за данного неверного суждения.
Тут либо куча логических правил, которая будет постепенно подбирать всё лучшее и лучшее число, либо некая магическая формула, которая будет резко уменьшать количество возможных вариантов.
В первом случае необходимо ввести некую меру "лучшести" числа. Классически, если брать какие нибудь шашки или шахматы, критерий улучшения очевиден (большее количество своих фигур и меньшее фигур противника), а исходов множество. Здесь же исход всего один, и улучшение цифр ответа (1/2 ==> 2/2) не означает приближения к результату. По крайней мере, это неочевидно :)
Во втором случае нам нужно получить функцию, которая будет принимать на вход все возможные варианты и ответ игрока, и в соответствии с этим вариантом убирать все неподходящие ответы. По идее, такая функция при рекурсивном вызове должна очень значительно редуцировать количество оставшихся вариантов, ибо я совсем не уверен, что за 7 рекурсивных вызовов можно уменьшить A = n! / (n - k!) = 9! / (9 - 4)! = 3024 вариантов до одного. В принципе, при простейшем случае мы пытаемся угадать у игрока новое число просто взяв его "от балды" из оставшихся вариантов. Можно попробовать применить таки какие-то логические правила для того, чтобы отбрасывать каждый раз ещё больше чисел.
Первый вариант решения нужно либо как-то замутно писать на прологе, при этом динамически добавляя правила, либо организовывать какие-то эффективные структуры данных. Какие именно пока что без понятия, поэтому кодировать нет смысла. А вот второй вариант решения вроде как просто реализуется, поэтому чуть позже попробую его замутить.
Вся соль в алгоритме, главное его проработать и все будет бегать.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 14:32:52.883333
|
|
|
doopy
Сообщений: 29
Оценки: 0
Присоединился: 2010-05-27 17:06:41.296666
|
У меня получилось так(по моему алгоритму):
Я загадал число 1459
1. 1234 2/1 - 1 часть алгоритма
2. 5678 1/1 - 2 часть алгоритма
3. 2367 0/0 - эти числа отсеиваем т.к. оказалось, среди них нет нужного
4. 1458 3/3 - эти числа прога посчитала нужными(так и есть)
5. у нас одно из этих чисел не проверенное, но мы точно знаем, чтто 1 и 4 точно на месте, значит проверяем 5 и 8 оставшейся цифрой 9: 1498 2/2 - узнаем, что 5 была нужна
6. 1459 4/4 - получилось то что надо.
В теории все работает, осталось проверить на практике.:D
P.S число простое да, щас скажете, что с таким числом легко получается, но если взять посложнее, то число ходов станет больше максимум на 2-3 и того будет равно 8-9. Так что если создавать компьютерного соперника, то этот алгоритм подойдет.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 14:59:33.473333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
ORIGINAL: doopy
В теории все работает, осталось проверить на практике.:D
Ждем с нетерпением)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 15:40:29.490000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
4) из "пересечённого" набора выбираем наугад любое число и идём на шаг номер 2.
Кстати, нашёл пример, показывающий, что не стоит ограничиваться "пересечённым" набором при выборе любого числа:at start: 90 variants. trying to guess 97
guess 34, answer 0/0. Remains 56 variants
guess 89, answer 1/0. Remains 12 variants
guess 8, answer 0/0. Remains 5 variants
guess 12, answer 0/0. Remains 3 variants
guess 56, answer 0/0. Remains 1 variants Это правда для двух-цифирного варианта игры. Загаданное число 97. Видно, что после третьего хода становится известным, что в первой позиции числа должна стоять девятка. Но следующими ходами проверяются числа 12 и 56, и это правильно: ведь цель не угадать всё число целиком, а выяснить оставшуюся цифру.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 16:05:17.106666
|
|
|
doopy
Сообщений: 29
Оценки: 0
Присоединился: 2010-05-27 17:06:41.296666
|
quote:
ORIGINAL: Родригес
quote:
ORIGINAL: doopy
В теории все работает, осталось проверить на практике.:D
Ждем с нетерпением)
Лень писать:D
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 21:46:35.793333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: doopy
3. 2367 0/0 - эти числа отсеиваем т.к. оказалось, среди них нет нужного
Ну и откуда ты взял эти числа? Почему ты не взял 2345 или 1256, или 3458? Ни одно из этих чисел не дало бы тебе результата 0/0 и ты бы не смогу их всех выбросить. Ты поробуй по своему алгоритму поиграть с программой, которую Родригес кидал.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-29 21:58:18.113333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Кстати, нашёл пример, показывающий, что не стоит ограничиваться "пересечённым" набором при выборе любого числа…
Просто если брать число не из пересечённого набора, то мы рискуем получить новый набор, который вообще никак не будет пересекаться с последним вычисленным, и тогда мы потратим ход впустую. Мне всё-таки кажется, что каждый ход даёт более или менее фиксированное улучшение положения, потому как "типично 5-6 [ходов]" - это всё-таки довольно определённые границы, в то время как вероятностные методы чаще дают больший разброс (к примеру, от 3 до 7 ходов).
В любом случае, надо проверять. Сейчас я остановился на функции, которая вычисляет набор всех возможных чисел при данных ограничениях (при данном ответе пользователя). Будет она - можно будет проверить.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-30 07:05:32.140000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
quote:
ORIGINAL: rgo
Кстати, нашёл пример, показывающий, что не стоит ограничиваться "пересечённым" набором при выборе любого числа…
Просто если брать число не из пересечённого набора, то мы рискуем получить новый набор, который вообще никак не будет пересекаться с последним вычисленным, и тогда мы потратим ход впустую.
Это если ход выбирать "случайно". Тогда можно и впустую потратить этот ход. А если оценивать количество информации, которое ход даст… ;)
quote:
ORIGINAL: kreol
Мне всё-таки кажется, что каждый ход даёт более или менее фиксированное улучшение положения, потому как "типично 5-6 [ходов]" - это всё-таки довольно определённые границы, в то время как вероятностные методы чаще дают больший разброс (к примеру, от 3 до 7 ходов).
Не совсем так. Если бы игра состояла из одного хода, то быть может вероятностный подход был бы ничем не лучше какого-нибудь другого, а может даже и хуже. Но в данной ситуации, когда для правильного выбора хода надо гадать о том, что может прятать оппонент, и когда мы должны сделать несколько ходов, ситуация будет быстро стабилизироваться с каждым ходом.
Короче, я не поленился, я реализовал этот свой алгоритм, навеянный теорией игр. Реализация медленна, потому что выбор правильного хода это три вложенных цикла:(defun best-guess (guess-set secret-set card)
(loop
; ....
for g in guess-set
for goodness = (loop
with count and proper and new-card
for s in secret-set
; ...
... (count-if (filter count proper g) secret-set) Два цикла явно присутствуют, третий неявно, прячется в count-if. Но насколько бы эта реализация не полагалась бы на грубую силу, она позволяет проверить алгоритм на всех возможных загаданных числах в двухцифирном варианте игры. И реализация укладывается 5 ходов. В среднем даёт 4.1 ход на отгадывание.
Я тут обратил внимание на то, что цифра 0 не участвует, это конечно же резко ускоряет перебор, и я смог погонять с оригинальной формулировкой игры.
CL-USER> (let-us-game (make-number 1459))
at start: 3024 variants. trying to guess 1459
guess 1234, answer 2/1. Remains 480 variants
guess 1739, answer 2/2. Remains 36 variants
guess 1948, answer 3/1. Remains 3 variants
guess 1253, answer 2/2. Remains 1 variants
#(1 4 5 9)
4
CL-USER> (let-us-game (make-number 1469))
at start: 3024 variants. trying to guess 1469
guess 1234, answer 2/1. Remains 480 variants
guess 1739, answer 2/2. Remains 36 variants
guess 1948, answer 3/1. Remains 3 variants
guess 1253, answer 1/1. Remains 1 variants
#(1 4 6 9)
4
CL-USER> (let-us-game (make-number 9164))
at start: 3024 variants. trying to guess 9164
guess 1234, answer 2/1. Remains 480 variants
guess 1739, answer 2/0. Remains 88 variants
guess 9384, answer 2/2. Remains 10 variants
guess 5194, answer 3/2. Remains 1 variants
#(9 1 6 4)
4
CL-USER> (let-us-game (make-number 1236))
at start: 3024 variants. trying to guess 1236
guess 1234, answer 3/3. Remains 20 variants
guess 4275, answer 1/1. Remains 3 variants
guess 1268, answer 3/2. Remains 1 variants
#(1 2 3 6)
3
CL-USER> (let-us-game (make-number 1263))
at start: 3024 variants. trying to guess 1263
guess 1234, answer 3/2. Remains 60 variants
guess 3594, answer 1/0. Remains 12 variants
guess 1842, answer 2/1. Remains 2 variants
guess 1236, answer 4/2. Remains 1 variants
#(1 2 6 3)
4
CL-USER> (let-us-game (make-number 1623))
at start: 3024 variants. trying to guess 1623
guess 1234, answer 3/1. Remains 180 variants
guess 2635, answer 3/1. Remains 12 variants
guess 1532, answer 3/1. Remains 1 variants
#(1 6 2 3)
3
CL-USER> (let-us-game (make-number 6123))
at start: 3024 variants. trying to guess 6123
guess 1234, answer 3/0. Remains 220 variants
guess 2948, answer 1/0. Remains 42 variants
guess 3512, answer 3/0. Remains 6 variants
guess 1263, answer 4/1. Remains 1 variants
#(6 1 2 3)
4
CL-USER> (let-us-game (make-number 6231))
at start: 3024 variants. trying to guess 6231
guess 1234, answer 3/2. Remains 60 variants
guess 3594, answer 1/0. Remains 12 variants
guess 1842, answer 2/0. Remains 2 variants
guess 1236, answer 4/2. Remains 1 variants
#(6 2 3 1)
4
CL-USER> (let-us-game (make-number 6213))
at start: 3024 variants. trying to guess 6213
guess 1234, answer 3/1. Remains 180 variants
guess 2635, answer 3/0. Remains 17 variants
guess 5243, answer 2/2. Remains 1 variants
#(6 2 1 3)
3
CL-USER> (let-us-game (make-number 9587))
at start: 3024 variants. trying to guess 9587
guess 1234, answer 0/0. Remains 120 variants
guess 7618, answer 2/0. Remains 42 variants
guess 5789, answer 4/1. Remains 4 variants
guess 1287, answer 2/2. Remains 1 variants
#(9 5 8 7)
4
CL-USER> (let-us-game (make-number 9517))
at start: 3024 variants. trying to guess 9517
guess 1234, answer 1/0. Remains 720 variants
guess 6572, answer 2/1. Remains 128 variants
guess 8176, answer 2/0. Remains 30 variants
guess 6845, answer 1/0. Remains 5 variants
guess 3719, answer 3/1. Remains 1 variants
#(9 5 1 7)
5
CL-USER> (let-us-game (make-number 6517))
at start: 3024 variants. trying to guess 6517
guess 1234, answer 1/0. Remains 720 variants
guess 6572, answer 3/2. Remains 23 variants
guess 2519, answer 2/2. Remains 2 variants
guess 1236, answer 2/0. Remains 1 variants
#(6 5 1 7)
4
CL-USER> (let-us-game (make-number 8517))
at start: 3024 variants. trying to guess 8517
guess 1234, answer 1/0. Remains 720 variants
guess 6572, answer 2/1. Remains 128 variants
guess 8176, answer 3/1. Remains 9 variants
guess 5638, answer 2/0. Remains 1 variants
#(8 5 1 7)
4 К сожалению проверить алгоритм на всех числах, которые могли бы быть загаданы, не представляется возможным, если только я не придумаю как можно эффективнее представлять множества secret-set и guess-set, чтобы перебирать не все их элементы, а их подмножества, элементы которых дадут одинаковые по информативности ответы. Но как видите, я проверил на ряде чисел. Алгоритм стабильно укладывается в пять ходов, как правило ему хватает четырёх.
Местами там складывается ощущение, что алгоритм читерит, поскольку он подчастую выбирает один из равноценных с его точки зрения ходов очень непредсказуемо. Я это объяснить могу лишь использованием floating-point, при использовании которого не работает коммутативность, то есть a+b != b+a. Не знаю так ли это, но другого объяснения у меня нет. И как бы там не было, я постарался перебрать разные, но похожие числа, чтобы было ясно, что это не читерство.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-05-30 23:54:03.103333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Это если ход выбирать "случайно". Тогда можно и впустую потратить этот ход. А если оценивать количество информации, которое ход даст… ;)
Не, ну так я сразу и сказал, что "случайно" - это в простейшем случае. Никто не запрещает вводить какие-то дополнительные оптимизации. Но чем мне не нравится вероятность, так это недетерминированностью: с ней очень сложно расчитать максимальное необходимое количество шагов. Разве что полным перебором, но ты сам сказал, что это не представляется возможным, да и чуть чуть изменишь условие, и по новой перебирать?
Есть у меня идея, как лучше оценивать количество информации, которую даст ход. Насколько я понимаю, ты для расчёта "полезности" хода используешь величину, обратную количеству чисел, которые могут остаться, если сделать данных ход. Ну, и умножаешь его на вероятность попадания этого числа, так? Я же хочу выбросить из расчётов вероятность, а полезность оценивать по количеству групп, на которые разобьётся всё множество возможных чисел (одна группа - это все числа, которые дадут одинаковый ответ). Чем больше групп - тем лучше число. Правда, в таком случае придётся всё равно расчитывать вероятность выпадения данного числа (любого из чисел, которые дадут такое разбиение на группы), но что-то мне кажется, что там вероятность уже не будет столь недетерминированной.
Это навскидку. Если успею, сегодня всё додумаю и проверю на практике.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-02 23:41:42.820000
|
|
|
FriLL
Сообщений: 2539
Оценки: 335
Присоединился: 2007-08-11 17:14:26.703333
|
Один мой знакомы написал программу, которая так же считает количество попыток для всех вариантов
Регистрироваться на форуме он отказался по неизвестным причинам
Вообщем код:
//---------------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------------
/////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <list>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////
using namespace std;
/////////////////////////////////////////////////////////////////////////////
struct condition
{
vector<int> number;
int count,position;
};
/////////////////////////////////////////////////////////////////////////////
list<condition> cond,empty;
/////////////////////////////////////////////////////////////////////////////
vector<int> int2vec(int num)
{
vector<int> ret;
for(int i=3;i>=0;i--){ret.push_back(num%10);num/=10;}
return ret;
}
/////////////////////////////////////////////////////////////////////////////
bool check(int num,list<condition> cond)
{
vector<int> n=int2vec(num);
for(int i=0;i!=4;i++)if(!n[i])return false;
for(int i=0;i!=3;i++)
for(int j=i+1;j!=4;j++)
if(n[i]==n[j])return false;
for(list<condition>::iterator it=cond.begin();it!=cond.end();it++)
{
int count,position;
count=position=0;
for(int i=0;i!=4;i++)
for(int j=0;j!=4;j++)
if(n[i]==it->number[j]){count++;if(i==j)position++;break;}
if(count!=it->count||position!=it->position)return false;
}
return true;
}
/////////////////////////////////////////////////////////////////////////////
#pragma argsused
int main(int argc, char* argv[])
{
string mode,ans;
condition input;
cout<<"choose mode [game/info] (g/i): ";
cin>>mode;
if(mode=="G")mode="g";
if(mode=="I")mode="i";
while(mode!="g"&&mode!="i")
{
cout<<endl<<"g or i: ";
cin>>mode;
}
cout<<endl;
cond.clear();
if(mode=="g")
{
cout<<endl<<"game mode. please give answers in a/b format"<<endl<<endl;
for(int i=0;i!=10000;++i)
if(check(i,cond))
{
int outs=0;
for(int j=i;j!=10000;++j)if(check(j,cond))outs++;
cout<<i<<"\t"<<outs<<" outs left"<<endl;
cin>>ans;
input.number=int2vec(i);
input.count=ans[0]-0x30;
input.position=ans[2]-0x30;
if(input.position==4)break;
cond.push_back(input);
}
}
else
{
int rec,rec_checks,checks,checks_sum,numbers_count;
rec=rec_checks=checks_sum=numbers_count=0;
cout<<endl<<"info mode. generating..."<<endl;
for(int k=0;k!=10000;++k)
if(check(k,empty))
{
cond.clear();
numbers_count++;
checks=0;
for(int i=0;i!=10000;++i)
if(check(i,cond))
{
vector<int> a,b;
a=int2vec(i);
b=int2vec(k);
input.number=a;
input.count=input.position=0;
for(int m=0;m!=4;m++)
for(int n=0;n!=4;n++)
if(a[m]==b[n]){input.count++;if(m==n)input.position++;break;}
cond.push_back(input);
checks++;
if(input.position==4)break;
}
checks_sum+=checks;
if(checks>rec_checks){rec_checks=checks;rec=k;}
}
cout<<endl<<"checked\t\t\t"<<numbers_count<<endl<<
"average checks count\t"<<double(checks_sum)/numbers_count<<endl<<
"longest checks count\t"<<rec_checks<<endl<<
"longest try on\t\t"<<rec<<endl;
}
system("pause");
return 0;
}
//---------------------------------------------------------------------------
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-03 18:35:33.743333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
ORIGINAL: FriLL
Один мой знакомы написал программу, которая так же считает количество попыток для всех вариантов
Регистрироваться на форуме он отказался по неизвестным причинам
Прекрасно. Максимум 8 и среднее 5.2 . Результат для вероятностного алгоритма, описанного Креолом в 23 посту. Знакому плюс.
Я решал задачу тем же способом. Но есть еще над чем поработать, снизить максимум до семи.
У rgo как я понял какое то иное решение, которое он пока придержал.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-08 17:33:15.146666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Таки придумал я, как избавиться и от случайности, и от вероятности.
Для каждого числа мы можем составить таблицу вида:
0/0 M(x, 0/0)
0/1 M(x, 0/1)
0/2 M(x, 0/2)
...
4/4 1 где x - текущее число,
M(x, A) - мощность множества чисел, которые дадут ответ A, если мы спросим у пользователя число x.
Для каждого проверяемого числа x совокупность возможных мощностей будет иметь различное распределение. Например, график для некоторого x1 может иметь вид:
а для x2:
Видно, что на втором графике распределение значительно более равномерное, чем на первом. Если мы будем выбирать числа, которые разобьют исходное множество на максимально равномерные подмножества (в данном случае - x2), то гарантированно на каждом шагу будем получать некоторое значительное уменьшение множества. В случае же выбора числа, которое даёт сильную дисперсию мощностей получившихся подмножеств (здесь - x1), мы имеем шанс для какого-то загаданного числа всё время попадать в максимальное подмножество, и в итоге выйти за предел разрешённых 8 попыток. В этом была суть моей претензии к варианту с расчётом вероятностей, который предложил rgo.
Теперь осталось только всё это закодить и прогнать на всех 3024 возможных числах. Есть тут обладатели мощных комптьютеров, которым к тому же нечего делать? :)
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-08 19:16:36.393333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
Теперь осталось только всё это закодить и прогнать на всех 3024 возможных числах. Есть тут обладатели мощных комптьютеров, которым к тому же нечего делать? :)
Меня вот этот вопрос сейчас больше интересует. Ведь и я, и ты, мы просчитываем ситуацию на один ход вперёд. Почему бы не просчитать её на два, три хода вперёд? Или уж сразу до конца? Мешает лишь тормознутость алгоритма.
Так вот, надо научиться быстро искать M(x, A), эти самые мощности. Я сейчас ищу перебором, это долго. На одну игру может уйти минут пять-десять. Была мысль, как это можно ускорить, раз в 100 (в идеальной ситуации в 100), но я пока её забросил. Ввиду другой мысли.
Первый ход. Мы можем походить одним из 10k способов. Ну, точнее способов поменьше, но всё равно несколько тысяч, не важно сколько точно, много. Но ведь понятно из самых общих соображений, что все варианты первого хода равноценны, потому что про каждую цифру мы имеем одну и ту же информацию.
Пускай первым ходом, мы проверили число 1234.
Второй ход. У нас уже есть несколько классов цифр, например это может быть: a={5, 6, 7, 8, 9}, b={1}, c={2}, d={3}, e={4}. Рассмотрим два возможных хода x1 и x2. Заменим каждую цифру в xi на букву класса, в котором эта цифра содержится. Пускай мы получим строку F(xi). Так вот, если F(x1) == F(x2), то это означает, что нам без разницы какой из ходов делать: x1 или x2. Эти ходы будут равнозначны с точки зрения наших знаний на текущем этапе. Очень хочется, при этом, объединить {b, c, d, e}, но это не получится следать в общей ситуации, ответ, например, 0/4 скажет нам о том, что 1 присутствует но не на первом месте, 2 присутствует но не на втором месте, и тд. То есть информация об этих цифрах будет различаться.
После последнего хода, мы получим опять же пять классов: четыре одноцифирных класса, с правильными цифрами, и один класс, со всеми остальными цифрами, которые в ответе отсутствуют.
Мне просто пока никак не добраться, не подумать как учесть информацию полученную ходом, как она повлияет на наши классы. Но если такой подход довести до рабочего состояния, то он позволит радикально уменьшить перебор. Не думаю, что имеет смысл особо заботиться объединением классов, если вдруг информация про две разные цифры сравнивается. Не знаю возможно ли такое кроме случая, когда мы выясняем что цифры нет в ответе. Но вариант, когда цифру можно отбросить можно рассмотреть отдельно, остальное же повлияет не сильно. Главное первые три хода сделать (первый можно рандомом), остальные можно даже полным перебором.
Но такой подход – это первая половина задумки. =)
Дальше можно использовать что-нибудь типа memoization, и тогда уж можно будет подумать о полном переборе всего дерева игры. С текущего хода до последнего.
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-08 23:10:27.736666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Родригес
Это реальные графики или от балды? Меня несколько смущает наличие в них предпоследнего столбика , подписанного как 3/4.
Это от балды, для показа идеи. Реальные данные ещё нужно считать )
|
|
|
|
|
RE: Задача от Родригеса. Логическая игра в числа. - 2010-06-09 00:46:13.076666
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
ГЫ : http://www.cyberforum.ru/pascal/thread140249.html Обратная задача.
|
|
|
|
|
|
