Forum.Gomoku.pl
Forum Polskiego Stowarzyszenia Gomoku, Renju i Pente

Gomoku - Sekwencyjność go-moku

jopq - 2007-10-09, 11:11
Temat postu: Sekwencyjność go-moku
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 - 2007-10-09, 13:42

jopq napisał/a:
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


Hmn jeśli dobrze zrozumiałem odpowiedz brzmi 15 pól czyli maks. Wyobraż sobie vcf zaczynanego z A1 i kończącego się się cutem na na K1 gdyż stoi kamień na O1 dzięki któremu tworzy się cut. Więc nie można zagrać A1 a np A2 trzeba..

jopq - 2007-10-09, 14:11

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 - 2007-10-09, 14:46

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 - 2007-10-13, 00:23

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 - 2007-10-13, 03:13

http://portal.acm.org/citation.cfm?id=1143954
angst - 2007-10-13, 08:17

Barfko napisał/a:
Można np. pokazać, że nie istnieje nieskończony VCF na nieskończonej planszy rozpoczęty od skończonego układu kamieni


Przekładając to na język praktyczny - co to jest nieskończony VCF? Bo coś takiego nie istnieje z definicji :D

Pozdrawiam

Angst

Barfko - 2007-10-13, 20:14

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 - 2007-10-13, 20:39

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" ? :lol: . Może coś w praktyce zamiast suchych wypowiedzi o_O

bad_mojo - 2007-10-13, 21:32

Barfko napisał/a:
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.

Jest coś nieskończonego, co by się opierało tylko na rzeczach skończonych? Miałem świetnego fizyka w podstawówce, przy okazji omawiania prędkości światła, podał nam przykłądy rzeczy, które mogą się poruszać z prędkością większą od prędkości światła: zajączek na ścianie, punkt na przecięciu się ramion nożyczek- ponieważ nie mają masy, nie dotyczą ich też ograniczenia.

templar - 2007-10-13, 22:26

bad_mojo napisał/a:
Jest coś nieskończonego, co by się opierało tylko na rzeczach skończonych?

Zależy w jakim sensie pytasz. Bo czy w ogóle można mówić o nieskończoności w świecie rzeczywistym? Wątpię. A jeśli się poruszamy w świecie matematyki, to mogę Ci mnóstwo przykładów podać, choć podejrzewam, że i tak nie zadowolą Cię. :)

Pozdrawiam
templar

P.S. coś nie tak jest gramatycznie z tym moim ostatnim zdaniem.

Barfko - 2007-10-14, 02:58

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 - 2007-10-14, 08:19

Barfko napisał/a:
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.


Mając na myśli aspekt praktyczny chyba nie chodzi nam o pieniądze, tylko o przełożenie tego na realia gomoku.

Mam więc pytania, do cytowanego stwierdzenia:

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ć?

Odpowiedzi na powyższe pytania dałyby mi możliwość przemyślenia poważnie tej kwestii. A na 1 000 000 USD i tak nie mam szans, więc próbuję od dwóch lat wygrać sobie jakiegoś oficjala :)

Pozdrawiam

Angst

ermijo - 2007-10-14, 09:21

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 - 2007-10-14, 11:44

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ę.

lonewolf - 2007-10-14, 23:54

jopq napisał/a:
http://portal.acm.org/citation.cfm?id=1143954

Ciekawy artykuł. Zastosowanie tego do gomoku mogłoby dać bardzo interesujące wyniki, ale chyba należałoby uwzględnić też inne kształty tych patternów. Ale to szczegół, większym problemem jest to, że w gomoku nie ma bazy dobrej jakości partii, będącej odpowiednikiem bazy partii zawodowców w go.

Barfko - 2007-10-15, 22:59

Prócz tego, że nie ma bazy dobrych partii w gomoku (jest za to niezła baza gier w renju) go ma dodatkowo tę przewagę *) nad gomoku, że jakby nieco więcej zależy od wyglądu, kształtu i wzorców (nie to żebym miał jakieś pojęcie o go). Gra w renju, więc również w gomoku polega w dużej mierze na analizowaniu wąskich drzew. Niejaki Yamagouchi kiedyś nauczał o tym, jak to pewien ruch w pewnej partii mógł był okazać się katastrofą po wykonaniu 42 kolejnych ruchów i doprowadzeniu do fałszywego VCFa; to jest do cięcia. Te 42 ruchy były zdaniem mistrza naturalne i optymalne. W ogóle większość analiz otwarć w renju w pewnym momencie doprowadza nas do sekwencji ruchów niemal nieuniknionych.

*) Ten algorytm grający w gomoku poprzez odcinanie gałęzi ze zredukowanymi VCT (Allis) pokazuje, jak niewielką złożoność ma gomoku i jak głęboko można analizować, o ile potrafi się szybko znajdować VCT w uproszczonej wersji. Go przerasta gomoku w tym sensie nieporównywalną obfitością strategii.

ermijo - 2007-10-16, 07:59

Temat jest "sekwencyjność go-moku", jednak człowiek myśli równolegle. Spoglądając na planszę lub na jej fragment, wybiera optymalny ruch badając układy kamieni jako całość a nie jak czynią to algorytmy oparte na przeszukiwaniu drzewa gry - poprzez badanie kolejnych pojedynczych ruchów, z których wiele człowiek bez zastanawiania się odrzuca jako nielogiczne.
Z drugiej strony, człowiek ma problemy z liczeniem np. kolejności VCT - komputer wykona to szybciej(w zachłannej wersji myślę że górną granicą będzie tutaj silnia z liczby ruchów do wykonania VCF-a).

Człowiek lepiej zapamiętuje wzorce, zwłaszcza wzorce dotyczące gry defensywnej lub co najmniej nieatakującej. Wzorce te w programach praktycznie istnieją jedynie jako biblioteka bazy danych. Mnie jednak nie interesuje wklepywanie do bazy 20 najlepszych(i tak nie mamy pewności jakie to są najlepsze) ruchów dotyczących około (szacuję) 1000-3000 różnych lecz nie absolutnie trywialnych otwarć.

Nie znam się na programowaniu dlatego trudno mi sobie wyobrazić i zaprojektować algorytm, który grałby tak jak ja - tak jak człowiek(ogólnie rzecz biorąc chcący wygrać nie na czas i w jak najmniejszej liczbie ruchów).

Myślę, że konstrukcja algorytmu, który zawiera elementy pozwalające osiągnąć cel gry zwany "wygraną na czas bądź też utrzymywanie remisowej sytuacji za wszelką cenę przy rezygnacji z możliwości ataku", nie jest ciekawym oraz przydatnym dla graczy gomoku zajęciem.

Wydaje mi się również, że dobry algorytm powinien rozpoczynać przeszukiwanie ruchów od tych pozycji, które przeczą zdrowemu rozsądkowi, np. sprawdzanie, czy po takim ruchu jest na pewno porażka. Po ustaleniu progu będącego liczbą ruchów, po których mająca przewagę druga strona nie jest w stanie skutecznie zaatakować(wygrać), należy przyjmować te ruchy jako dobre lub złe. Dlaczego tak?

Często zdarza się podczas gry, że w pierwszych ruchach mało kto uzyskuje znaczącą przewagę. Interesuącę są zatem takie ruchy, które dadzą przeciwnikowi możliwość wykonania "fałszywego ataku", który nie prawa nastąpić aby dać zwycięstwo. No i zresztą podobnie gra człowiek - atakuje jak jest już pewien i nie zwraca uwagi na ruchy, blokujące kolejne zagrożenia składające się na atak do zwycięstwa.

ermijo - 2009-03-14, 22:08

Całkowicie się z tym zgadzam - czyli nic się nie zmieniło w moim rozumowaniu :)

Powered by phpBB modified by Przemo © 2003 phpBB Group