Forum.Gomoku.pl

[jopq]

Ostatnio czytając o sekwencyjnych strukturach danych, wzorcach, algorytmach ich przeszukiwania zadałem sobie pytanie: na jaką powierzchnię wokół na planszy ma oddziaływanie każdy ruch? Pytanie wcale nie takie głupie, bo może udało by się całą grę zapisać w postaci skończonej maszyny stanów, gdzie dla każdej możliwości wykonywało by się parę operacji wyceniających daną pozycję. Być może kamień ma wpływ na otoczenie rzędu 4 pól? Kto wie. Gdyby mieć narzędzie w postaci API jakiegoś dobrego programu do gomoku, to można by się pobawić. Czym różni się to podejście od heurystyk? Ano choćby tym, że tutaj istotna jest kolejność ruchów.
Ludzki mózg przecież nie sprawdza wszystkich możliwości, nie ocenia też czysto heurystycznie, bo "działa" w oparciu o właśnie poznane sekwencje, których uczy się i ulepsza cały czas. Może ktoś będzie miał ochotę podzielić się swoimi przemyśleniami :P

[utratos]

[jopq]

Czy ruch postawiony w grze, który został obudowany dookoła (skrajny i kiepski przykład: czarny i 8 białych wokół), ma jeszcze znaczenie przy szukaniu kolejnych?

[utratos]

Znaczy zmienia w tym sensie , że
- czarny został przyblokowany
- czarny mógł też w danym polu stworzyć układ szóstkowy a teraz może wybrać inne pole na planszy , które mogło być zajęte przez białego gdyby nie postawilł tam swojego ruchu
Natomiast dla białych -"nie biorących pod uwagę czarnych" ten kamień nic nie daje w osiągnięciu zwycięstwa( jest zmarnowany) ale to sytuacja hipotetyczna:)

[Barfko]

Są tu dwa pytania.

1. Czyli istnieje "dobra" funkcja ewaluująca pozycję na planszy mająca małą złożoność.
2. Które kamienie mają wpływ na taką hipotetyczną funkcję.

Pierwsze pytanie ~łatwo sprowadzić do "P=NP".

Na drugie pytanie można dość łatwo odpowiedzieć. Wystarczy zdefiniować obszar zapełniony kamieniami następnie zdefiniować inteligentnie brzeg tego obszaru o grubości 5. Kamienie siedzące głębiej, niż 5, są nieistotne, o ile odrzucić overline, co jest tanim uproszczeniem, bo i bez overline pytanie numer 1 jest równoważne "P=NP".

Zalążkiem ciekawej funkcji ewaluującej może być Energia, zdefiniowana jako ogólna liczba swobód wszystkim kamieni danego koloru na planszy. Łatwo kontrolować energię i łatwo różne rzeczy o jej zachowaniu wraz z rozwojem gry udowodnić. Można np. pokazać, że nie istnieje nieskończony VCF na nieskończonej planszy rozpoczęty od skończonego układu kamieni.

Krótko mówiąc idea bardzo szczytna i w dodatku za odpowiedź na owe pytania dostaje się aktualnie 1.000.000$.

[jopq]

http://portal.acm.org/citation.cfm?id=1143954

[angst]

[Barfko]

Skoro prowadzi to do nieporozumień i ktoś w ogóle to czyta, to sprecyzuję.

Dla każdego skończonego układu kamieni na planszy zbiór VCF, wszystkich możliwych zwycięstw poprzez sekwencję czwórek, jest skończony.

[zukole]

Ostatnie zdanie brzmi jak definicja pierdoł podanych przez moją nauczycielkę od matmy.

Były już rozważania na temat otwarć, programów itd, teraz będzie szereg dyskusji na temat "nieskończonego vcf-a" ? . Może coś w praktyce zamiast suchych wypowiedzi

[bad_mojo]

[templar]

[Barfko]

Cytat:

Może coś w praktyce zamiast suchych wypowiedzi.

Za rozstrzygnięcie "P=NP" jest 1 mln USD, dostaje się z dużym prawdopodobieństwem 2 nagrody, Fields i Nevalina, każda też dość opłacalna oraz w przypadku pozytywnego rozstrzygnięcia tej hipotezy można złamać większość używanych na świecie szyfrów. Dla mnie to dość konkretne, hehe, i znacznie praktyczniejsze od wygrania gazyliona turniejów na kurniku.

[angst]

[ermijo]

Nie ma czegoś takiego jak nieskończony VCF, ponieważ aby wykonać jakiś VCF musi zaistnieć odpowiednia sytuacja na planszy już nie mówiąc o tym czy jest ona powstała naturalnie czy ułożona. Wydaje mi się również, że nie ma takiej początkowej sytuacji kamieni na planszy, żeby dysponując nieskończoną planszą, przy optymalnych ruchach utrzymać wartości funkcji oceniającej na stabilnym poziomie(mam na myśli stabilność na granicy oscylacji). Uważam, że układ kamieni nie pozostanie stabilny, gdyż jedna ze stron będzie miała przewagę. Ciężko za to powiedzieć, ile ruchów stanowi minimum do wyjścia z bardzo wyrównanej dla obydwu stron pozycji przechylając szale na zwycięstwo. Myślę też, że nie potrzeba przeglądać bardzo daleko(w sensie odległości od biorących udziału w gdzie kamieni) planszy. Jak tutaj wspomniano, ważne są brzegi zagrożeń czyli graniczne pozycje na planszy rozdzielające 2 obszary:

- obszar, w obrębie którego nie jesteśmy w stanie skutecznie zaatakować, gdyż będziemy "zamykani" czy tez otaczani przez przeciwnika
- obszar, w obrębie którego oddajemy przeciwnikowi zbyt duże pole a on rozbudowuje przewagę - np. jakiś długi ruch na 5 pól od właściwego układu...

Zatem wydawać się może, że ta ów granica między obszarami stanowi optymalne położenia przy kolejnych ruchach. Ale jak wygląda? Zauważyłem, że układa się ona w kształt konika szachowego lub też podwójnego konika szachowego. Ruch konikiem to przejęcie tempa - w przypadku pojedynczego ruchu konikiem, lub powiększanie przewagi wraz z kontrolą co może zrobić przeciwnik ruch "long horse", czyli np. 2 ruchy skoczka na szachownicy z punktu A do B jako jeden.

[Barfko]

Cytat:

1. Skończony układ kamieni - czyli, jak rozumiem, jest ich znana ilość, np. 120? 2. Czy sekwencja czwórek może powstać i kilkadziesiąt ruchów później? (ale wtedy chyba zmierzamy w stronę nieskończoności) 3. Czy vcf to także jedna czwórka? (swoją drogą kiedyś w trakcie naszych dyskusji wypracowałem piękną definicję vcf i wysłalem na priv - masz ją jeszcze? ) 4. Czy kamienie w tym skończonym układzie mają ustaloną pozycję na planszy, czy też możemy je przekładać?

Układamy na nieskończonej planszy w jakikolwiek sposób skończoną liczbę kamieni i rozpoczynamy robienie czwórek, które są blokowane. Fakt, o którym wspomniałem powiada, że układania kolejnych czwórek nie można kontynuować w nieskończoność. Czy jak kto woli, dla każdego układu na planszy istnieje ograniczenie górne na długość sekwencji czwórek. Czy jak kto woli dla każdej liczby kamieni istnieje ograniczenie górne długości sekwencji czwórek na planszy zależne tylko od liczby kamieni. Ruchy są wykonywane zgodnie z zasadami gomoku, więc nie można przestawiać w trakcie gry.

Angst, za VCF w gomoku zwykło się uważać sekwencję czwórek wykonywanych przez jednego z graczy i blokowanych przez drugiego prowadzącą do zwycięstwa. Zastanawianie się, czy jedną czwórkę (np. powstałą z otwartej trójki) można już uznać za VCF ma niewielkie znaczenie aż do momentu, gdy próbujemy podać definicją VCT. Wtedy warto przyjąć, że jedna czwórka może być VCF-em, bo skróci to istotnie definicję VCT, szczególnie w renju.

Granie w gomoku w ogóle ma niewielkie znaczenie praktyczne. Jest to rozrywka umysłowa. Podobną rozrywką umysłową jest rozwiązywanie problemów inspirowanych gomoku. W świecie rzeczywistym obserwujemy różne wydarzenia starając się znaleźć zbiór możliwie prostych reguł, z na podstawie których da się te zdarzenia wytłumaczyć. Zagadnienie jest nieuchwytne, ale nieustannie popycha ludzi naprzód. Z gomoku jest na odwrót. Reguły już znamy i są proste, można więc pytać, jakie są możliwe zdarzenia odwracając tym samym całą zabawę.