Pytanie:
Kiedy ruchy są losowe, czy istnieje nieodłączna przewaga dla gracza, który idzie pierwszy, czy gracza, który idzie drugi?
Galen
2020-04-23 19:40:35 UTC
view on stackexchange narkive permalink

Wyobraź sobie, że stawiamy przeciwko sobie dwóch automatycznych graczy (botów), ale zamiast przemyślanych ruchów wykonywanych przez graczy, dokonują oni całkowicie przypadkowych wyborów. Zdaję sobie sprawę, że tak naprawdę nie o to chodzi w grze w szachy, ale to daje podstawy do teoretycznego pytania o szachy.

Czy gracz, który idzie pierwszy, ma nieodłączną przewagę? idzie na drugie miejsce?

„Nieodłączna przewaga” oznacza tutaj, że prawdopodobieństwo wygranej jednego gracza jest wyższe niż drugiego i że te losowe warunki nie uwzględniają tego, jak graliby prawdziwi gracze. Jeśli taka przewaga istnieje, może zostać całkowicie zniszczona przez sposób, w jaki ludzie grają ze sobą w szachy. Chcę podkreślić, że to pytanie nie ma na celu uogólnienia na grę ludzką lub algorytmiczną.

Aktualizacja

Dzięki niewielkiej korekcie odzyskałem wyniki 1000000 losowo rozegranych gier do kodu itub. Przygotowałem podstawowy wykres, aby pokazać wyniki.

enter image description here

Ale jeśli wolisz konkretne liczby, oto wydruk:

  Counter ({'is_insufficient_material': 474230, 'can_claim_fifty_moves': 169123, 'can_claim_threefold_repetition': 149398, '1-0': 75868, '0-1': 75239, 'is_stalemate': 56142})  

Zgodnie z obietnicą w komentarzach do jednej z odpowiedzi, zamierzałem obliczyć przedział punktacji Wilsona z korektą ciągłości. Napisałem następującą funkcję w Pythonie, aby to osiągnąć.

  import numpy as npfrom scipy import statsdef wilson_cont (n1, n2, alpha = 0,05): '' 'Interwał punktacji Wilsona z korektą ciągłości. Zakłada się przedział dwustronny. Parametry: n1 (int): Liczba wyników 1. n2 (int): Liczba wyników 2. alpha (float): Źródło: https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval '' 'typ asercji (n1) == int i type (n2) == int assert 0 < alpha < 1 z = stats.norm.ppf (1 - alpha / 2) n = n1 + n2
phat = n1 / n num1 = 2 * n * phat + z ** 2 num2 = z * np.sqrt (z ** 2 - 1 / n + 4 * n * phat * (1 - phat) + 4 * phat - 2) + 1 num3 = z * np.sqrt (z ** 2 + 1 / n + 4 * n * phat * (1 - phat) - 4 * phat - 2) + 1 denom = 2 * (n + z * * 2) return max (0, (num1 - num2) / denom), min (1, (num1 + num3) / denom)  

I wywołanie tej funkcji na wyniku liczy się, gdzie albo biała lub czarna wygrana, mamy:

  >>> print (wilson_cont (75868, 75239)) (0.4995569815292355, 0.5046054923932771)  

poniższe uwagi i odpowiedzi nie różnią się znacząco od 50%. Jak wskazał MaxW w swojej odpowiedzi, podobne obliczenia przeprowadzono na jeszcze większej próbie, która wykazała, że ​​ istniała różnica istotna statystycznie. Jedną z obaw związanych z tymi wszystkimi obliczeniami, moimi i innymi, jest to, że stają się one bardziej wrażliwe na odchylenia, gdy wielkość próbki staje się większa. Oznacza to, że trudno jest określić, czy naprawdę istnieje różnica przy użyciu standardowego testowania hipotezy zerowej, gdy wielkość naszej próby staje się wyjątkowo duża, ale jeśli nie próbujemy wystarczająco dużo, nasza próbka nie będzie wystarczająco reprezentatywna. To, co mi to wyjaśniło, to forma warunkowego rozumowania, że ​​ jeśli jest różnica, to jest ona niezwykle mała pod względem wielkości efektu .

Dziękuję wszystkim, którzy wykazali zainteresowanie tym postem i wnieśli swój wkład w jego rozumowanie, badania lub kod.

„Nieznacznie różne” oznacza tylko, że próbka nie jest wystarczająco duża, a nie faktyczna różnica
@David Tak, zgadza się. Jak stwierdziłem powyżej, albo nie ma różnicy, albo jest to niewielka różnica. Możemy bezpiecznie wykluczyć dużą różnicę.
Pewnie! Właśnie wyjaśniałem ludziom, którzy mogliby się w tej sprawie zagubić
Trzy odpowiedzi:
#1
+23
itub
2020-04-23 21:16:41 UTC
view on stackexchange narkive permalink

Kiedyś napisałem program do wykonywania losowych ruchów, kazałem mu rozegrać 1000 gier i takie były moje wyniki:

  Outcome Count Avg. #moves ----------------------------- ----- ----------- Remis przez niewystarczające materiał 500 179 Losowanie pięćdziesięcioma ruchami 157 208 Losowanie trzykrotnym powtórzeniem 147 164 Czarny wygrywa matem 75 87 Biały wygrywa matem 72 78 Ciągnięcie pata 49 138  

Próbka jest zbyt mała, aby dojść do ostatecznego wniosku, ale jak widać, czarne wygrywały więcej gier niż białe! (Myślę, że to tylko szczęście). Bardziej zauważalne jest jednak to, że przytłaczająca większość gier to remisy.

Moje przeczucie jest takie, że ani białe, ani czarne nie mają żadnej przewagi podczas wykonywania losowych ruchów. Często przytaczana przewaga białych w pierwszym ruchu opiera się na założeniu, że białe mają inicjatywę, ale bardzo łatwo jest stracić inicjatywę, a jeśli wykonasz losowe posunięcia, masz gwarancję, że bardzo szybko ją stracisz. (Edycja: dzięki odpowiedzi MaxW, cieszę się, że ktoś faktycznie przeszedł przez problem symulacji miliardów gier i stwierdził, że w rzeczywistości białe mają bardzo niewielką, ale statystycznie istotną przewagę: 7,7340% vs 7,7293%).

Pierwotnie zamieściłem powyższą tabelę jako odpowiedź na inne pytanie: Ze wszystkich możliwych legalnych partii szachowych, ile z nich kończy się wygraną białych, remisem i wygraną czarnych ( zakładając regułę 50 ruchów)? Ta odpowiedź zawiera więcej spekulacji na temat tego, dlaczego większość gier kończy się remisami, ale co ważniejsze, zawiera kod źródłowy Pythona na wypadek, gdybyś mógł uruchomić własne symulacje.

Biorąc pod uwagę, że istnieje zwycięzca, prawdopodobieństwo wygranej czarnych wynosi około 51% w Twoich danych. Obliczenie [normalnego przedziału aproksymacji] (https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval) ($ n = 147 $, $ z = 1,96 $) dla tej podprzestrzeni sugeruje prawdopodobieństwo wygranej czarnych (zakładając, że ktoś wygrywa) wynosi od 43% do 59%, co jest zgodne z 50%.
Dziękuję za link do kodu źródłowego. Używam go do podsumowania miliona gier, co na moim procesorze zajmie kilka dni. Zamierzam obliczyć przedział punktacji Wilsona z korektą ciągłości, aby ponownie ocenić istotność.
Z twojej odpowiedzi już wyciągnąłem, że nawet jeśli istnieje efekt, może on mieć * bardzo * mały rozmiar efektu.
Ktoś powiedział, że pierwszy ruch daje szansę popełnienia pierwszego błędu. Ma sens, że przy przypadkowych ruchach białe stracą więcej.
@MikeJones Możesz popełnić pierwszy błąd, ale przeciwnik musi to wykorzystać, co w przypadku gry losowej jest mało prawdopodobne. Na początku pomyślałem, że białe powinny mieć niewielką przewagę, ponieważ jeśli wykonasz pierwszy ruch, możesz matować jako pierwszy (a większość matów byłaby na wczesnym etapie gry, gdy na planszy jest dużo pionów). Z drugiej strony, w przypadku najkrótszego mata (mat głupca) matuje czarny. To powinno mieć prawdopodobieństwo mniej więcej jednego na milion w losowej grze (4 półruchy).
@user1583209: mówi, że obie strony mają średnio 20 pierwszych ruchów i 25 sekund, co daje około 250 tysięcy czterech gier w połowie ruchu, z których cztery są matem głupców (istnieje wybór między f3 i f4 oraz między e6 i e5). Więc mniej więcej jeden na 60 000. Myślę, że fakt, że czarne mogą matować wcześniej, może wystarczyć, aby dać mu niewielką, malutką przewagę, ale losowe zagranie powinno zniweczyć prawie wszystko. Jestem zdumiony, że jedna ze stron wygrywa równie często jak oni.
Ale link w odpowiedzi MaxW pokazuje, że mimo wszystko jest biały.
Nie ma koncepcji „inicjatywy” dla prawdziwie przypadkowych ruchów. Jeśli białe grożą zajęciem hetmana czarnych w następnym ruchu, czarne zignorują zagrożenie, a jeśli białych jest dostępnych 50 legalnych ruchów, istnieje 98% szans, że białe i tak nie wezmą hetmana w następnym ruchu.
W swoich symulacjach widziałem kilku głupich kumpli (po obu stronach), ale są one rzadkie, powiedziałbym, że nie więcej niż 1/1000. Zauważ, że średnio gry, które kończą się mate, są dość długie: około 80 pełnych ruchów! Nawet jeśli głupcy koledzy będą preferować jeden kolor, i tak zgubią się w hałasie.
@alephzero W rzeczywistości symulacja MaxW pokazuje, że może nawet wystąpić efekt „odwrotnej inicjatywy”. Jeśli białe rzucają czarne do szachowania, czarne muszą wykonać merytorycznie „użyteczne” posunięcie, które ma większą niż przeciętną szansę na zbicie atakującej figury. Sprawdzając kolor czarny, biały naraża się na większe ryzyko straty materialnej, co zmniejsza prawdopodobieństwo przyszłych matów. Białe mają tę przewagę, że wcześnie matują, ale wczesne czeki są w rzeczywistości obciążeniem. Jednak późniejsza odpowiedzialność nie równoważy wczesnej przewagi.
Nie dziwię się, że 50 ruchów kopie w foten - ale trzykrotne powtórzenie jest mniej więcej równie często?
@HagenvonEitzen, ciekawe pytanie. Ponieważ powtarzające się pozycje mogą być oddalone od siebie o wiele ruchów, być może są to gry, w których poruszają się tylko królowie, a niektóre pionki są zablokowane, aby zapobiec remisowi z powodu niewystarczającej ilości materiału. Może wystarczająco dużo takich gier jest w stanie natknąć się na potrójne powtórzenie, zanim dojdzie do 50 ruchów. Pewnego dnia przyjrzę się konkretnym przykładom, aby zobaczyć, jak wyglądają powtórzenia ...
Tutaj jest świetna dyskusja! Nadal czekam na zakończenie obliczeń. Kod zbadał 609500 partii szachowych, więc dociera do celu.
#2
+21
MaxW
2020-04-24 09:14:05 UTC
view on stackexchange narkive permalink

Kiedy ruchy są losowe, czy istnieje nieodłączna przewaga gracza, który idzie pierwszy, czy gracz, który idzie drugi?

Pierwszy gracz ma niewielką przewagę. Kiedy czarne wykonały n ruchów, białe wykonały n + 1 podczas kończenia swojej tury. Nawet jeśli czarne mogą matować w swoim n + 1 -tym ruchu, czarne nadal przegrywają.


EDYTUJ Moja analiza była zbyt prosta, ale miałem szczęście.

Ponad 29,28 miliarda losowych partii szachowych białych jest nieco bardziej skłonnych do matowania niż czarnych (7,7340% vs 7,7293%).

Oznacza to, że jeśli mecz kończy się matem, białe wygrywają 50,015% z nich, a czarne 49,985%.

Zobacz: https://wismuth.com/ chess / random-games.html

Kiedy ruchy są wybierane losowo, nie jest dla mnie oczywiste, że w rzeczywistości jest to jakakolwiek przewaga białych.
@ChrisH - Wiedziałem, że ktoś musiał to zrobić. Zobacz https://wismuth.com/chess/random-games.html Ponad 29,28 miliarda losowych partii szachowych jest nieco bardziej prawdopodobne, że białe szachy będą matować niż czarne (7,7340% vs 7,7293%),
@MaxW, że link i statystyki z niego odpowiadają na pytanie, należy do Twojej odpowiedzi.
@ChrisH Jeśli każdy losowy ruch ma pewne szanse na wygraną, to spodziewałbym się, że białe będą miały niewielką przewagę, ponieważ średnio częściej rzucają kośćmi niż czarne.
#3
+1
Laska
2020-04-26 10:42:46 UTC
view on stackexchange narkive permalink

Powyższe odpowiedzi są świetne, ale mogę dodać jedną kwestię, która właśnie mi przyszła do głowy.

Analiza statystyczna sugeruje niewielką przewagę białych w losowych szachach. Ale każda pozycja godowa może być "odwrócona" (figury White<-> czarne, osoba do przeniesienia zmieniona i odwrócona plansza góra<-> dół), aby zająć legalną pozycję z matowaniem drugiej strony. Innymi słowy, nie ma przypadków, w których parzystość obecna na pozycji startowej może być zachowana aż do mata.

Innymi słowy: w ogromie szachów są dokładnie taka sama liczba pozycji matowych dla białych jak dla czarnych. Jest to więc trochę paradoksalne, że więcej gier losowych wygrywa białe. Myślę, że odpowiedź jest taka, że ​​odwrócenie parzystości wymaga podążania jakąś stosunkowo mało prawdopodobną ścieżką ruchów (np. 1.c3 d5 2.c4, aby zasymulować 1.d4 c5).

Nie jestem pewien, czy istnieje pełna parzystość, ponieważ pozycja jest określana nie tylko przez bierki na szachownicy, ale także przez: ** którego ruch jest **, ** roszada **, ** en passant rights ** , ** trzykrotne powtórzenie i 50 (75) ruchów **.
Jeśli weźmiesz najkrótszego mata, mat głupca, który wymaga 4 pół-ruchów w przypadku czarnych matów lub 5 pół-ruchów w przypadku białych matów. Dodatkowy ruch w połowie, który wykonują białe, może w rzeczywistości przeszkadzać mu w możliwości matowania w pół ruchu 5. Jeśli spojrzysz na dane, tak właśnie się dzieje, w krótkich grach czarne mają przewagę, ale w dłuższych grach jest biały, który dogania.
Dzięki user1583209: Wyjaśniłem teraz, że osoba może przesuwać koziołki. Zmieniają się prawa do roszady i prawa przelotowe. „Trzykrotne / pięciokrotne powtórzenie pozycji” z definicji oznacza, że ​​liczba nie jest częścią pozycji. Jednak każdą osiągalną pozycję można osiągnąć bez jej powtarzania. Podobnie, liczba ruchów 50/75 nie jest czynnikiem pozycji, w przeciwnym razie nigdy nie mógłbyś powtórzyć pozycji!
Na pytanie głupca tak, zgadzam się @user1583209. To ciekawe zjawisko - myślę, że dla * bardzo * długich gier Wh wygrywa i Bl wygrywa zbiegają się. Czy widzisz to?
Do Laski: To nie są moje dane, po prostu je czytam. Domyślam się, że w bardzo długich grach zbliżamy się do 100% remisu, więc tak, w pewnym sensie wygrane w & b zbiegają się do 0.
Chociaż każdą pozycję można odwrócić, osiągnięcie jej może wymagać innej liczby ruchów, a zatem mieć inne prawdopodobieństwo.
Tak - alternatywną miarą jest to, że każda gra się liczy 1. W ten sposób nie przeważamy krótkich gier. Zasada 50 ruchów z pewnością byłaby jednak czynnikiem i trudno ją zdyskontować. Myślę, że mój pierwotny punkt widzenia jest nadal aktualny, chociaż paradoks nie jest trudny do przejrzenia


To pytanie i odpowiedź zostało automatycznie przetłumaczone z języka angielskiego.Oryginalna treść jest dostępna na stackexchange, za co dziękujemy za licencję cc by-sa 4.0, w ramach której jest rozpowszechniana.
Loading...