Собственно игра находится вот здесь : http://www.games.look.ru/bc/
Предлагаю подумать над поиском оптимальной стратегии для игры, а также определить наихудший случай и определить максимальное число ходов для решения этой задачи.
Собственно игра находится вот здесь : http://www.games.look.ru/bc/
Предлагаю подумать над поиском оптимальной стратегии для игры, а также определить наихудший случай и определить максимальное число ходов для решения этой задачи.
Ленивый дурак - это полбеды; деятельный дурак - это для всех головная боль, но нет ничего хуже, чем дурак с инициативой, да ещё и при должности.
У нас есть 13 реакций на введенную комбинацию:
0 - 0
1 - 0, 1 - 1
2 - 0, 2 - 1, 2 - 2
3 - 0, 3 - 1, 3 - 2, 3 - 3,
4 - 0, 4 - 1, 4 - 2,
Цель - дойти до 4 - 4 - т.е. выигрыша.
Всего возможных комбинаций в игре 10*9*8*7, правильных только одна.
Пробую решить задачу переборным путем. Для этого надо составить программу, работающую по следующему алгоритму:
для всех возможных комбинаций (от 1234 до 7890) далаем попытку угадать (начиная с 1234) - получаем ответ - одну из 13-ти ситуаций, указанных выше. Если ответ 4-4 - мы нашли загаданное число. Если нет - выбираем следующее число, и в распоряжении уже 2 реакции компьютера. Существует какая-то минимальная цепочка, по котором можно однозначно определить, какая комбинация будет правильной. Необходимо ее найти.
Есть интересная характеристика - количество информации, или энтропия. Например, если мы получили f(1234)=00, то ход N2 - 4321 нам новой информации не даст. Математически это можно вычислить через условную энтропию, а можно пойти другим путем: Пусть у нас известны отклики на k различных комбинаций - тогда Мы можем заведомо вычитать отклики для некоторых других комбинаций (например f(1234)=00 будет давать f(1243)=00, f(2431)=00 и т.д.) - тем самым снижая число вариантов следующего хода.
Ленивый дурак - это полбеды; деятельный дурак - это для всех головная боль, но нет ничего хуже, чем дурак с инициативой, да ещё и при должности.
отгадала число за 7 ходов.
Алгоритма решения сказать не могу, т.к. я все-таки не математик. При решении просто анализирую результаты, сравниваю их, исключаю какие-то цифры, замечаю угаданные и цифры и места (угаданных быков) и таким образом пытаюсь вычислить правильный ответ.
Самое главное - то, чего не увидишь глазами... (с) "Маленький принц"
честно сказать, меня эта хадача задела за живое) до сих пор покоя не даёт =)
недавно натолкнулась на алгоритм реализации её решения на с++
Интересная игра . Пока лучший результат - 7 ходов.
Вот тут: http://igrun.com/?7210 можно в эту игру на деньги играть
Там она называется "Сейф", нужно угадать за 5 ходов - выиграл (чем раньше угадал - тем больше выиграл).
Моя программа угадывает всреднем за 5.4 ходов, этого мало, чтоб деньги зарабатывать
Завтра буду думать над улучшением алгоритма
Что скажете об этом?
bulca.h18.ru
Тут можно заставить комп играть самого против себя!
Открыл технологию угадывания 4-значного числа! Абсолютная безотказность. Количество необходимых попыток - 5-6, ну в случае фатального невезения может потребоваться 7.
Такая технология, правда, требует от Вас хорошей сообразительности и достаточно большого промежутка времени для отгадывания чисел (у меня уходило от 70 до 160 секунд). Если для Вас это - пустяки, можете смело прибегать к этой технологии)
Принцип такой.
Первые 4 попытки пишем следующие числа:
1234
4567
3480
6043
И смотрим на результаты.
В частности нас интересует СУММА всех быков и коров за эти 4 попытки.
Вы спросите в чем дело, почему именно эти числа? Можно и другие, на самом деле, но обязательно условие такое:
ОДНА цифра должна повторяться ЧЕТЫРЕ раза (в данном случае это 4) и желательно стоять во всех числах на разных позициях;
ОДНА цифра - ТРИ раза (в данном случае это 3);
ДВЕ цифры - по ДВА раза (6 и 0);
и ОДНА цифра - отсутствовать вовсе (9).
При этом пять цифр будут повторяться по одному разу - это 1, 2, 5, 7 и 8.
Еще одна особенность: в числе 6043, которое мы ввели 4-ой попыткой, присутствуют все цифры, которые повторяются в данной комбинации более чем один раз (это 4, 3, 6 и 0) - и ТОЛЬКО они. Это сыграет также важную роль. Зачем это надо - потом скажу.
Итак, теперь считаем сумму полученных быков и коров. Их может быть от 3 до 11. Это нам надо для того, чтобы определить, какие из повторяющихся цифр встречаются в загаданном числе.
Например, если в итоге получилось 3 быка и коровы - ясное дело, что загаданное число содержит три цифры, которые повторяются в комбинации один раз, и цифру, которая отсутствует. Другого варианта быть не может.
Для тех, кто хочет сэкономить время, приводу шпаргалку:
Сумма БК/Повторения
3 = 1110
4 = 2110 или 1111.
5 = 3110/2210/2111
6 = 4110/3210/3111/2211
7 = 4210/4111/3220/3211
8 = 4310/4220/4211/3221
9 = 4320/4311/4221
10 = 4321
11 = 4322
Если сумма равна от 4 до 9, то вариантов, как вы видите, несколько.
В этом случае на помощь приходит число 6043 (то самое, где встречаются только повторяющиеся цифры). Смотрим сумму быков и коров именно у него.
Например, если общая сумма равна 7, а у четвертой попытки только один бык, то ясное дело - иначе как 4111 вариантов быть не может.
Вот например:
1234 - 1б, 1к
4567 - 1б, 1к
3480 - 0б, 2к
6043 - 1б, 0к.
Подставляем и получаем следующее:
Цифра 4 - ТОЧНО есть, причем стоит она на 3-ей позиции.
Цифр 3, 6, 9, 0 - ТОЧНО нет.
Подставляем результаты в третью попытку: Цифра 8 - точно есть.
И еще есть одна из цифр 12, и одна из цифр 57. Обе - стоят на своих позициях (так как в обоих случаях 4 - это корова).
Возможные варианты: 1847, 1548, 8247.
Более точно мы определить число пока не можем, но заметьте - уже свели количество возможных вариантов к трем (при том что всего их ни много ни мало 4536, при условии что число не начинается с нуля). Вероятность того, что мы угадаем с 5-ой попытки, равна 33%. Вопрос - что вводить 5-ой попыткой?
Посмотрим варианты.
Если мы введем 1847, то:
Если загадано число 1548, результат будет - 2 быка 1 корова.
Если загадано число 8247, результат будет - 2 быка 1 корова.
Вывод: число 1847 вводить не стоит, если только Ваши экстрасенсорные способности не подсказывают Вам, что загадано именно оно.
Если мы введем 1548, то:
Если загадано 1847, результат будет - 2 быка 1 корова.
Если загадано 8247, результат будет - 1 бык 1 корова.
Уже лучше! Делаем пятую попытку. С вероятностью 33% - она оказывается удачной, если же нет - то шестая попытка уже точно будет последней. =)))
Если жа и после такой проверки вариантов все равно осталось несколько (например, общая сумма = 8, сумма у 4-го числа = 2, варианты - 4310 и 4211) тогда уже анализируйте дальше, исходя из кол-ва быков и коров на каждой попытке.
Еще один пример:
1234 - 1б, 1к
4567 - 0б, 2к
3480 - 2б, 0к
6043 - 0б, 2к
Сумма = 8. 8 = 4310/4220/4211/3221.
После проверки 4-ой попыткой возможные варианты: 4211, 4310.
Проверим сначала 4310. Может быть такое? Может. Это означает, что цифры 3 и 4 - есть, 6 и 0 - нет, 9 - есть. Все подходит.
Теперь определим местоположение. Третья попытка - два быка, и кроме как 3 и 4 вариантов быть не может. СТО-о-оп! А где же тогда бык в первой попытке? Согласно ей, цифр 1 и 2 быть не может, а 3 и 4 уже заняты... Не получается!
ЗНАЧИТ - 3 все-таки нет, а единственный вариант оставшийся - 4211.
То есть: 4 есть, также есть 6 или 0, 9 нет. 3 - тоже нет.
Если предположить, что есть 4 и 6, тогда есть еще 8, а также 1 или 2.
Если же предположить, что есть 4 и 0, то есть еще 5/7 или 1/2.
Еще один момент: В первой попытке остался неиспользованным один бык. Причем это точно цифра 1, так как на второй позиции стоит цифра 4 (согласно 3-ей попытке), а цифры 3 вообще нет.
Итак, первые две цифры числа 14.
Варианты: 1450, 1470, 1486.
И опять с вероятностью 33% мы угадываем с пятой попытки, с вероятностью 67% - с шестой.
Конечно, значительную роль в игре играют быки. В третьей попытке получилось два быка - и в итоге мы сэкономили один ход. Но на самом деле бывает так, что мне удалось выиграть с пятой попытки (и даже без угадывания в конце!!!) имея лишь одного быка.
Например:
1234 - 0б, 2к
4567 - 1б, 0к
3480 - 0б, 3к
6043 - 0б, 3к.
Сумма = 9. 9 = 4320/4311/4221.
6043 = 3 коровы
Остаются варианты 4320 и 4221.
Пробуем оба этих варианта. Согласно первому:
Есть цифры 4, 3 и 9, также есть 6 или 0.
Или:
Есть 4, 6 и 0, а также еще одна цифра из неповторяющихся - 1, 2, 5, 7 или 8.
Какая? Смотрим по быкам. И натыкаемся на несоответствие - во второй попытке 4567 имеем только одного быка, а согласно этому варианту есть 4 и 6. Не подходит.
Следовательно, подходит только первый вариант, причем как мы только что выяснили, цифры 6 нет, значит есть 3, 4, 9 и 0.
Теперь вычислим местоположение этих цифр. 4 - единственный бык во второй попытке, значит, она на первой позиции.
Цифра 3 может находиться только на 2-ой позиции, так как она была использована в первой и в четвертой попытке на 3-ей и 4-ой позиции, и нигде нет ни одного быка. Значит, у нас два варианта: 4390 и 4309. 4390 - быть не может, так как в третьей попытке у нас тоже нет быков. Остается единственный ваариант - 4309, который мы и вводим 5-ой попыткой и выигрываем!
Но могут изредка возникать ситуации, когда четырех попыток маловато, чтобы свести дальнейший процесс к тупо угадыванию.
1234 - 0б, 1к
4567 - 1б, 0к
3480 - 0б, 1к
6043 - 0б, 1к.
Итого - 4 в сумме. 4 = 2110 или 1111.
На 4-ой попытке - одна корова. Это означает, что вариант 1111 нам не подходит - только 2110.
Из этого делаем вывод следующий:
9 - есть
Есть также 6 или 0
Есть также 1 или 2 (исходя из первого числа)
И еще одна цифра. Это может быть 5 или 7, но если есть одна из этих цифр, значит 6 нет, а есть 0. Или же если есть 6, то есть 8 обязательно.
Проще говоря, варианты цифр: 1/2 - 6 - 8 - 9, или 1/2 - 5/7 - 9 - 0.
О местоположении цифр догадываться мы пока не можем - маловато быков.
Возможных вариантов пока много. Делаем пятую попытку. Лучше первым проверять тот вариант, где меньше точно известных цифр. Пусть это будет число 2907.
Получилось: 1 бык, 1 корова.
Что это означает?
1: Цифры 9 и 0 - верны, а 2 и 7 надо заменить на 1 и 5.
2: Вариант неверен, и совпали цифры 2 и 9, а оставшиеся две - 6 и 8.
То есть набор цифр получается следующий: либо 1-5-9-0, либо 2-6-8-9.
Рассмотрим сначала первый вариант. Мы имеем следующее:
5 может быть только на второй позиции;
0 - не на четвертой, значит на третьей позиции (в начале числа он не может стоять). Это и есть бык;
1 - не на первой позиции.
Единственный вариант - 9501. Пока не спешим его вводить...
Теперь второй вариант - с набором 2-6-8-9:
6 - на третьей позиции;
2 - не на второй позиции.
Варианты: 2869, 2968, 8962, 9862
Варианты 2968 и 9862 - не подходят, так как в первом случае получается 2 быка, а во втором - ни одного.
Остается три варианта: 9501, 2869, 8962. Тут уже - только вопрос везения. Мне не повезло, я ввел 8962 и получил 1 корову и только) оказалось как раз 9501((( получилось 7 попыток.
Конечно, выглядит сложно на первый раз. Но нужно просто попрактиковаться, и все будет хорошо). А главное - это РАБОТАЕТ! Реально, я только что 40 раз сыграл с компьютером, в 52,5% случаев (21 из 40) угадал с 5 попыток, в 42,5% (17 из 40) - с 6-ти, и лишь дважды (5%) мне не повезло и пришлось использовать седьмую.
Хотя бывают, конечно, и исключительные случаи. С вероятностью 1 к 1134 компьютер может загадать одно из чисел 1234, 4567, 3480, 6043. Однажды он загадал число 4576, которое я благополучно угадал с трех попыток) А может оказаться так, что после ввода, к примеру, 3480 Вы получите 0 быков 0 коров, что делает почти бессмысленным ввод числа 6043. Но факт есть факт - при использовании этой стратегии вероятность отгадывания с 4 попыток равна 0.09%
не более чем с 5 попыток = около 50%
не более чем с 6 попыток = около 90%
не более чем с 7 попыток = 100%!
Может быть конечно я и ошибаюсь, но на мой взгляд - это самая оптимальная стратегия отгадывания четырехзначного числа. В настоящее время я еще думаю над стратегией отгадывания 5-значных, 6-значных и даже 9-значных чисел. Как додумаюсь - поделюсь, если конечно это будет интересно.
В завершении даю ссылку на мою версию программы, которую я написал за 1,5 часа на Delphi 7. Ее особенность - возможность отгадывать числа как четырехзначые, так и других разрядностей, а также возможность проходить Чемпионаты, т.е. последовательность раундов с отгадыванием чисел разных разрядностей с ограничением по кол-ву попыток и времени (мой рекорд по прохождению чемпионата на 8 раундов - 58 попыток и 590 секунд, уровень Экстрасенс).
Вот она - http://depositfiles.com/files/ma1i1gsiw
УДАЧИ!!!
Последний раз редактировалось Bars; 10.10.2012 в 20:14.
Ссылка уже мертвая. Может кто успел скачать ? Или автор еще тут - очень нужен код.
Киньте живой ссылочкой или на почту shroomz@mail.ru.
Заранее спасибо.
Idea and creation: fuldon (aka miXei) © 2000-2015
Powered by vBulletin® Version 4.2.6 by vBS Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. |