Решение пасьянса FreeCell

Я вот подумала, как бы написать программку для решения пасьянса FreeCell. Кто не в курсе, это такая игра от MS, которая устанавливается вместе с Виндой.

Написать хочу сама. Только не совсем понятно как подступиться. Есть идеи?

мою тему вообще кто-нибудь видит? или я что-то не так сделала?
извините, на этом форуме тему первый раз начинала %)

Ну, тут как бы две проблемы. Первая — сам алгоритм решения пасьянса. А вторая — как сделать так, что бы запустить сам FreeCell и запустить мою программу, и что бы моя программа давала команды FreeCell по перемещению карт, как это обычно делается с помощью мыши.

За последние полгода, кажется, единственная интересная задача.
А в результате пока 0.(0)

Похоже ресурс-то склеивает ласты ((

Похоже ресурс-то склеивает ласты

Ну так не появляется ничего интересного, поэтому и затухает.

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

М-м-м... На счет распознавания карт есть одна идейка. В FreeCell каждый расклад пронумерован. Номер расклада выводится слева в строке статуса («Game #NNNNN»). Через меню тоже можно выбрать расклад по его номеру. Остается немного: выяснить зависимость конкретного расклада карт от этого номера ))

Но взаимодействие с запущенным оригинальным FreeCell — это как бы вторая проблема, задача-максимум. Первая проблема — решение самого пасьянса. Я прикинула, сделать колоду, начальную раскладку карт и что-то типа игрового стола — несложно. Правила перекладки — тоже решаемо. А вот с логикой решения пасьянса — плохо. У меня не получается выделить и формализовать правила, которые я применяю при игре в FreeCell. Но когда я сама играю, я же не случайным образом перетаскиваю карты?! И этот пасьянс у меня сходится всегда. Значит какие-то правила есть?

Зависимость расклада от «Game #NNNNN» — это

  1. Лезть в код программы — не спортивно, не универсально и нужно быть немного хакером.

  2. Ручка, бумажка и усидчивость — зайди в меню «Игра»->«Выбрать игру», миллион вариантов. По статистике, женщина живет в среднем... Не хочется чтобы твои пра-пра...пра-правнуки продолжали дело своей пра-пра...пра бабушки в написании бота для FreeCell . :-) Чтобы это решить, нужно написать программу, а она должна распознавать карты с экрана и сопоставлять его с «Game #NNNNN». Но если мы это решим, то зачем нам вообще нужен этот второй метод.

Взаимодействие с программой — это самая легкая проблема.

Логика сходимости — это пока не для меня. Ну не играю я в пасьянсы. :-(

У-у-у.......
Так не интересно ((
Я сама хотела такое написать

Я и не предлагаю брать готовое. Просто показал, что задача решаемая. У меня тоже есть идеи, но я больше программист теоретик. Всю жизнь читаю книги по программированию, код тоже писал, но давно, времени не хватает. Первая игра мной написанная — карточный покер.
Это было еще в те года, когда программы сохраняли на кассетах, но я не об этом... На работе у меня тоже многие складывают пасьянс но объяснить зачем они делают данную перекладку в данный момент, тоже не могут. В сети можно найти алгоритм решения данной задачи, но мне так тоже не интересно. На выходных напишу полигон для отработки логики решения различных пасьянсов. А ты то уже сделала?

Я знаю, что решаемая. Но когда видишь, что ЭТО уже кто-то сделал, интерес сильно страдает.

А программист-теоретик — это как? В смысле что вы делаете на работе?

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

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

Программист теоретик — это прочитал и читаю много книг по данной теме, различным языкам программирования, хакингу и защите, обработка изображений, распознавание образов, искусственный интеллект итд. Изучил много программ, занимался 3d моделированием и скульптингом. У меня хобби все и ничего конкретно. Но зная это все нельзя, стать профессионалом в какой то области.

Работа с компьютерами не связана, я водитель. На работе единственный комп. это мой смарт с бейсиком, вот на нем я сейчас и пишу полигон для отработки алгоритма, при том он должен просто перенестись на С++.

Насчет алгоритма:

  1. Если карта в столбце может лечь на базу — ложим.
  2. Проверяем количество временных свободных ячеек, если есть карта
    лежащая в столбцах не дальше от края чем количество ячеек плюс одна
    и может лечь на базу — ложим карты в свободные ячейки и карту на
    базу.
  3. Если есть карта в столбце ложащаяся на другую карту в другом столбце — ложим.

Ну дальше ты... Просчет на перед и выбор лучшего варианта из имеющихся с тебя. Да еще и новые правила. А вообще совет, сперва займись песочницей иначе как проверять алгоритм? Да и программа должна сообщать о чем она думает иначе если очень задумается (зависнет), нужно знать где алгоритм не верен. Помощь в коде не предлагаю, ведь ты хочешь сама. Но сообщи на каком уровне владеешь языком.

Все предложенные правила тупиковые. Мои комментарии соответствуют по номеру твоим правилам.

  1. Карта может понадобиться для перекладки других карт. Кстати недаром пасьянс начинает автоматически собираться только при выполнении неких условий. А твое правило в пасьянсе можно заставить работать правым кликом на свободном поле. Только это нужно далеко не всегда.
  2. Достаем одну карту на базу и остаемся с забитыми временными ячейками и минимальной возможностью для перекладок. Иногда прокатывает, но чаще Ctrl-Z * 5.
  3. Если есть две свободные карты, которые можно переложить на одну. Какую выбрать? Это раз. Если есть одна свободная карта, которую можно положить на одну из двух. На какую ложить?

Тут как бы все не так просто.

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

2-е правило я и отмел, но не совсем.

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

  1. Так какой же ход сделать из двух, трех... возможных? А может обойти все варианты? Компьютер такие задачи решает очень быстро. Могу дать намек если ты хочешь этого. Но ведь мы не можем просчитать все ходы наперед, мы это решаем ка кто по другому.

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

Ну насчет того, чтобы попрактиковаться в программировании я не спрашиваю, ведь полигон для проверки алгоритма, ты не написала.:-( Если с этим проблемы, спрашивай. Сперва помогу общими советами, если и дальше ни ни, то кодом.

В пасьянсах есть начальная раскладка, цель и правила перекладки. Это всё известно и формально описано — это не проблема. Проблема в алгоритме решения в пределах правил перекладки.

Прохождение лабиринта в худшем случае дает полный обход этого самого лабиринта. В нашем случае — это brute force. На крайний случай, конечно, пойдет. Только сомневаюсь на счет «Компьютер такие задачи решает очень быстро». Здесь только из начальной позиции 8 альтернатив. А если добавить еще 4 карты во временных ячейках — это уже 12.

Самообучающийся алгоритм — звучит заманчиво. Но боюсь, что очень сложно.

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

Да, с полигоном я немножко засела. Со временем напряги (( Хочется по уму все написать, что бы потом к этому уже не возвращаться.

У меня тоже пока нет времени, в субботу работал.
Brute force + вероятность успеха данной ветки обхода. Вероятность успеха ты можешь выставить сама. Но можно доверить это программе — чем чаще, или быстрей или то и другое вместе, программа натыкается на тупик, вероятность уменьшаем и наоборот. Вот в принципе и все самообучение.(Но это только мое мнение).
Пора бежать. Вернусь, поделюсь своими мыслями насчет полигона — песочницы. Самое главное она должна без изменения превратится в бота или в игру и притом любой карточной игры, головоломки, фокуса...

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

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

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Предпросмотр сообщения

Ваше сообщение пусто.