Artur Wydra - 2005-04-28, 20:44 Temat postu: Rozpoczęcie wygrywające Witam! Zna ktoś algorytm jak można wygrać w Gomoku (zwykłym) rozpoczynając ruch. Podobno coś takiego jest. Nauczycielka od majcy powiedziała, że da mi 5 na koniec jak dam jej ten sposób 
soul_reaper - 2005-04-28, 21:00 Jak chcesz moge podeslac Ci prace doktorska Victora Allisa w ktore podal on dowod na istnienie pewnego zwyciestwa w standardowym gomoku. Natomiast algorytmu jako takiego raczej nikt Ci nie poda. Allis przeprowadzil swoj dowod podajac wszystkie mozliwe kombinacje ruchow za pomoca programu Victoria. Program ten korzysta z bazy danych otwarc oraz bardzo mocnego algorytmu zwanego threat-space search analysis. Posiada on ponadto funkcje oceniajaca pozycje w przypadku nie znalezienia sekwencji wygrywajacej pierwsza metoda. Rowniez z tego co wiem, Istvan Virag napisal program potrafiacy znajdowac sure win, ale nie jestem tego pewny. kashon - 2005-04-28, 21:31 na stronie gomoku.pl znajdziesz w dziale renlib biblioteki z opracowanymi wygranymi (sure wins) dla 2 otwarc - d4 oraz i11. kashon jopq - 2005-04-28, 23:55 Sure Win? Jeszcze go nie znasz? www.gomoku.boo.pl/sure_win "majcy" czego Ty się w szkole uczysz, hehe bad_mojo - 2005-04-28, 23:58 Śmieszne, ale właśnie zauważyłem, że Piskv nie widzi całego sw ![:]](images/smiles/krzywy.gif ":]")
Barfko - 2005-04-29, 00:22 Wszystko zależy od tego jak twoja pani od majcy sformułowała zagadnienie. 1. Gdyby to było : "Podaj algorytm wygrywający", wówczas zagadnienie jest banalne. Polega na przeszukaniu całego drzewa gry. Algorytmy przeszukujące drzewa są dość proste. 2. Gdyby to było : "Podaj algorytm wygrywający i udowodnij jego poprawność", wówczas nieco gorzej. Algorytm z pktu 1. wciąż działa. Ale trzeba jeszcze wykazać, że czarne mają SW. Takiego dowodu w sensie ścisłym nie ma, ale jest "dowód komputerowy" polegający na wskazaniu bardzo małego poddrzewa drzewa gry, w którym jest zawarta informacja o SW. Dowód ten jest w pracy, o której wspomniał soul. 3. Gdyby chodziło o podanie algorytmu działającego w rozsądnym czasie, na przykład z ograniczeniem liczby operacji bitowych na ruch (powiedzmy < 10000000000 operacji), wówczas kłopot jest poważny, ale z użyciem istniejącego oprogramowania i istniejących bibliotek RenLibowych jest to wykonalne. W bibliotekach, o których wspomniał kashon, jest zawarta informacja o SW z dokładnością do VCT. Żeby mieć algorytm, wystarczy więc napisać funkcję szukającą VCT (nie jest to trudne) i użyć te biblioteki (plus kilka bibliotek z banalnymi SW, gdy białe grają pierwszy ruch dalej). Wszystkie potrzebne biblioteki to jakieś kilka tysięcy ruchów. 4. Gdyby chodziło o podanie algorytmu, o którym mowa w 3. wraz z dowodem jego poprawności, wówczas należy wręczyć pani od majcy pracę doktorską, o której wspomniał soul. Zaletą ostatniego rozwiązania jest mała złożoność czasowa algorytmu (dużo mniejsza od poszukiwania VCT z pkt. 3), za to złożoność pamięciowa byłaby kilkadziesiąt razy większa niż w pkcie 3 - trzeba by było zapamiątać około 300000 ruchów. Wystarczy więc teraz poprosić panią od majcy, żeby zagadnienie sformułowała na piśmie i mieć nadzieję, że chodzi rozwiązanie z pktu 1., lub z punktu 2. W takim wypadku wystarczy kilka linijek tekstu do wykazania następującego twierdzenia: Tw1. Jeśli czarne mają SW, to algorytm przeszukujący całe drzewo gry jest dobry. To twierdzenie wzmocnione wynikiem Allisa Tw2. Czarne mają SW. daje twierdzenie Tw 3. Algorytm przeszukujący całe drzewo gry znajduje SW czarnych. Oczywiście, gdyby pani od majcy chciała sobie na kurniku rank nabić, to dowód powyższy w tym jej nie pomoże. Hehe. ermijo - 2005-05-07, 19:11 Hmm... bardzo dziwna nauczycielka matematyki, a może to była informatyka lub logika ? Moja teoria na temat SW czarnych w grze gomoku typu standard, jest może trochę "since fiction" , ale uważam, że jeśli chodzi o planszę 15x15, teoretycznie paria zawsze jest remisem. Zawsze można, koncentrując się na grze, nastawić się na remis, co częto stosują tzw. blokersi w grze na 1 min. Zgodziłbym się, że instnieje "pozorne SW" czarnych dla nieskończonego czasu i nieskończonej planszy. Myślę, że z czasem zmierzającym do nieskończoności, czarne zyskują przewagę stopniopwo ( nie wiem wegdług jakiej funkcji, może wykładniczej) , ale nigdy nie wygrają. Wracajac do gry standard - przeprowadzałem analizy. Symulowałem gry nastepującymi programami: w roli czarnych - CARBON Gomoku, w roli białych FIVER. Programy miały ustawiony najlepszy poziom gry. Okazało się, że rzeczywiście większość partii wygrywały czarne, ale zwykle było to po 40 - 50 ruchach. Można by było przeprowadzić badanie, - sprawdzić zależność ilości ruchów kończących grę od rozmiaru planszy. Wiadomo, że w polu 7x7 ze zrobieniem remisu nie będzie miał problemu nawet człowiek. A przy nieskończonej mocy obliczeniowej ?  Myślę że nawet pole 10000000x10000000 by nie wystarczyło na wygraną czarnych.
Ponieważ gomoku to gra ograniczona wymiarem planszy i jakimś czasem, gra standard dla graczy idealnych (teoria) prowadziłąby do remisu przy rosnącej przewadz czarnych. Zatem jak dla mnie to w teorii SW , praktyce zawsze remis a w ludzkich umiejętnościach zawsze wygrana czarnych dla "niemałej planszy". angst - 2005-05-07, 19:32 Przy optymalnej grze w wersji standard czarne maja oczywista wygrana nawet przy optymalnej obronie bialych. I plansza 15x15 spokojnie wystarczy. Zostalo to udowodnione jakies 25 lat temu i pewnie juz wspomniano o tym w ktoryms z powyzszych postow. Pozdrawiam Angst P.S. Akurat grac Carbonem czarnymi to nie byl zbyt dobry pomysl, bo spokojnie mozna go ograc bialymi (no moze nie az tak spokojnie dla przecietnego gracza  ).
nc - 2005-05-07, 19:38 Ermijo, zamiast teorii proponuję praktykę, pograj sobie na kurniku, standard jak dojdziesz (bez nabijania) np. do reda to uznam to za dowód Twojej teorii 
a tak serio to proszę:
ermijo - 2005-05-07, 19:49 Bardzo chętnie zapoznam sie z tym dowodem, może Cię złapię na kurniku kiedyś --- Pozdawiam bad_mojo - 2005-05-07, 21:23 Nie wiem o czym jest tu rozmowa, bo to jest udowodnione, że czarne mają sw w standardzie, i to nawet w renju, gdzie czarnym jest dużo gorzej... jopq - 2005-05-08, 14:44 Bez dwóch zdań czarne mają wygraną w wersji standard. Nie wiem tylko co ma do tego czas i czy moc obliczeniowa go skraca? Bo przecież przy nieskończonej mocy obliczeniowej wymaganay czas dąży do 0. Czas sobie leci... Nie można brać go jako parametru przy stwierdzaniu suchych faktów, które skoro były do udowodnienia wiele lat temu, to dziś przy dużo lepszych możliwościach obliczeniowych naszych komputerów powinny być o oczywiste i łatwe do ponownego przeliczenia (problem pozostaje w dobrze zooptymalizowanym algorytmie). 15x15 spokojnie wystarcza, nawet ostatnio grałem z kilkoma graczami na standard i nie byłem w stanie zablokować jednego z podstawowych wyjść. Warto zobaczyć na otwarcia renju, gdyż te które mają oznaczenia sw, to w gomoku bedza one duzo prostsze do opanowania, a wrecz calkowitego rozpracowania. PS dowód jest w necie, google... pozdrawiam, jopq Ece - 2005-05-08, 18:22
To poprosze o rozpracowanie D13 i I13 dla Gomoku - SW dla bialych w Renju
jopq - 2005-05-09, 21:11 Mając na myśli sw w gomoku, udowadniające wygraną dla koloru czarnego, nie można brać pod uwagę D13 i I13, które wykorzystują faule. Myśl przewodnia jest taka, że jeśli czarne wygrywają z białymi w renju, to w gomoku tym bardziej. W przypadku białych sytuacja jest zupełnie inna, bo wsw w renju moze nic nie znaczyć, a nawet okazać sie bsw. Pozdrawiam zukole - 2014-10-30, 00:13
|
