Dajmy na to generujemy drzewo dla kółko i krzyżyk dla planszy 10x10 do oporu (wyczerpania pamięci, lub dotarcia do końca gry). Czy jest sens trzymać w nim pełne drzewo, czy też idzo jakoś skompresować sprowadzając je do formy w której będziemy trzymali tylko odnośnik do węzła gdzie przechowywane są odgałęzienia dla przypadków obróconych o 90, 180, 270 stopni? Potem sobie te dane poddamy odpowiedniej transformacji przy wykorzystaniu ich w praktyce dla bierzacej gry. Jeśli ma to sens, to czy istnieje jakiś sensowny sposób przeprowadzenia takiej kompresji? Nie jest to praca domowa, tylko luźne rozważanie na temat który mi chodzi po głowie już kilka lat, ale nic sensownego na szybko nigdy nie znalazłem na ten temat.
0
0
Złoty Samiec napisał(a):
Czy jest sens trzymać w nim pełne drzewo, czy też idzo jakoś skompresować sprowadzając je do formy w której będziemy trzymali tylko odnośnik do węzła gdzie przechowywane są odgałęzienia dla przypadków obróconych o 90, 180, 270 stopni?
- obróconych o 90, 180.270 i ich symetryczne warianty.
0
Najważniejsze jest to żeby nie liczyć dwa razy tej samej planszy w różnych gałęziach drzewa, czyli tak zwane spamiętywanie z programowania dynamicznego. Mając już to eliminacja dodatkowo obróconych i symetrycznych zredukuje nam drzewo o plus minus pi razy drzwi maks 6 razy stanów. Czyli stała i to dość niska, jak dla mnie nie warto komplikować implementacji, bo zbyt mało jest do zyskania w tym wypadku.
0
neves napisał(a):
Najważniejsze jest to żeby nie liczyć dwa razy tej samej planszy w różnych gałęziach drzewa, czyli tak zwane spamiętywanie z programowania dynamicznego. Mając już to eliminacja dodatkowo obróconych i symetrycznych zredukuje nam drzewo o plus minus pi razy drzwi maks 6 razy stanów. Czyli stała i to dość niska, jak dla mnie nie warto komplikować implementacji, bo zbyt mało jest do zyskania w tym wypadku.
Nawet jeśli to tylko 6 razy (zakładając, że intuicyjnie, czy jak tam policzyłeś prawidłowo, jednak wolałbym najpierw zibaczyć odpowiednie obliczenia dla przypadku ogólnego rozmiaru N na N) to jeśli drzewa są odpowiednio głebokie to istotną różnicą będzie czy zmieszczą się w 60GB czy 360 w GB. Chyba, że narzut czasowy związany z "kompresją" będzie nieopłacalny. To bym już uznał za o wiele wartościowszy argument "przeciwko". Z drugiej strony, zawsze można korzystać z wcześniej wygenerowanego drzewa zapisanego do pliku. Wtedy 6 razy mniejszy plik może być zaletą. Zwłaszcza w sytuacji ograniczonej przestrzeni pamięci urządzenia. Jeśli pociągnie to za sobą w miarę przynajmniej wprost proporcjonalny przyrost czasu wyszukiwania, to też plus.
0
Raczej mówimy o różnicy na poziomie pi razy drzwi 375 x 10^19 GB a 62 x 10^19 GB zakładając że zapisujemy jedynie różnice między stanami i starczy nam na to 4 bajty, liczba stanów jest na tyle duża że moja magiczna liczba 6 wzięta z sufitu raczej nie robi różnicy, no ale ja w sumie się nie znam, bo nigdy nie miałem do czynienie z drzewami gier których liczenie w całości zajmowałby więcej niż 10 sekund :D