Matematické Fórum

Ondra Bouda, který tu má účet pod nickem anode a který programoval sokobana pro PROSO by ti k tomu určitě mohl říct víc (ikdyž teď je určitě zavalen důležitějšími věcmi). Jeho program totiž nejen úlohu vyřeší, ale sestaví kompletní stavový prostor -- tedy graf tvořený všemi stavy hry, v němž je hranami vyznačeno, odkud kam se dá dojít. Webová aplikace pak sleduje, jak lidé v tomto stavovém prostoru bloudí.

Snad neprozradím mnoho z jeho knowhow, ale dvě výrazná zrychlení jsou tato
* nezáleží na políčku, kde sokoban stojí. Důležitá je jen oblast, ve které se nachází.
* jak píšeš, místo spojového seznamu použít hashovací tabulku. Ondra to psal v PHP, kde fungují asociativní pole. V C++ je STL šablona hash_set, v javě třída java.util.HashSet, v C# neporadím.

Takový program jsem si kdysi též napsal. Najde řešení s nejmenším počtem hýbání kameny.

Dvě pozice považuji za ekvivalentní, nacházejí-li se kameny na stejných místech a existuje-li cesta pro sokobana z místa v jedné pozici do místa ve druhé (bez hýbání kameny) - nazývám to konfigurací hry.

Sestavuju strom (resp. pouze seznam s ukazatelem na otce), kde každé patro je vždy postupně (po konfiguracích) kontrolováno na koncovou pozici a do dalšího patra přidávám pouze "nové" konfigurace.

Snadno se pak zobrazí celé řešení (jde se jen po rodičích).

Také testuji, jestli vkládaná konfigurace není neřešitelná: třeba když obsahuje čtverec z kamenů, kde aspoň jedno místo je "nekoncové", atd. Ostatní viz obrázek


Dále také může člověk do hracího pole označit některá místa jako ta, kam sice může sokoban, ale kam nemůže žádný kámen - typicky rohy. Asi by se to dalo zalgoritmizovat, ale to se mi už nechtělo.

Pro hledání, jestli konfigurace již v seznamu je, používám následující hashování: Mám pole omezené na 32x32, tedy polohu kamenů v konfiguraci reprezentuji bitově kódovanými čísly (32 krát 32bit-int). No a jako hash použiji součet všech těchto 32 int hodnot. Je to velmi rychle vyčíslitelné. Pokud se hash vkládané konfigurace shoduje s již vloženou konfigurací, je třeba ověřit polohu kamenů podrobně, resp. existenci cesty pro sokobana, jak jsem psal výše. To je vlastně účel hash tabulky - rychle vyčíslitelná funkce + pokud se záznam neshoduje, netřeba dál zkoumat a "věci" nejsou stejné.

Pokud to dokončíš, bylo by zajívamé udělat třeba nějaké srovnávací testy.

EDIT: Ideu na prohledávání máme asi stejnou, bitové operace to hezky urychlí. Mám to takhle, pro inspiraci:

#define   GET_BIT(row, col, bit_map)  ((bit_map[row] >> (col)) & 0x01)
#define   SET_BIT(row, col, bit_map)  {bit_map[row] |=  (0x01 << (col));}
#define UNSET_BIT(row, col, bit_map)  {bit_map[row] &= ~(0x01 << (col));}

#define   IS_WALL(row, col)  GET_BIT(row, col, walls)
#define   IS_HOLE(row, col)  GET_BIT(row, col, holes)
#define   IS_BALL(row, col)  GET_BIT(row, col, act.balls)

#define      IS_REACHABLE(row, col)     GET_BIT(row, col, act.reachable)
#define     SET_REACHABLE(row, col)     SET_BIT(row, col, act.reachable)

#define   SET_BALL(row, col)    SET_BIT(row, col, act.balls)
#define UNSET_BALL(row, col)  UNSET_BIT(row, col, act.balls)

#define   SET_WALL(row, col)  SET_BIT(row, col, walls)
#define   SET_HOLE(row, col)  SET_BIT(row, col, holes)

    for (;;)
    {
        if ((pushes_done < act.pushes) || (last_filled_in_work + 500 < filled_in_work))
        {
            pushes_done = act.pushes;
            last_filled_in_work = filled_in_work;

            SET_STATUS_TEXT(UsedDepth((float)filled_in_work * sizeof(POSITION_typ) / (1024 * 1024), max_memory, pushes_done));
        }

        if (found_solution = is_act_the_final_position()) break;

        for (row = 1; row < LEN - 1; row++) for (col = 1; col < LEN - 1; col++)
        {
            if (IS_BALL(row, col))
            {
                if (IS_REACHABLE(row - 1, col) && !IS_BALL(row + 1, col) && !IS_WALL(row + 1, col) && !IS_NOBALL(row + 1, col))
                {
                    UNSET_BALL(row, col);
                    SET_BALL(row + 1, col);
                    SET_SOKOBAN(row, col);
                    compute_hash_for_act();
                    
                    if (is_act_a_new_position() && is_act_allowed(row + 1, col, row, col)) if (is_act_allowed_by_user(hWnd))
                    {
                        act.parent = act_index_in_work;
                        act.pushes += 1;

                        if (add_act_to_heap())
                        {
                            MessageBox(hWnd, (LPCTSTR)"Out of memory.", szTitle, MB_OK | MB_ICONWARNING);
                            return 0;
                        }
                    }

                    act = work[act_index_in_work];
                }

                if (IS_REACHABLE(row + 1, col) && !IS_BALL(row - 1, col) && !IS_WALL(row - 1, col) && !IS_NOBALL(row - 1, col))
                {
                    UNSET_BALL(row, col);
                    SET_BALL(row - 1, col);
                    SET_SOKOBAN(row, col);
                    compute_hash_for_act();
                    
                    if (is_act_a_new_position() && is_act_allowed(row - 1, col, row, col)) if (is_act_allowed_by_user(hWnd))
                    {
                        act.parent = act_index_in_work;
                        act.pushes += 1;

                        if (add_act_to_heap())
                        {
                            MessageBox(hWnd, (LPCTSTR)"Out of memory.", szTitle, MB_OK | MB_ICONWARNING);
                            return 0;
                        }
                    }

                    act = work[act_index_in_work];
                }

                if (IS_REACHABLE(row, col - 1) && !IS_BALL(row, col + 1) && !IS_WALL(row, col + 1) && !IS_NOBALL(row, col + 1))
                {
                    UNSET_BALL(row, col);
                    SET_BALL(row, col + 1);
                    SET_SOKOBAN(row, col);
                    compute_hash_for_act();
                    
                    if (is_act_a_new_position() && is_act_allowed(row, col + 1, row, col)) if (is_act_allowed_by_user(hWnd))
                    {
                        act.parent = act_index_in_work;
                        act.pushes += 1;

                        if (add_act_to_heap())
                        {
                            MessageBox(hWnd, (LPCTSTR)"Out of memory.", szTitle, MB_OK | MB_ICONWARNING);
                            return 0;
                        }
                    }

                    act = work[act_index_in_work];
                }

                if (IS_REACHABLE(row, col + 1) && !IS_BALL(row, col - 1) && !IS_WALL(row, col - 1) && !IS_NOBALL(row, col - 1))
                {
                    UNSET_BALL(row, col);
                    SET_BALL(row, col - 1);
                    SET_SOKOBAN(row, col);
                    compute_hash_for_act();
                    
                    if (is_act_a_new_position() && is_act_allowed(row, col - 1, row, col)) if (is_act_allowed_by_user(hWnd))
                    {
                        act.parent = act_index_in_work;
                        act.pushes += 1;

                        if (add_act_to_heap())
                        {
                            MessageBox(hWnd, (LPCTSTR)"Out of memory.", szTitle, MB_OK | MB_ICONWARNING);
                            return 0;
                        }
                    }

                    act = work[act_index_in_work];
                }
            } /* if (IS_BALL */
        } /* for(row, col */

        if (++act_index_in_work == filled_in_work)
        {
            /* no more possibility */
            break;
        }
        act = work[act_index_in_work];
    
        if (AbortComputations) 
        {
            MessageBox(hWnd, (LPCTSTR)"Computations aborted.", szTitle, MB_OK | MB_ICONINFORMATION);
            return 0;
        }

    } /* for (;;) */
    
    if (!found_solution)
    {
        MessageBox(hWnd, (LPCTSTR)"There exists no solution.", szTitle, MB_OK | MB_ICONINFORMATION);
        return 0;
    }

EDIT2: benchmark - řešení tohohle najdu za 7 sekund (notebook Intel Core2 DUO 2.66GHz) - 182 kroků, 27 hýbání s kameny

↑ BrozekP: S tím hashováním to mám takto:

Uvažme konfiguraci na obrázku výše a značme 0b......... dvojkové číslo (což tak nejde, ale to je teď jedno). Po řádcích (první vynechávám, protože to jsou samé zdi:

balls[0] = 0b00000000000000000000000000000000
balls[1] = 0b00000000000000000000000000000000
balls[2] = 0b00100100000000000000000000000000
balls[3] = 0b00101000000000000000000000000000
balls[4] = 0b00000100000000000000000000000000
balls[5] = 0b00101000000000000000000000000000
samé nuly dál,

(de facto pole těchto intů je přesně struktura, kde mám uloženy jak kameny, tak zdi, takže žádnou konstrukci těchto čísel nepotřebuji a jen na ní využívám makra z předchozího příspěvku).

Tedy klíč pro tuto konfiguraci je \sum_0^31(balls[i]) = 251658240. Klíče jsou ve vyhledávacím stromu s linky na konfigurace. Pravděpodobnost, že se klíče různých konfigurací shodují, je dle mého docela malá. Takže to považuji za dost rychlé. Samozřejmě, jsou-li konfigurace rozdílné například pouze v tom, ve které oblasti stojí sokoban, pak mají stejný klíč.

Ohledně těch oblastí: Zdi jsou fixní a moje konfigurace se de facto skládá ze dvou 32 intových polí, jedno pro polohy kamenů a jedno pro oblast, kde se může nacházet sokoban. Tato oblast se vždy počítá v okamžiku, kdy se nová konfigurace přidává do seznamu (čtyřsouvislý flood-fill od aktuální pozice sokobana, kde překážkami je logický součet zdí a kamenů).

↑ musixx:

Nejsem si jistý, jestli už chápu ten hash správně. Součet mi totiž vychází 2013265920. Když sokoban posune kámen svisle, tak se hash nezmění? Např. když udělá krok dolu, tak to bude vypadat

balls[0] = 0b00000000000000000000000000000000
balls[1] = 0b00000000000000000000000000000000
balls[2] = 0b00100100000000000000000000000000
balls[3] = 0b00101000000000000000000000000000
balls[4] = 0b00000100000000000000000000000000
balls[5] = 0b00001000000000000000000000000000
balls[6] = 0b00100000000000000000000000000000
...nuly
?

(Edit: Budu si muset přečíst ten kód cos posílal, zatim se mi do toho moc nechce, vypadá to složitě. :-) )

To tvé hrací pole bych v rozumném čase nespočítal, shora bych byl omezený asi milionem a půl mých konfigurací a po několika minutách jsem zkontroloval asi jenom deset tisíc. Zkus tenhle level:



35 sekund (PC, AMD Athlon(tm) 64 Processor 3700+ 2.20GHz) - 430 kroků, počet hýbání s kameny nezjišťuju.

(Edit: 10 sekund, pokud při hledání nevypisuju nic na obrazovku, ale řádově je to pořád špatný.)

Tak kolik milisekund to zabere tobě (pokud aspoň jednu)? :-)

↑ BrozekP: S tim hashem mas pravdu. Ten priklad, co uvadis, u me produkuje opravdu stejny klic. Mozna se nad tim jeste nejak lepe zamyslim a pomuze mi to jeste snizit cas vypoctu.

musixx napsal(a):

Klíče jsou ve vyhledávacím stromu s linky na konfigurace.

Chápu dobře, že ty spočítáš hash pro konfiguraci, kterou zrovna testuješ, a pak ještě musíš hledat link ve vyhledávacím stromu podle hashe? Já jsem myslel, že přednost hashování je v tom, že spočítám hash a pak už nic nemusim hledat. Takhle by celý smysl hashe byl pouze v přiřazení nějakého pokud možno jedinečného čísla každé konfiguraci.

↑ musixx:

Tak jsem to vylepšil, konfiguraci už mám stejnou jako ty. Hash ale vytvářím jednoznačný ke každé konfiguraci, pokud tedy hash už existuje, můžu si být jistý, že už jsem na konfiguraci narazil dřív. Já si ukládám konfiguraci jako objekt, kde mám uloženou pro každé hrací políčko informaci, jestli tam sokoban může (to mám tedy stejně jako ty) a pak pole souřadnic, kde jsou kameny. Hash počítám tak, že vezmu první dostupné pole (nejvíce vlevo nahoře) a počítám:

ID := PrvniDostupnePole.x*NY + PrvniDostupnePole.y;
for i := 1 to PocetBeden do
  ID := ID*NX*NY + Bedna[i].x*NY + Bedna[i].y;

(NX a NY jsou rozměry hracího pole)

Pokud beden není moc a rozměry jsou rozumné, tak na to stačí Int64. Např. při sedmi bednách mám maximální rozměry 15x15, pokud jsem dobře počítal. To mi přijde postačující.

Hash pak hledám v poli seřazeném podle ID, kde mám uložené ukazatele na objekty konfigurací. Při hledání postupuju tak, že procházím postupně frontu, do které na konec přidávám nové konfigurace. Takže najdu řešení s nejmenším počtem posunů beden. Nejvíc mi to teď asi zpomaluje to, že při ověřování konfigurace vytvářím zbytečně objekt konfigurace, hledám všechny dostupné pozice, z nich vyberu tu první a pak teprve můžu spočítat ID. Pořád to mam pomalé - zkus tenhle level (měl by být o dost těžší než ten co jsem posílal minule):



1 minuta a 33 sekund, 56 hýbání s kameny. Celkem prošlých konfigurací: 144047.

Půjdu si udělat oběd, mezitím nechám běžet řešení toho tvého hracího pole a jestli se dopočtu řešení, tak ho sem potom dopíšu :-)

Edit (po asi hodině od spuštění): Tak tam asi mam chybu, prošel jsem přes 700000 různých konfigurací, ve frontě jich čeká ještě asi 400000, z kterých se postupně vytváření pořád další. Jsem zatím na 22 pohybech beden. V ramce už to zabírá půl giga :-)

Tak to byla hloupá chyba, počítal jsem špatně ID - kvůli ní to někdy rozlišovalo pořadí beden.

Ten tvůj level - 7,5 sekundy, 27 hýbání s kameny :-) To už by chtělo pustit na stejném počítači, aby se to dalo přesněji srovnávat :-)

Ale to podstatné zrychlení je díky tobě, kdybych to vymýšlel sám, tak bych asi to zjišťování dostupných políček neudělal tak dobře. O prázdninách to asi zkusím ještě zrychlit, přidělám tam to hashování.

Zdravím,

můj druhý level: 0,890s, 2,7MB, 9819 konfigurací, 9800 jich program prošel. (Ta paměť je ale jen orientační, neměřím to přesně, je to pouze rozdíl spočítaný ze správce úloh ve Windows.)

Jsem zvědavý, jestli se nám to podaří ještě nějak výrazně zrychlit. Už bych ale nečekal tak podstatné zrychlení jakým jsem teď prošel.

Ty levely co sem dávám jsou z PROSO, doufám, že se organizátoři nezlobí.