Forum.Gomoku.pl

[angst]

[ermijo]

[bad_mojo]

[ermijo]

[bad_mojo]

Roku-moku, jeżeli czegoś nie przekręciłem, to gra do sześciu, nie pamiętam jak otwarcie wygląda, ale dalej gra się stawiając dwa kamienie w jednym ruchu. Był swego czasu link na forum do serwera, gdzie można było w to pograć.

[ermijo]

7.) Człowiek kontra komputer

Prostota zasad gomoku sprawia, że regóły tej gry można zaimplementować na maszynie liczącej. Problem, który niewątpliwie pojawia się w tym zagadnieniu dotyczy w głównej mierze optymalizacji algorytmu, którego zadaniem jest rozwiązanie zadanego układu wejściowego na planszy. Złożoność obliczeniowa mająca charakter wykładniczy, w praktyce narzuca programiście rezygnację z zachłannych algorytmów na rzecz efektywnej minimalizacji wskaźnika jakości, jakim będzie tutaj czas.

Czas jako miara szybkości rozwiązywania oraz wykonywania ruchów, stanowi podstawowy parametr, który należy uwypuklić badając zmagania człowieka ze sztuczną inteligencją.

Zarówno zdolności ludzkiego umysłu jak i możliwości mocy obliczeniowych komputerów mają swoje zalety oraz niestety wady. Mózg człowieka, złożony z milionów neuronów potrafi wykonywać szereg operacji paralelnie, a jest to możliwe dzięki licznym sprzężeniom zwrotnym połączeń komórek nerwowych(jeśli by chcieć zbudować uproszczony model mózgu jako sieci neuronowej, musielibyśmy rozważyć różnioczkowe równanie macierzowe o wielomilionowym wymiarze; niestety rozwiązanie takiego równania nie jest i nie będzie możliwie nawet jeśli przybliży się je rozwiazaniem iteracyjnym).


Struktura standardowych komputerów osobistych uniemożliwia praktyczne zrównoleglenie przetwarzania sporej ilości danych nawet, jeśli będziemy mieć dodatkowe pary procesorów. Trudno powiedzieć, ile procesów niezależnych jest wymagane do efektywnej implementacji algorytmu gomoku. Na pewno nie mniej niż ilość możliwych zagrożeń (dwójki, trójki, czwórki, VCT, VCF) oraz innych zestawień funkcji(np. podział planszy na strefy) razem wziętych. Imitacja obliczeń równoległych na maszynie z jednym procesorem jest wysoce nieskuteczna w zestawieniu z sprzętową realizacją algorytmów.

Bardzo wydajne sa układy elektroniczne FPGA nastawione głównie na wykonywanie operacji równoległych dzięki tysiącom bramek logicznych zatopionych w krzemowej płycie. Można wówczas stworzyć i zaprogramować ogromną liczbę procesów, które sprzętowo będą się zachowywały jak procesor i wykonywały ściśle określone zadania.(przykładowo - takie operacje jak szybka transormata Fouriera, obróbka obrazu i dźwięku są wielokrotnie wydajniejsze niż przy realizacji tych zadań na "domowym" o uniwersalnej architekturze pececie).

[jopq]

Skoroś taki mądry, to weź napisz program do gomoku, bo rzeczy o których piszesz można wyczytać na onecie, ale nie mają one większej wartości dla czytających - akurat niczym mnie nie zaskoczyłeś, bo takie szczątkowe informacje to ma każdy, kto cokolwiek wie o architekturze komputerów, algorytmach i narzędziach sztucznej inteliegencji. Sieci neuronowe niestety nie sprawdziły się w praktyce, a pisząc takie coś "rozważyć różnioczkowe równanie macierzowe o wielomilionowym wymiarze" popadasz w śmieszność. A co do programowalnych układów logicznych, to może nadają się one do przetwarzania sygnałów w promach kosmicznych, ale nie ma takiego cwaniaka, co by napisał na nich program do gomoku - z resztą pewnie ciężko by było nawet do 3x3.

"regóła" pisze się przez "u". Nie ma też takiego słowa jak "paralelnie", a powinno być równolegle.

Oczywiście też nie napisałem nic wartościowego, ale podkreślam jeszcze raz, że takie bujanie w obłokach, prezentowanie zlepeka informacji, czy pisanie samemu do siebie nie ma przyszłości. Jeżeli tak dobrze się na tym wszystkim znasz, to niech coś z tego będzie, bo pisanie jakichś opowiadań...

[Muchal]

[jopq]

Skoro już mówimy o statystykach, to takie zapytanie dla wtajemniczonych: czy macie gry z kurnika ze wszystkich miesięcy, bo ja już gdzieś od roku nie ściągam?

[dusksky]

Zostawcie Ermisia w spokoju skoro lubi robic to co robi to niech to czyni nadal. I tak wole poczytac wywody na temat jakiegos tam opena niz przeslodkie posty o IRP itp.
Sam swego czasu chcialem naklepac programik, cos na wzor "raportu z bazy danych" dla danego opena cos nawet napisalem , wlasciwie to ciezko nazwac programem bo to tylko wielka sucha baza w MS SQL z openami dobrych graczy gdzie przy pomocy mniej lub bardziej wyrafinowanych zapytan mozna wyciagac dosc ciekawe wnioski.

[Ece]

A tak właśnie jakoś przy okazji. To ile gdzieś jest otwarć w Gomoku? Teoretycznie to kamienie można ułożyć na 225*224*223 sposobów, ale bez sensu jest traktować zamianę 1 i 3 ruchu jako inne otwarcie, tak samo jak otwarcia symetryczne. Nie wiem czy dobrze, ale jak pisałem w SB, mi wyszło (225*224*223-56)/8 + 56/4 = 1.404.907 otwarć.

Teraz kolejna fajna zabawa, ile z tych otwarć można wywalić jako praktycznie bezużyteczne?

[ermijo]

Potraktujmy chwilowo otwarcie swap jako ciąg 3 wyrazowy. Każdy wyraz tego ciągu może być jednym elementem ze zbioru o mocy (wielkość zbioru)15*15, bo tyle jest miejsc na planszy.
Ponadto w ciągu tym, żaden wyraz nie może się powtarzać (nie mogą do niego należeć przynajmniej jeden taki sam element w/w zbioru). Wynika z tego, że ilość takich 3-wyrazowych ciągów ze zbioru15*15 elementowego bez powtórzeń (w skrajnych przypadkach ciągi będą sie różniły kolejnością, eliminacją tego zajmę się później) można obliczyć ze wzoru kombinatorycznego na wariację bez powtórzeń V(3,225).

Wynosi ona wówczas:11239200. Ta duża liczba ulegnie zmniejszeniu nie więcej niż 16-krotnemu przez zastosowanie ograniczeń:

1.) Ponieważ w otwarciu mamy 2 kamienie czarne, których kolejność względem siebie(zamiana pozycji) w niczym nie zmienia otwarcia, dlatego zmniejszamy liczbę wszystkich otwarć 2 razy i już mamy : 5619600.

Teraz trochę o symetrii otwarć. Może być symetria względem środka oraz symetria względem środka symetrii planszy(przekątne oraz linie h1-h15 i a9-p9).

2.) Symetria otwarcia względem środka (h8) powoduje, że można ułożyć tylko 4 różne otwarcia np. open Zakona H8 - F5 - K10(pod warunkiem że nie jest on jednocześnie symetryczny względem jednej z osi symetrii).

3.) Symetria otwarcia względem jednej z osi symetrii planszy np. open Zakona ustawiony jako H8 - K10 - M12, powoduje identyczny skutek - tylko 4 sekwencje(przy podobnym założeniu jak wyżej).

4.) Symetria względem środka i osi symetrii np. h7-h8-h9 powoduje, że można ustawić jedynie 2 sekwencje.

W pozostałych przypadkach możliwe jest ułożenie 8 różnych sekwencji z jednego otwarcia.

Liczbę 5619600 należy podzielić przez odpowiednią liczbę wynikającą z dublowania się otwarć przez symetrie. Należy się jeszcze zastanowić ile jest symetrycznych otwarć względem środka a ile względem osi symetrii ? Obliczymy wtedy ile jest otwarć niesymetrycznych i dla każdej grupy, podzielimy ją kolejno ad.2 i ad.2 przez 4, ad.3 przez 2 oraz ad.4 przez 8.

Sumując ilorazy otrzymamy ilość wszystkich możliwych otwarć gomoku na planszy 15x15.

C.D.N. (nie mam czasu) , ale z mojego szacunku wynika, że otwarć jest nie więcej niż 702450(szacunkowo wydaje mi się, że symetrycznych jest nie więcej niż 2000 tyś. wiec liczba o rząd się nie zmieni).

[Ece]

Ja pier*** Ermijo. Następnym razem przeczytaj to co napisałeś zanim to wyślesz. Sprawdź formatowanie (usunąłem puste linijki). Poza tym, poza pierwszym punktem, każdemu kolejnemu brakuje sensu, konsekwencji, albo zawiera błędy rzeczowe. Na dodatek nic z tego postu nie wynika.

[templar]

Ja spróbowałem zliczyć to trochę inaczej.

Zacząłem od ilości możliwych ustawień pierwszego kamienia - jest ich 57 (warto to przemyśleć ). Potem przemnożyłem to przez 224*223. Podzielić teraz przez 2 nie można (bo pierwszy kamień wpada tylko w jedną ćwiartkę) i tu już zaczęły się schody, choć przebrnąłem przez to (to, tzn. odrzucanie otwarć powstających przez dublowanie się czarnych kamieni). Dalej zacząłem rozważać liczbę w ten sposób wygenerowanych podwójnych otwarć (tzn. otwarć symetrycznych do siebie tylko względem przekątnej - poczwórnych jest niewiele, licząc moim sposobem, więc to pominąłem) i od pierwszego wyniku odjąłem właśnie tę liczbę (bo te otwarcia są liczone podwójnie). Tutaj trochę miałem problemów, ale bez wnikania w szczegółowe obliczenia (które są makabryczne - musicie mi uwierzyć na słowo )wyszło mi, że różnych otwarć jest co najwyżej 1.100.000 (delikatnie zaokrąglając w górę). Wiem - szału nie robi, ale zawsze to 300.000 mniej otwarć niż w wyniku Ece.

Tę liczbę na pewno można jeszcze zmniejszyć, ale podejrzewam, że już nie dużo - nie sądzę, żeby można było zejść aż do 700.000 jak pisze Ermijo (zwłaszcza, że źle tam zliczał te otwarcia), chociaż kto wie - gubię się w takich skomplikowanych rachunkach .

A co do bezużytecznych otwarć, to co masz na myśli Ece?

Pozdrawiam
templar

PS. Kombinatoryka to raczej nie jest moja mocna strona, więc całkiem możliwe, że gdzieś się pomyliłem.
PS2. Pierwotnie wyszło mi 900.000, ale znalazłem błąd w obliczeniach.

[Ece]

Templar, zobacz jak ja to policzyłem i może spróbuj do tego się odnieść. Odpaliłem wszystkie możliwości, podzieliłem przez 4 jako symetrie w każdej z ćwiartek kwadratu i przez 2 jako zamienniki 1 i 3 ruchu. Ale z tego co ja zauważyłem, jest 56 otwarć, gdzie symetrie w ramach ćwiartek i zamiana 1 i 3 ruchu się pokrywają. Np. G8-H8-I8 to symetria I8-H8-G8, a zarazem zamiana 1 i 3 ruchu. Takie przypadki pierw usuwam z puli którą dzielę przez 8, a następnie dodaję to 56, ale podzielone przez 4.

Bezużyteczne otwarcie to dla mnie np. A1-H8-O15, A2-A1-B1. Może inni mają bardziej konstruktywne propozycje?