Koncept - niedyskretna teoria gier

[Noqa]

Przede wszystkim to nie bardzo wiedziałem, gdzie umieścić ten wątek. Nic o teorii gier nie znalazłem, dyskretna nie pasuje z definicji. Ew. może geometria, choć nie do końca.

Wrzuciłem to już na innym forum (niematematycznym), więc forma może być czasem niejasna.
Z góry przepraszam, za wszelkie źle użyte nazwy i ew. błędy w rozumowaniu.

Chodzi o coś, co można chyba nazwać niedyskretną teorią gier.
Załóżmy, że na pewnej powierzchni/przestrzeni znajdują się punktowe kot i pies. Pies goni kota, przy czym oba mają określoną prędkość, pochodne ich położeń od czasu są stałe.

Oba zwierzęta zachowują się bezbłędnie, tj. wybierają najlepszy rodzaj ruchu, bazując na tym, co wiedzą o ruchu drugiego gracza.
Pies dąży do zbliżenia do kota, kot stara się tego uniknąć.
"Nie zostanie złapany" oczywiście definiuje się jako "położenia kota i psa, nigdy nie będą takie same".

Oczywiście nie jest jasne czy w ogóle możemy mówić, o tym, że gracze podejmują najlepsze możliwe decyzje - tu potrzebny byłby jakiś dowód.
A zagadnienia mogą być trywialne (np. "czy K (kot) nie zostanie złapany, jeśli on i P (pies) znajdują się na nieskończonej powierzchni, a ich początkowe położenia nie są równe" albo "czy K uniknie złapania jeśli znajduje się na płaszczyźnie ograniczonej w jednym wymiarze (X) obustronnie, a w drugim jednostronnie (Y), przy czym K i P są w tym samym położeniu w wymiarze X, a K bliżej ograniczonej strony Y" - chyba ściśle, choć może niejasno. Chodzi o takie molo z początkiem, ale bez końca, a K jest bliżej początku), bardziej skomplikowane, choć raczej dotyczącego podstawowych dowodów, jak np. "czy K uniknie złapania na figurze(chyba nie można tego nazwać płaszczyzną?) o skończonej powierzchni? (Położenia K i P początkowo różne)", aż do tych ciekawszych - najlepsze jakie udało mi się wymyślić to sytuacja, gdzie K i P znajdują się na ograniczonej ze wszystkich stron powierzchni, a na środku znajduje się wycięte koło (gdzie P i K oczywiście nie mogą się znaleźć). Dla jakich położeń K i P, przy jakich rozmiarach koła K zostanie złapany?
Można to łatwo rozwiązać, problemem jest raczej formalny dowód. Ale myślę, że można wymyślić bardziej ambitne problemy.

Oczywiście można to zagadnienie rozszerzać wprowadzając więcej wymiarów, więcej psów lub kotów czy też istoty o innych celach (np. układ pies-kot-mysz, który powinien już wymagać większego umysłowego wysiłku). Jeszcze bardziej skomplikowałoby wprowadzenie dodatkowych wymogów, np. P i K wpływają tylko na drugą różniczkę położenia, tj. przyspieszenie, a więc podlegają bezwładności. Wtedy chyba byłoby to już połączenie teorii gier z rachunkiem różniczkowym.

W teorii gier mamy zwykle skończoną liczbę możliwości. Tutaj w każdej nieskończenie małej chwili mamy nieskończenie wiele różnych możliwości (wektorów ruchu). Dlatego zagadnienie jest ciągle, niedyskretne.
Tylko zastanawia mnie, czy w ogóle może istnieć najlepszy wybór, gdy ilość decyzji w jednostce czasu rośnie do nieskończoności, a zatem czy zagadnienie w ogóle ma sens w takiej formie.

Co wy na to? Ciekawe? I kto to już dawno przede mną wymyślił?

[Noqa]

Co do gier nieskończonych - no tu jest trochę podobnie, tylko, że tu możliwości ruchu jest nieskończenie wiele, ruchy są przy tym nieskończenie małe i jest ich (w jednostce czasu) nieskończenie wiele. Trochę jak różniczki.
W pewnym sensie nie można tu ponumerować punktów, bo pomiędzy dwa dowolne można wcisnąć zawsze jeszcze jeden.

czy dla każdej liczby naturalnej n musi być \(\displaystyle{ |p(n+1)-p(n)|=|k(n+1)-k(n)|}\)?

Tak. Właściwie prędkości nie muszą być stałe, wystarczy, że są równe (na jedno wychodzi)

Pytasz o to czy istnieje strategia wygrywająca dla \(\displaystyle{ p}\) taka, że \(\displaystyle{ p(m)=k(m)}\) dla pewnej liczby naturalnej \(\displaystyle{ m}\)? Moim zdaniem, nie ale możnaby lekko zmodyfikować założenia gry, aby taka szansa była.

Nie do końca. To co opisuje to tylko założenia, na których można zbudować różne pytania zależne od ilości P i K, a przede wszystkim od kształtu \(\displaystyle{ \Omega}\)

Choć teraz boję się, że brakuje tu pewnych założeń, które likwidowały, by sytuację, w której K może uciec, mimo, że odległość dąży do 0 (może samo złapania trzeba by tak zdefiniować, jako \(\displaystyle{ p(n) \rightarrow k(n)}\) dla \(\displaystyle{ n \rightarrow \infty}\)

[Zordon]

Ciekawe zagadnienie, w tej chwili nie mam zbytnio czasu żeby się nad tym głębiej zastanowić, dlatego zostawie tylko komentarz do powyższego: jeśli będziemy rozważać ciągi położeń to już problem staje się bardziej "dyskretny", czego autor tematu (takie przynajmniej mam wrażenie) chce uniknąć...

[Noqa]

Zordon, zgadza się. Niestety nie bardzo potrafię ściśle, matematycznie zdefiniować tego, co mam na myśli i mam nadzieje, że ktoś mi pomoże

[Noqa]

Temat bardzo stary, ale udało mi się w internecie znaleźć to, o co mi chodziło.

Praktycznie identyczne zagadnienie jest znane jako , a należy do kategorii gier różniczkowych (oryginalnie differential game).
Tylko tutaj problem jest bardziej ufizyczniony, bierze pod uwagę bezwładność.

Wrzucam tak na wypadek, gdyby ktoś kiedyś trafił na ten temat.

[xiikzodz]

Można ten problem rozważyć przy założeniu, że pies i kot skaczą po punktach kratowych. Odległość pomiędzy sąsiednimi punktami kratowymi oznaczamy \(\displaystyle{ \varepsilon}\). Następnie przechodzimy do granicy \(\displaystyle{ \varepsilon\to 0}\). Teoria homogenizacji daje kryteria, przy których takie przejście do granicy jest sensowne. Często tak mniej więcej podchodzi sie do równań różniczkowych cząstkowych.

[Inkwizytor]

Jeżeli prędkość psa jest większa, niż kota to pies zawsze złapie kota.
1. Dwa punkty sa współliniowe: Kot ucieka wzdłuż prostej (oddala się się od psa), pies porusza się wzdłuż tej samej prostej goniąc kota. Skoro ma większą prędkość to z elementarnej fizyki da się nawet obliczyć kiedy.

2. Kot zmienia tor poruszania się. Algorytm prymitywny:
a) Zapisujemy położenie początkowe psa i kota.
b) Pies biegnie do zapamiętanego położenia kota. Gdzie kot biegnie nieistotne.
c) W momencie gdy pies osiągnie stare położenie kota, sprawdza gdzie teraz jest kot (nowe położenie jest na pewno w mniejszej odległości od psa) i idź do punktu b)

Oczywiście jeżeli rozbijamy problem na liczbę kroków to otrzymamy "paradoks Achillesa i żółwia", a z drugiej strony czy aby nie zrobi się z tego problem dyskretny? No i nie jest to rozwiązanie optymalne

3. Modyfikacja pomysłu 2.
a) Zapisujemy położenie psa i kota.
b) Rysujemy okrąg o środku w położeniu psa i promieniu równym odległości psa od kota.
c) Ponieważ prędkość psa musi byc większa od kota to kot porusza się wew. tego okręgu w każdym momencie (zakładamy że pies cały czas się porusza i "ma ciąg na kota" ) zatem po momencie \(\displaystyle{ \Delta t}\) wróć do pkt. a)

Problemem jest to "próbkowanie" położenia. Nakłada to na nas określenie częstotliwości próbkowania \(\displaystyle{ \Delta t}\). Ale czy wówczas znowu nie zrobi się aby problem dyskretny? Trzeba by sprowadzić problem do \(\displaystyle{ \Delta t \rightarrow 0}\) co też poniekąd idealizuje tę życiową sytuację (brak opóźnień w reakcji na ruch przeciwnika )

[Noqa]

Inkwizytorze - w moim zamyśle wygląda to trochę inaczej

Pies i kot mają te same prędkości, pies wygrywa jeśli zbliży się kota na odległość e (e może dążyć do zera) w skończonym czasie.
W pustej 2-wymiarowej przestrzeni P nigdy nie dogoni K.
Ale sytuacja zmienia się, jeśli zmienimy obszar, po którym mogą się poruszać. Jeśli zamiast nieskończonej przestrzeni, będzie np. prostokąt, to domyślam się, że K przegra - P zawsze zapędzi go w róg.
Jeszcze inna "plansza" - znowu mamy przestrzeń ograniczoną prostokątem, ale teraz wycinamy ze środka koło. Okazuje się, że są położenia początkowe, dzięki którym K może wygrać (jeśli K i P są na brzegu koła, wtedy dla obu najlepszym ruchem jest ruch po okręgu. Zresztą chyba da się udowodnić, że P nie wygra, jeśli K jest na okręgu. Próbowałem geometrycznie, ale nie wyszło)

[Inkwizytor]

Ale sytuacja zmienia się, jeśli zmienimy obszar, po którym mogą się poruszać. Jeśli zamiast nieskończonej przestrzeni, będzie np. prostokąt, to domyślam się, że K przegra - P zawsze zapędzi go w róg.

W pełni się zgadzam i to że pies zapędzi do narożnika kota jest oczywiste Można by tu nawet rozważyć kwestię, typu pies ma mniejszą prędkośc od kota, ale że kot "strachliwy" to nie moze poruszać się po prostej dłuzej niz.... albo pies moze poruszać sie po prostej 2x, 3x... dłużej od kota. To wymuszałoby na kocie poruszanie sie po łamanej, po łuku. Jednak podejrzewam że złożoność tego problemu znacznie wrasta.

Jeszcze inna "plansza" - znowu mamy przestrzeń ograniczoną prostokątem, ale teraz wycinamy ze środka koło. Okazuje się, że są położenia początkowe, dzięki którym K może wygrać (jeśli K i P są na brzegu koła, wtedy dla obu najlepszym ruchem jest ruch po okręgu. Zresztą chyba da się udowodnić, że P nie wygra, jeśli K jest na okręgu. Próbowałem geometrycznie, ale nie wyszło)

Tu moglibysmy zaobserwować pewien paradoks z założeniem. Jezeli zakładamy że zwierzęta cały czas sie poruszają, to da się ustawić sytuację, w której optymalnym rozwiązaniem dla kota byłoby tkwienie w miejscu przez pewien czas.
1. Prostokąt o rozmiarach dużo wiekszych, niż wydrążony okrąg. Kot na początku stoi na okręgu.
2. Pies współliniowo z kotem i środkiem okręgu ale po przeciwnej stronie tego okręgu, w dodatku w odległości od okręgu przewyższającej połowę obwodu (to ważne).
3. Pies biegnie po prostej w stronę kota (i okręgu).
4. Kot musi się poruszać i ucieka od psa po tej samej prostej (optymalnie utrzymuje swoja odległość od psa)
5. Pies po dobiegnięciu do okręgu (kot w tym czasie oddalił się od okręgu na odległość większą niż połowa okręgu), zaczyna się biec po łuku.
6. Kot nie da rady wrócic na okrąg i po pewnym czasie zostanie na "czystej ograniczonej przestrzeni" oko w oko z psem.
7. A gdyby kot czekał na okręgu, aż pies dobiegnie do tego okręgu z drugiej strony, to nigdy by nie został złapany

[Noqa]

Tu moglibysmy zaobserwować pewien paradoks z założeniem.

Ale założeniem jest takie działanie, aby uniknąć złapania - czyli w opisanej sytuacji będzie nim bezruch, dlatego jest to gra
A jeśli już wymuszamy ruch to zawsze możemy mówić o mikroskopijnych ruchach wte i wewte - tak by stać w miejscu.

Za to zaprezentowana sytuacja ładnie pokazuje, jak bardzo błędna może być prosta strategia dla K "utrzymuj jak największa odległość"

[Inkwizytor]

Możliwość nieporuszania się przez zwierzęta (lub np. tylko przez kota) strasznie komplikuje całą sytuację, bo wzrasta stopien złożoności takiego rozwiązania. Nie wiem czy da się utworzyć jeden uniwersalny algorytm czy należałoby tworzyć dla każdej sytuacji inny? Już samo stworzenie algorytmu, który bedzie miał bardziej złożone kryterium optymalizacyjne niż "zachowaj możliwie dużą odległość" wydaje się trudne.

Nawet gdyby zwierzęta nie mogły zatrzymywać się to oczywiście istnieje rozwiązanie:
W czasie dobiegania psa do okręgu, kot musiałby w przebyć jakiś cykl, łamaną lub odcinek "w tą i z powrotem" tak by powrócić na okrąg w momencie, gdy pies dobiegnie do okręgu (lub nawet bedzie "przez chwilę" już poruszał sie po nim). Sęk w tym że ciężko wprowadzić takie kryterium uniwersalne by kot nie próbował optymalizować odległości od psa Można by tu powiedzieć, że w chwili pogoni zwierzęta działają instynktownie więc cięzko posądzać je o "sprytną strategię"