formularz a "szachy", jak tego dokonać? Opcje

[dutagamo]

Witam
Zaczynam się uczyć tego języka i zastanawia mnie pewna sprawa:
Poprzez formularz chciałbym aby wywołało mi tablicę podobną do szachów i na danym polu umieścić punkt lub cokolwiek innego. i zasada jego działania chciałbym aby była podobna do skoczka w szachach. By pokazało miejsca na które on może skoczyć.
Jak to zrobić?

[ayeo]

Witam!

Tabela (szachownica) to tylko sposób prezentacji danych. Zanim zaczniesz ją generować musisz ustalić statusy dla pól. Szachownica w Twoim systemie to tablica ( 8x8 ). Stawiasz skoczka na pierwszym polu

[PHP] pobierz, plaintext 
$array[1][1] = 1; // 1 - obecna pozycja skoczka
[PHP] pobierz, plaintext 

Teraz wystarczy zmienić wartości 8 innych pól. Tyle jest (w idealnym przypadku) możliwości przesunięcia skoczka (ale normalnie większość wypadnie poza szachownicą).

[PHP] pobierz, plaintext 
$x = 1; $y = 1; //pozycja skoczka
 
$array[x+2][y + 1] = 2; // 2 - pole gdzie mogę skoczyć
$array[x+2][y - 1] = 2;
 
$array[x-2][y + 1] = 2;
$array[x-2][y - 1] = 2;
 
$array[x+1][y + 2] = 2;
$array[x+1][y - 2] = 2;
 
$array[x-1][y + 2] = 2;
$array[x-1][y - 2] = 2;
[PHP] pobierz, plaintext 

Oczywiście powinieneś sprawdzać czy dane pole na szachownicy istnieje i czy jest wolne itd, ale to taki zarys idei. Z taką tablica bez problemu narysujesz stosowną tabelkę (2 pętelki).

[PHP] pobierz, plaintext 
<table>
 
foreach( $array as $row )
{
 <tr>
  foreach( $row as $one )
  { 
   <td>
    if( $one == 1 ) tu stoi skoczek;
    if( $one == 2 ) tu może skoczyć;
   </td>
  }
 <tr>
}
 
</table>
[PHP] pobierz, plaintext 

Taki pseudo kod, formatowanie do dupy, ale pisałem to bezpośrednio na forum (tab nie działa tak jakbym chciał).



Pozdrawiam!

[thek]

Wyślę, że wygodniejsza byłaby notacja liczbowa Definiujemy nie tyle możliwe do użycia pola, ale możliwe ruchy. Każdy ruch pionka to tak naprawdę przesunięcie z pola x na y, co jest równoznaczne z dodaniem lub odjęciem pewnej liczby od obecnie zajmowanej. To najlepsza metoda, co wiem z doświadczenia bo pisałem algorytm mający znaleźć ścieżkę przez wszystkie pola szachownicy skoczkiem (koniem). Taki sposób prezentacji pozwala łatwo określić czy znajduje się on na, czy poza szachownicą w danym ruchu. Interpretujesz planszę jako pole nie 8x8 ale 12x12. Numerujesz więc pola rzędami, rząd 1 - od 1 do 12, rząd 2 - od 13 do 24 itd... (możesz liczyć od zera jak w tablicach). To daje Ci dwa rzędy zapasu z każdej strony, a sama plansza główna to pola 27-34, 39-46, 51-58, czyli od 27+n*12 do 34+n*12 (n z zakresu 0-7). Teraz zdefiniuj ruchy konia. Masz 8 możliwości. Weź przykładowo, że stoisz na polu 78 i popatrz na jakie pola możesz stanąć. To pozwoli Ci określić jakie liczby możesz dodać lub odjąć od aktualnej pozycji by uzyskać określony ruch. Podpowiem, że mogą to być pola 53 i 55, a więc (x-25) i (x-23). Znajdź jeszcze pozostałe 6 sam Skoro masz już je to nie problem sprawdzić czy po operacji dodania lub odjęcia skoczek jest na polu planszy czy na dodatkowych polach (nadmiarowe obrzeże). Teraz jedynie musisz jeszcze sprawdzić, czy gdy jesteś na planszy po dodaniu liczby, jest ono zajęte przez inną figurę. Ja w ten sposób kombinacją liczb 1-3-6-7.... itd. zapisałem przejście przez wszystkie możliwe pola szachownicy, gdzie liczby od 1 do 8 definiowały mi ruch konia, czyli dodawania i odejmowania. Jaki tego plus? Daje Ci to łatwy sposób notacji za pomocą tablicy jedno-, a nie dwuwymiarowej. W ten sposób można szybko napisać algorytm szukający ścieżki przejścia z jednokrotnym stawianiem na każdym z pól. Uwierz, że większość algorytmów iteracyjnych ma z tym problemy, gdyż wszelkie algorytmy optymalizacyjne są jednymi z najtrudniejszych do zaprogramowania i nieraz zdarzają się tutaj próby wprowadzania sztucznej inteligencji. Ja w swoim projekcie używałem algorytmów genetycznych i potrafiłem w ciągu maksymalnie 5-10 sekund znaleźć prawidłowe rozwiązanie. Zaznaczam, że jest pewna pułapka. Istnieje pole na szachownicy (bodajże c3 lub c4), dla którego zwykłe algorytmy iteracyjne nie potrafią znaleźć rozwiązania problemu skoczka. Pokazano nam typowe i uruchomiono przed feriami zimowymi. Po powrocie z ferii one nadal szukały A to już było ze 2 tygodnie

EDIT: Gwoli ścisłości wyjaśnię dlaczego plansza jest 12x12 a nie 8x8... W sytuacji gdyby była 8x8 operacje "poruszania się" powodowały by "rolowanie się" planszy. Czyli skok z pola na obrzeżu jednym, który normalnie wyszedł by poza planszę sprawiłby pojawienie się piona na przeciwległej krawędzi. Stąd nadmiarowe pola po bokach, które zawsze "złapią" wyjście skoczka poza planszę gry.

Dlatego moja podpowiedzią dla Ciebie jest.... Nie definiuj pól jako takich ale zakoduj ruch i samą szachownicę w sposób przeze mnie opisany lub podobny. A sposób graficznego rzutowania danych (w postaci tablicy jednowymiarowej) na płaszczyznę to już banał w porównaniu do algorytmu i można to na wiele sposobów rozwiązać.

Ten post edytował thek 19.10.2009, 14:46:44

[ayeo]

Witam!

Nie zgłębiałem nigdy tematu (napisałem podobny program, tj szukanie drogi dla skoczka, x lat temu w Turbo Pascalu, ale były to algorytmy czysto rekurencyjne). Rozwiązanie, które podajesz wcale nie wydaje mi się najlepsze. Może są jakieś zalety jeżeli chodzi o optymalizację. Normalnie jednak szachownica jest dwuwymiarowa i tyle samo wymiarowa powinna być tablica, która ją reprezentuje - jest to bardziej intuicyjne. Co do sposobów implementacji to oczywiście nie chodzi o to, zeby dodawać i odejmować coś bezpośrednio w kodzie. Każda klasa figury powinna mieć tablicę możliwych ruchów i jedna prosta  metoda może zwracać tabelę pól. Jednak to detal.

Pozdrawiam!

[thek]

To może wyjaśnię dlaczego takie podejście zastosowałem. Algorytm genetyczny polega na wybraniu dwóch osobników, "złamaniu" ich w tym samym miejscu (lub kilku miejscach) i wymiana pomiędzy nimi odpowiednich fragmentów. Na starcie losowo więc wypełniamy cały 64-polowy chromosom liczbami od 1 do 8 co tworzy "ścieżkę przejścia". Zastosowanie "kodowania polami" sprawiłoby, że na złamaniu po wymianie genomu w dużym stopniu skok byłby niemożliwy do wykonania wedle zasad. Zakodowanie ruchami sprawia, że dla algorytmu nieistotna jest pozycja końcowa ruchu, ale sam ruch, czyli po wymianie materiału ścieżka jest możliwa do prześledzenia. Może być lepsza, może być gorsza, ale na pewno możliwa do sprawdzenia. Po etapie wymiany materiału genetycznego może nastąpić mutacja (z pewnym prawdopodobieństwem), czyli niekontrolowana zmiana jakiejś pozycji w chromosomie. To przy kodowaniu ruchami też nie jest problemem Najważniejsza z punktu algorytmu część następuje teraz: funkcja oceny. To ona wyznacza najlepsze osobniki. Przy ruchu skoczka oceni ona ile pól przeszedł według zasad. Gdy to się zakończy cały proces jako kolejna epoka następuje od początku. Czyli wybranie najlepszych parami i krzyżowanie, mutacja, ocena. Trwa do albo do padu kompa, albo przy dobrze dobranych parametrach skończy się szybciutko i znajdzie w końcu osobnika, który przeszedł wszystkie pola jednokrotnie. Jego chromosom to właśnie droga z rozwiązaniem Z prac doszedłem do wniosku, że powinno być wiele takich chromosomów (około 10-15k) i przy łamaniu w jednym miejscu najlepiej gdy prawdopodobieństwo mutacji jest w miarę wysokie, bo bez tego szybko dochodzi do sytuacji, że większość chromosomów waha się między 56-62 polami i dopiero mutacje coś zmieniają na plus.

Jako bonus dodam, że jest dział AI, który nazywa się "programowanie genetyczne" i działa na identycznej zasadzie Problemem algorytmów genetycznych jest ścisłe dopasowanie do problemu i nie są one uniwersalne niestety.

A wracając do zakodowania tablicy jako dwuwymiarowej, to uważam to za przerost formy nad treścią. To dokładnie to samo co jednowymiarowa z indeksami modulo 8 Ruch piona to tylko dodanie lub odjęcie konkretnej wartości (bicie to odchyłka jej o +/-1). Tak naprawdę więc całość jest jedynie zbiorem operacji dodawania i odejmowania oraz sprawdzania pól na których można stanąć po tych operacjach. Kombinowanie z manipulacją dwoma indeksami tablicy jednocześnie (tak jest nawet w ruchu wieżą, tyle że jednemu z nich nakazujesz +0) jest IMHO niepotrzebne, skoro mozna je zredukować do prostszej postaci.

Ostatecznie uważam, że tak naprawdę zależy to od tego, czemu ma służyć rozwiązanie problemu. Może się okazać, że Twoje podejście będzie w określonym przypadku skuteczniejsze, ale dla problemu skoczka, uwierz, że algorytmy bez specjalnych modyfikacji potrafią utknąć na wspomnianym przypadku. Znajdą drogę przez 63 pola i dalej będą liczyły bez efektu. Można nawet próbować tak modyfikować algorytm, by obliczał on sam pewne parametry na podstawie zdefiniowanej wielkości planszy. Ale może nie rozgrzebujmy problemu skoczka szachowego, bo to pewnie nie z nim się mierzy autor. Ale jesli tak, to myślę, że w necie znajdzie nie tylko podpowiedzi, ale gotowy kod, jeśli tylko pogrzebie pod "knight tour" w google

Gdy zaś mowa o szachach jako całości to można już przemyśleć wariant dwuwymiarowy, bo kilka problemów on rozwiązuje w przystępniejszy sposób, ale tylko dla kogoś kto ma problem z "widzeniem" ruchu przy zwykłym dodawaniu i odejmowaniu. Dla reszty użycie jedno- lub dwuwymiarowej formie to tylko inna notacja i nic więcej. Jak już wspomniałem, zwykłe modulo 8 z 1-wymiarowej robi 2-wymiarową, a mnożenie wiersza razy 8 i dodawanie drugiego indeksu zrobi działanie odwrotne. To tylko notacja i nic więcej

Ten post edytował thek 19.10.2009, 23:52:12

[dutagamo]

hehe to może ja się wetknę do tej dyskusji i skonkretyzuję co chcę zrobić

Chcę aby z poziomu formularza wpisany został numer pola na którym potem pojawi się "skoczek" i pokażą się na tej szachownicy również miejsca zaznaczone w dowolny sposób do których może się ruszyć... i chodzi mi tylko o jego jeden ruch na dowolnie przeze mnie wybranym polu.

Tylko o takie coś proszę nie zagłębiajcie się w tematykę alogrytmów genetycznych hehe bo takie coś mam teraz na studiach z matmy i nie jest to wcale takie łatwe nawet jak dla mnie

[thek]

Sposobów na to masz wiele... Zrobić tablicę 2-wymiarową i sparsujesz literę w formularzu na indeks, a liczbę z formularza zmniejszysz o 1 i w ten sposób uzyskasz współrzędne start. Sparsować całość z formularza na indeks 1-wymiarowej tablicy. Zrobić na starcie nie formularz ale obrazek gdzie klikasz pokazując to miejsce, a wybór między 1- a 2-wymiarowym zapisem startu masz dowolny. Jak widzisz to niektóre z propozycji na określenie pola startowego.
Co do ruchów możliwych to znów zależy od notacji szachownicy. Jeśli masz tylko 1 ruch pokazać, to 2-wymiarowa jest lepszym rozwiązaniem, bo prościej pokazać możliwe pola na ruch. Wystarczy wybrać wszystkie kombinacje indeksów tablicowych z zakresu: (+/-3, +/-1) oraz (+/-1, +/-3), gdzie wyniki muszą być w przedziale (0,7).
Przykład:
Na początek sprecyzujmy, że litery to kolumny od lewej do prawej, a wiersze to liczby od dołu do góry rosnące, czyli punkt (0, 0) to lewy dolny róg (taki jest zapis szachowy i tego się trzymam).
Pole: B5 to start, co daje nam w macierzy pole o współrzędnych (1,4)
Możliwości:
+3,-1 -> (4, 3)
+3,+1 -> (4, 5)
-3,-1 -> (-2, 3)
-3, +1 -> (-2, 5)
+1,-3 -> (2, 1)
+1,+3 -> (2, 7)
-1,-3 -> (0, 1)
-1,+3 -> (0, 7)
Teraz eliminujemy wszystkie mające choć jedną współrzędną spoza zakresu <0,7>
Wylatują więc propozycja 3 i 4, a pozostałe są w zakresie.
Pozostaje Ci już tylko zwizualizować wynik. Sądzę, że najprościej poprzez zrobienie DIV z szachownicą jako background i wobec niego pozycjonować obrazki majace pokazywać obrazek skoczka oraz możliwych jego posunięć. Jak? Temu DIV nadaj position:relative a wewnątrz niego pozycjonuj img z obrazkami To chyba najprostsze rozwiązanie jakie można tu wymyślić

EDIT: Bym zapomniał... Pozycjonowanie na stronie masz zawsze od lewego górnego rogu, a nie lewego dolnego jak w szachach, więc musisz wyniki nieco skonwertować, ale to już banał i powinieneś sobie poradzić.

A poza tym mój pomysł to jedna z wielu możliwych wersji rozwiązania tego problemu, jak sam możesz przeczytać. Więc nie musisz go tak implementować jak napisałem, ale zrobić po swojemu.

Ten post edytował thek 20.10.2009, 21:50:43

[ayeo]

@dutagamo, to co chcesz zrobić jest opisane w moim pierwszym poście.

@thek, twierdzisz, że algorytm rekurencyjny (przy rozsądnej ilości pól) jest w stanie "utknąć"? Są problemy przy optymalizacji. Może się zdarzyć, że dwa pola zostaną puste (bez możliwości wskoczenia na nie) na zasadzie wzajemnej adoracji. Jednak jest to ewidentny błąd programisty. Sam algorytm (w najprostszej postaci- jedna funkcja) zawsze znajdzie rozwiązanie (o ile takie istnieje), kwestia czasu (niestety).

Co do algorytmów genetycznych to strasznie zainteresowało mnie Twoje rozwiązanie problemu. Troszkę się tym (w wonym czasie) pobawię Tak więc: dzięki

Pozdrawiam!

[thek]

@ayeo: tak. Są sytuacje, że algorytmy utykają, także genetyczne. U mnie testem było właśnie znalezienie rozwiązania dla startu z pola c3 lub c4 na standardowej 64-polowej szachownicy, ale nie pamiętam już którego dokładnie, bo robiłem jakieś 4-5 lat temu ów algorytm. Pewnie w necie by się znalazło jakie to dokładnie Napisz jak Ci się podoba samo programowanie genetyczne jako podejście i gdy napiszesz kod - jak Twoim zdaniem sprawuje. I nie ma za co dziękować. Człowiek poznaje ciekawostki całe życie. Ta zaś ciekawostka mnie zainteresowała od razu bo daje naprawdę fajne możliwości przy szukaniu rozwiązań optymalizacyjnych. Jest pewną odskocznią od typowego programowania w standardowy sposób. Zresztą większość AI taka jest. Robisz coś od kompletnie innej strony i... działa. Zresztą poczytaj o tym jak się tworzy sieci neuronowe, to zdziwisz jak prosta matma tam jest Trochę mnożenia, dodawania i dzielenia A w efekcie możesz napisać OCR.

Tak dodatkowo dodam, że akurat w algorytmach genetycznych wcale nie ma przymusu znalezienia dokładnego rozwiązania. Jako algorytmy stosowane w optymalizacji podają one najczęściej wyniki "oszacowane" i wiele zależy od parametrów wejściowych algorytmu. Stąd właśnie sugerowałem do problemu skoczka większą ilośc osobników i duży % zaistnienia mutacji. Bez tego ów algorytm byłby długotrwały i nie podawałby rozwiązań w ciągu kilku sekund.

EDIT: Warunkiem stop jest zazwyczaj funkcja oceny. Można by ją ustawić nie na liczbę 64, ale 62 lub 63. Nie da to rozwiązania całkowitego, ale jak wspomniałem, genetyczny algorytm nie ma obowiązku szukać rozwiązań ostatecznych. To programista wskazuje w funkcji oceny o jaką dokładność mu chodzi Stąd też optymalizacja jest głównym polem do popisu dla tej części sztucznej inteligencji.

A co do samych algorytmów genetycznych, to uważam to za jeden z najciekawszych działów sztucznej inteligencji. To, IMHO, znacznie fajniejsze niż sieci neuronowe czy logika rozmyta, choć sieci rozmyto-neuronowe mają tę ciekawostkę, że dobrze zaprogramowane nawet całkiem dobrze działają. Mogę tylko dodać, że miałem okazję być uczony przez specjalistów polskich w tej dziedzinie i może dlatego złapałem więcej wiedzy o funkcjonowaniu AI, a spośród tego algorytmy genetyczne uznałem za najbardziej interesujące.

Ten post edytował thek 21.10.2009, 08:30:22

[ayeo]

Witam!

Samo zagadnienie SSN (rozpoznawanie kodów pocztowych ) jest mi znane. Algorytmy genetyczne same w sobie też kojarzę (proste, abstrakcyjne przykłady) jednak nie zdawałem sobie sprawy, że można tego użyć do tak matematycznego zagadnienia jak szachy (knight tour). Co do rekurencji to zawsze znajdzie rozwiązanie jeśli takie istnieje bo (było nie było) sprawdzi każdą możliwość  (co trudno nazwać rozwiązaniem problemu ). Dzięki jak najbardziej się należy bo nie doceniałem algorytmów genetycznych chyba, traktowałem to raczej jako ciekawostkę. Widziałem masę programów, które wykorzystują to w praktyce (malowanie Mona Lisy), ale dla codziennych zastosowań trudno mi było do wcisnąć. Teraz widzę, że nawet problem stricte matematyczny (sorry za wyrażenie, ale wiesz o co chodzi) można rozwiązać w taki sposób. Tak więc jeszcze raz: DZIĘKI!

Pozdrawiam i życzę miłego dnia!