|
|
|
Тема
|
 Симулация на пасианса Клондайк.
|
|
| Автор |
Гpиro ( играчът ) |
| Публикувано | 02.03.12 21:29 |
|
|
Налага ми се да напиша симулатор за пасианса .
Целта е да се определи, при оптимална игра, средно колко карти могат да се качат в крайните четири позиции.
Подхода за решение, който съм избрал е пълно изчерпване. Тоест, строя дървото на състоянията и проверявам, кой път в дървото е най-оптимален за конкретното разиграване.
Още не съм написал алгоритъма, че е рекурсивен и доста сложен. В един момент се замислих дали няма да се получи комбинаторен взрив? Интуитивно ми се струва, че няма чак толкова много комбинации. Как смятате, дали ще имам проблем с твърде голям брой комбинации?
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: Гpиro]
|
|
| Автор |
clovenhoof () |
| Публикувано | 02.03.12 21:37 |
|
|
Бе как така ти се налага да пишеш такива интересни неща пък аз само bug fixing и нищо от scratch?
____________________
Potes meos suaviari clunes
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: Гpиro]
|
|
| Автор |
croesus (хлевоуст) |
| Публикувано | 02.03.12 21:39 |
|
|
Добре де, то дори в статията има линкове към математически анализи + готов код. Това, което виждам е, че ако играта е реализируема (защото има и неразрешими ситуации) средното време за намиране на оптимален път е 2 минути, но ако нереализируема - 420 минути. Очевидно има "комбинаторен взрив", както го наричаш ти.
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: clovenhoof]
|
|
| Автор |
Гpиro ( играчът ) |
| Публикувано | 02.03.12 22:14 |
|
|
С много търсене. Тази задача е от една много малка фирма в София, за която се чу съвсем малко, в един много тесен интервал от време. Чист късмет беше, че попаднах на тях. Те правят и други още по-интересни неща.
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: croesus]
|
|
| Автор |
Гpиro ( играчът ) |
| Публикувано | 02.03.12 22:24 |
|
|
е доста позната концепция. Класика е да се проявява при задачи за които броят на възможните състояния е твърде голям.
Всъщност, задачата беше по-различна, но аз реших да я опростя, защото оригиналният вариант е действително сложен за реализация. Оригиналното задание е да се напише изкуствения интелект, на човек играещ оптимално този пасианс. Оптималната игра на човек не е оптимално възможното решение от математическа гледна точка. От математическа гледна точка, оптималната стратегия е все едно знаеш какви са и скритите карти. Тоест, ако се пробват всички възможни ходове (тоест се построи цялото дърво на състоянията) е все едно да знаеш всички карти предварително.
За оптималната игра, на реален играч човек, има група от десетина правила, които практиката е показала, че водят до по-добри резултати. Реалното питане е каква би била успеваемостта на този пасианс, ако човек (не машина) играе по оптимално известната до момента стратегия. Правилата са чисто емпирични и получените решения са далече от глобалния математически оптимум.
Все пак, за да се реализира група от правила то е все едно да си напишеш rule engine (тоест експертна система), а това си е трудна задача, дори за топ професионалисти.
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: Гpиro]
|
|
| Автор |
zaphod (мракобес) |
| Публикувано | 04.03.12 10:37 |
|
|
игт?
NE SUTOR ULTRA CREPIDAM
| |
|
Тема
|
Re: Симулация на пасианса Клондайк.
[re: Гpиro]
|
|
| Автор |
mihail121 (новак) |
| Публикувано | 04.03.12 13:40 |
|
|
Помага стандартният подход, наблюдавай се какво правиш ти. Аз гледам 3-4 карти напред как да отворя освободя групирам.
| |
|
|
|
От пръв поглед се сещам за варианта в който в едната колона имаш карти 6 спатия и 5 купа, а в другата имаш 6 пика. След това с пълното обхождане можеш да циклиш колкото искаш петицата между двете шестици ... а това е само най-простия вариант да зациклиш.
--------------------------
Там където свършват всички Надежди ... започва Обеля!
| |
|
|
|
При DFS се проследява наличието на цикли в дървото на състоянията и те се избягват.
| |
|
| 
|
|
