6
Rozważam symulację wszystkich ruchów, ale to nie może być najlepszy sposób, aby to osiągnąć. Propozycje?Jaki jest optymalny sposób ustalenia, że nie można wykonać ważnego ruchu w Bejeweled?
A
Odpowiedz
0
Nie twierdzę, że jestem ekspertem od tego typu problemów, ale pomyślałem, że przez to trochę przemyślę.
Sposób, w jaki podchodzę do tego, to myślenie o tym, jak człowiek podejdzie do problemu. Człowiek nie usiadłby i nie wykonałby wszystkich możliwych ruchów (nawet tych niewłaściwych). Najprawdopodobniej zeskanują planszę i poszukają wzorów. Trzeba to porównać ze skanowaniem w poszukiwaniu wszystkich możliwych ruchów, które mogą być szybsze w zależności od optymalizacji algorytmu i struktur danych. (W rzeczywistości, inną rzeczą, o której pamiętałem, może być, gdy wstawiasz każdy nowy klejnot do planszy, zachowujesz z nim powiązane metadane, które wskazywałyby, że ma on prawidłowy ruch związany z tym. aktualizowany więcej ruchów zostały wykonane)
Aby lepiej wyjaśnić moje podejście „poszukuje wzorców”, rozważmy następujący wzór klejnot.
(0)
x x
x
powyższy wzór (zakładając, że x jest skanowanym kolorem) spowoduje prawidłowy ruch. Możesz zeskanować planszę i sprawdzić każdy obszar 6x2 i 4x1, aby znaleźć możliwe ruchy.
następujące wzory będzie kandydatami:
(1)
x
x x
(2)
x x x
(3)
x x x
(4)
x
x
x
(5)
x
x
x
(6)
x
x
x
(7)
x
x
x
(8)
x
x x
(9)
x x
x
(10)
x x
x
(11)
x
x x
(12)
x
x
x
(13)
x
x
x
2
"Najlepszy" jako co najmniej kod? najbardziej elegancki kod? najmniej teoretyczna liczba kroków algorytmu? lub najlepiej radzi sobie w określonym języku na konkretnej platformie sprzętowej?
W każdym przypadku, w przypadku tak niewielkiego problemu (około 112 możliwych ruchów) skanowanie brute-force jest prawdopodobnie najlepszym podejściem do tych pomiarów. Jedną z optymalizacji, którą możesz rozważyć, jest wstępne wykonanie wszystkich koniecznych porównań. Możesz napisać program, który je wylicza i wygeneruje pojedynczą (dużą) instrukcję if, a następnie pozwoli, aby kompilator ją zoptymalizował. If może wyglądać ...
if ((cell[0,0] == cell [0,2] && cell[0,0] == cell [0,3]) || (...)
lub jako Chciałbym powiedzieć ...
„Nigdy nie lekceważ potęgi o Intel CPU do optymalizacji niemy liniowy algorytmy korzystające sekwencyjny pamięć lokalizacje w ciasnych pętlach. "
0
Chciałbym zobaczyć ten problem bardziej jako ważony zestaw węzłów. Być może nieco zbyt uproszczone, ale masz zestaw węzłów klejnotów obok siebie. Jeśli węzeł nie pasuje do jednego z sąsiednich węzłów, ma wartość 0.Jeśli ma wartość 1, dopasowuje się do jednego z otaczających go elementów (a otaczający węzeł będzie odpowiadał 1, lub może nawet więcej!). Z tego ważonego systemu wystarczy zaktualizować węzły, które miały zmieniono sąsiedni węzeł. Wartość 2 powinna być dobrym wyznacznikiem dobrych rzeczy, które mają nadejść, ale jak wspomniano w poprzedniej odpowiedzi, istnieją pewne wzorce, które mogą pomóc w dalszej optymalizacji tego ...
Bardzo konkretny przykład logiki gry AI ogólnie, podoba mi się . Rozmyślałem o tym samym pytaniu na temat pisania sztucznej inteligencji dla Reversi, ale nigdy się do tego nie zbliżałem. Mam nadzieję, że dobre odpowiedzi ... – David
jest to dla http://gamedev.stackexchange.com/ – Trufa
To jest związane z programowaniem, więc jest to mile widziane pytanie tutaj, ale zgadzam się z @Trufa, że prawdopodobnie będziesz lepiej odpowiedzi na stronie Game Dev. Mogę go migrować, jeśli chcesz. –