Масштабная "Быки и коровы"(MasterMind) 100х20
"Слегка" расширенный вариант игры "Быки и коровы":
(l) колво позиций <=100
(k) глубина позиции <=20
повторения возможны
Вопрос как реализовать сие?
Любые идеи (даже самые бредовые, у меня и таких уже нет), ссылки, все что можно...
Пока рабочая версия просто прощупывает последовательность, идя слева и проверяя изменение кол-ва быков. На длинных последовательностях также задается k вопросов и создается массив колва символа в последовательности.
Первоначально была идея отсеивать из области D (возможных решений) те которые не соответствуют заданному вопросу и ответу на нему. Но память... Была идея случайным образом брать из общего D и фильтровать через все уже заданные вопросы/ответы. Но так и до пенсии можно ждать... Была идея совмещать два вопрос/ответа в один или несколько и по нему случайно искать возможный ответ и т.д. И еще много чего, но все для далееекого будующего.
За любую помощь, заранее благодарен.
(l) колво позиций <=100
(k) глубина позиции <=20
повторения возможны
Вопрос как реализовать сие?
Любые идеи (даже самые бредовые, у меня и таких уже нет), ссылки, все что можно...
Пока рабочая версия просто прощупывает последовательность, идя слева и проверяя изменение кол-ва быков. На длинных последовательностях также задается k вопросов и создается массив колва символа в последовательности.
Первоначально была идея отсеивать из области D (возможных решений) те которые не соответствуют заданному вопросу и ответу на нему. Но память... Была идея случайным образом брать из общего D и фильтровать через все уже заданные вопросы/ответы. Но так и до пенсии можно ждать... Была идея совмещать два вопрос/ответа в один или несколько и по нему случайно искать возможный ответ и т.д. И еще много чего, но все для далееекого будующего.
За любую помощь, заранее благодарен.
Приведи набор базовых правил игры.
Попробуй вводить варианты по типу bitmask, где для каждой позиции
отводится n(количество возможных вариантов позиции) бит, где 1 значит МОЖЕТ и 0 значит НЕ МОЖЕТ. Таким образом одной битовой записью можно будет запоминать гораздо больше обычных записей, что должно решить проблемы с памятью. А вот проблемы со скоростью поиска решений ты обычными способами (без эвристики) никак не преодолеешь. Однако если проблема с памятью решена, ты сможешь использовать обычный алгоритм. Надо только грамотно организовать разбиение множества вариантов на набор bitmask'ов. Хэш будет не лишним.
Также когда сам реализовывал(давно это было, дос тогда рулил) такую фишку, правда не с такими размерностями, уменьшал количество вариантов для перебора создавая глобальную таблицу запретов: то есть когда известно что в позиции X не может стоять символ Y то эта информация заносилась в таблицу и не прошедшие проверку варианты отсеивались. Вначале это скорее затормаживало, но сильно уменьшало кол-во вариантов к концу.
Попробуй вводить варианты по типу bitmask, где для каждой позиции
отводится n(количество возможных вариантов позиции) бит, где 1 значит МОЖЕТ и 0 значит НЕ МОЖЕТ. Таким образом одной битовой записью можно будет запоминать гораздо больше обычных записей, что должно решить проблемы с памятью. А вот проблемы со скоростью поиска решений ты обычными способами (без эвристики) никак не преодолеешь. Однако если проблема с памятью решена, ты сможешь использовать обычный алгоритм. Надо только грамотно организовать разбиение множества вариантов на набор bitmask'ов. Хэш будет не лишним.
Также когда сам реализовывал(давно это было, дос тогда рулил) такую фишку, правда не с такими размерностями, уменьшал количество вариантов для перебора создавая глобальную таблицу запретов: то есть когда известно что в позиции X не может стоять символ Y то эта информация заносилась в таблицу и не прошедшие проверку варианты отсеивались. Вначале это скорее затормаживало, но сильно уменьшало кол-во вариантов к концу.
Думаю, от повторений стоит отказаться. Решение задачи превращается в лотерею - в подавляющем большинстве случаев за 100 попыток получение верного результата будет невозможным. Всё будет зависеть от того, повезёт или нет. А это уже не логическая игра.
И ещё - вот скажи, каков должен быть ответ, если загадано число 33333333331111111111, а отгадывающий называет число 13131313131313131313?
10 быков и 20 коров?
Или 10 быков (это споров не вызывает) и 10 коров? Или 10 быков и стадо коров? Подумай над этим вопросом и предаставь, как машина должна это определить...
И ещё - вот скажи, каков должен быть ответ, если загадано число 33333333331111111111, а отгадывающий называет число 13131313131313131313?
10 быков и 20 коров?
Или 10 быков (это споров не вызывает) и 10 коров? Или 10 быков и стадо коров? Подумай над этим вопросом и предаставь, как машина должна это определить...
10 быков и 2 коровы, т.к. по правилам алгоритм вычисления ответа не считает одно значение дважды, т.е.
код:
123454
вопрос:
144566
ответ:
1-бык/2-коровы
код:
123454
вопрос:
144566
ответ:
1-бык/2-коровы
[QUOTE=Ireul]...то есть когда известно что в позиции X не может стоять символ Y то эта информация заносилась в таблицу и не прошедшие проверку варианты отсеивались. Вначале это скорее затормаживало, но сильно уменьшало кол-во вариантов к концу.[/QUOTE]
В рабочей версии такая проверка выполняется так:
вначале задаем k вопровсов вида:
111111
222222
333333
444444
.........
hhhhhh
Получаем массив колв colors:
[0]=...
[1]=...
[2]=...
...
[h]=...
А потом задаем вопросы вида:
000000
100000
200000
подставляя только те эл-ты i у которых colors>0
и по изменению колва быков в ответе делаем вывод :
находится ли этот или предыдущий элемент в этой позиции.
После чего уменьшаем colors-- или colors[Prev(i)]--
Но так я только учитываю число быков:(
По производительности, то для задачи 13(k)х91(l) - 572 вопроса
В рабочей версии такая проверка выполняется так:
вначале задаем k вопровсов вида:
111111
222222
333333
444444
.........
hhhhhh
Получаем массив колв colors:
[0]=...
[1]=...
[2]=...
...
[h]=...
А потом задаем вопросы вида:
000000
100000
200000
подставляя только те эл-ты i у которых colors>0
и по изменению колва быков в ответе делаем вывод :
находится ли этот или предыдущий элемент в этой позиции.
После чего уменьшаем colors-- или colors[Prev(i)]--
Но так я только учитываю число быков:(
По производительности, то для задачи 13(k)х91(l) - 572 вопроса
WidowMaker
Есть мысля одна. Чтобы не было непонимания - что ты понимаешь под k и l?
То есть не вполне понятны термины количество позиций и глубина позиций. Количество - это количество шариков (букв и др.) в последовательности, а глубина - это количество возможных цветов (различных символов и др.)? И какое количество итераций для тебя допустимо?
Есть мысля одна. Чтобы не было непонимания - что ты понимаешь под k и l?
То есть не вполне понятны термины количество позиций и глубина позиций. Количество - это количество шариков (букв и др.) в последовательности, а глубина - это количество возможных цветов (различных символов и др.)? И какое количество итераций для тебя допустимо?
Так и есть.
А допустымым считается то колво вопросов которое дает в формуле l*lg(k)/guess_num>=1 (lg-по основанию 2). Впринципе сейчас оптимизирую
это перебор. Сортирую по колву цвета и первыми подставляю самые частые, уменьшаю кол-во и опять сортирую...
ЗЫ: под итерациями надо понимать кол-во вопросов
А допустымым считается то колво вопросов которое дает в формуле l*lg(k)/guess_num>=1 (lg-по основанию 2). Впринципе сейчас оптимизирую
это перебор. Сортирую по колву цвета и первыми подставляю самые частые, уменьшаю кол-во и опять сортирую...
ЗЫ: под итерациями надо понимать кол-во вопросов
Проблема уже решена. Ничего особенного...немного улучшенный перебор и на единицу уже выхожу ... а главное в срок...:)