Heurystyki w stochastyczno–statystycznym modelu gry w brydża Andrzej Matuszewski, Instytut Podstaw Informatyki PAN

1 VI 2007

Po ciężkiej pracy nad edyktem "Constitutio Antoniniana" (nadającym w roku 964 A.U.C.

STRESZCZENIE:

Wprowadzono probabilistyczne kryterium optymalizacji gry w brydża. Dotyczy ono jednego rozdania na jednym stole, ale uwzględnia ono rozegranie tego rozdania na innych stołach. W przeciwieństwie do już istniejących, proponowane kryterium dotyczy wszystkich faz rozdania – chociaż tu zajmiemy się głównie rozgrywką i jej niejaką konsekwencją: wistem (obroną). Przedyskutowano związek tego kryterium z bardziej konstruktywnymi metodami, które równocześnie dają się matematycznie i/lub algorytmicznie sformalizować, a zatem mogą być potraktowane jako heurystyki dotyczącymi generalnego kryterium. Zdefiniowano 3 heurystyki: dwie probabilistyczne i jedną deterministyczną. Sformułowano niektóre zadania do rozwiązania.

SŁOWA KLUCZOWE:

Wartość oczekiwana, symulacja Monte Carlo, strategia rozgrywającego, algorytmy, optymalizacja.

1 WSTĘP

Pojedyncze rozdanie jest podstawową cegiełką gry w brydża. W niniejszej pracy przedstawimy model przebiegu rozdania. Przebieg ów jak i każdy pojedynczy ruch (który nie jest jednak pod wszystkimi względami: „atomem”…) wykonywany w rozdaniu mają charakter stochastyczny. W pewnym sensie przymiotnik ten można „przetłumaczyć” jako: losowy (nie jest właściwym przymiotnik: statystyczny – o czym dalej). Jednak owa losowość posiada swoją nieubłaganą logikę. Jest to logika w 90–ciu procentach wynikająca z reguł gry w brydża. Reguły te – choć są proste – określają grę, która jest bardzo trudna i wieloaspektowa. Wykażemy, iż owa wieloaspektowość wynika m. in. z częściowo sprzecznych heurystyk, których nie da się uniknąć zarówno „ludzkiemu’ jak i „komputerowemu” graczowi. Pomimo sprzeczności owe heurystyki powinny być w przyszłości pomocne w uczeniu się tradycyjnym i informatycznym.

Przedstawimy stochastyczne kryterium optymalizacyjne, na które można spojrzeć z dwóch punktów widzenia. Z jednej strony pretenduje ono do roli ostatecznego wzoru rangującego możliwe ruchy, które są do wykonania w danym momencie przez gracza. Z drugiej strony – ze względu na bardzo ogólną formę kryterium – nie można na ogół podać efektywnego algorytmu wyliczenia numerycznej wartości wzoru, a zatem z pewnością wyznaczyć optymalny ruch. Stąd owe heurystyki.

Oprócz reguł i „bezosobowej” logiki postępowania (wystarczającej dla ułożenia programu komputerowego grającego w brydża) istnieje jeszcze praktyka gry na różnych poziomach wtajemniczenia. W poniższych rozważaniach modelujemy w pewnym stopniu również i ową praktykę. Ze względu na konieczność formalizacji procesu modelowania rozpatrzono tylko trzy podstawowe (postawmy znak zapytania przy tym przymiotniku) strategie postępowania najtrudniejszych problemów gracza i tylko w (nieco) uproszczony sposób.

2 DEFINICJE

Nie sposób w krótkim paragrafie zaprezentować wszystkich pojęć niezbędnych dla zrozumienia dalszego ciągu. Zamiast je definiować, lepiej byłoby odesłać słabo obeznanego z brydżem Czytelnika by ze 2 lata pograł sobie towarzysko, sportowo, w Internecie i z dobrym programem komputerowym. Spróbujmy jednak zestawić sobie pewne rzeczy podstawowe dotyczące brydża:

2.1 Pojęcia wstępne – oczywiste dla grających w brydża

Optymalizację gry trzeba podzielić, przynajmniej z punktu widzenia poszukiwania algorytmu postępowania graczy (w tym grającego programu komputerowego) na 3 zasadnicze sytuacje. Dotyczą one jednego rozdania rozgrywanego na jednym stole.

1. Licytacja – dotyczy wszystkich czterech graczy. Ponieważ gra się w parze, trzeba przede wszystkim uwzględnić system licytacyjny danej pary. W pewnym stopniu należy brać również pod uwagę system licytacyjny przeciwników – w czym pomocne są (na pewnym poziomie zaawansowania) karty konwencyjne. W fazie tej istnieją problemy probabilistyczne, ale omówienie ich odłożymy do innej publikacji.

2. Rozgrywka

3. Obrona. Tutaj oprócz optymalizacji gry własnej trzeba przekazywać i odbierać sygnały partnera (zrzutki konwencyjne).

Ściśle rzecz biorąc istnieje jeszcze jedna pozycja nie mieszcząca się w tym podziale, a mianowicie sytuacja gracza mającego oddać pierwszy wist. Dla uproszczenia tą sytuację w tych rozważaniach pominiemy.

2.2 Ustalenia dodatkowe – oczywiste dla grających w „brydża zaawansowanego” lub sportowego

1. Istnieją różne rodzaje zapisu dotyczące pojedynczego rozdania. W pewnym stopniu wpływają one na wszystkie 3 wymienione wyżej sytuacje gracza. W dalszym ciągu posłużymy się głównie skrótowymi określeniami: zapis na IMPy i zapis na maxy, bo te symboliczne skróty myślowe wystarczą do przedstawienia istoty tych rozważań. Z dalszych rozważań będzie wynikać, jak ważny dla optymalizacji (doskonalenia) gry w brydża jest właśnie sposób zapisu wyniku rozdania. Wieloletnie dyskusje jakie się toczą w wielu środowiskach brydżowych na ten temat mają zatem swoje głębokie uzasadnienie.

2. Można wprowadzić pojęcia strategii i taktyki gry – pojęcia te częściowo zdefiniujemy kontekstowo poniżej. Dotyczą one m.in. rodzaju zapisu, w którym toczą się rozgrywki.

3. To samo rozdanie może być rozgrywane na drugim stole (mecz) lub na wielu stołach (turniej). Jest to związane z ustaleniem 1. Chodzi o to, by system zapisu był bardziej sprawiedliwy, cokolwiek by to miało znaczyć!

4. Elementarnym matematycznie i algorytmicznie (lecz nie w pełni uświadamianym jako taki przez wielu graczy o różnym poziomie zaawansowania) jest pojedynczy ruch w licytacji i w rozgrywce/obronie.

5. Ruch niekoniecznie jest elementarną jednostką psychologicznie. W sytuacjach decyzyjnych bądź o znaczeniu taktycznym z pewnością nie jest elementarny – mówimy o grze ludzi nie automatów… Często jeden ruch decyduje o wyniku rozdania (czyli o wszystkim!), szczególnie wtedy gdy może być interpretowany przez pozostałych graczy na różne sposoby. W takich sytuacjach strategia sprowadza się do odpowiedniego przygotowania tego właśnie ruchu. Literatura brydżowa jest uboga w opracowania psychologiczne (temat arcy–trudny) – chociaż ostatnio jest pewne ożywienie w tym zakresie. Prawdopodobnie w tym elemencie najsilniej wychodzi na jaw słabość graczy–automatów.

Prawdopodobnie wymienione cechy brydża „zaawansowanego” to tylko formalny i bardzo ogólny aspekt zmagań na wysokim poziomie. Właściwie, wymienione powyżej cechy charakteryzują jeszcze inne gry karciane, bądź nawet szerzej: strategiczne. Na szczęście matematyzacja (bardzo trudna) brydża jest przecież czymś istotnym motywowana. W następnym paragrafie przedstawimy właśnie różne dodatkowe elementy motywacyjne i odkryjemy tym samym dodatkowe ważne aspekty brydża kwalifikowanego.

3 DODATKOWA MOTYWACJA

Oprócz chęci uzyskania pewnego postępu zarówno w teorii przeznaczonej dla graczy jak i dla programistów urządzeń grających w brydża, celem niniejszej publikacji jest rzucenie światła na pewne nietypowe a nawet „niewytłumaczalne” zjawiska występujące w teorii i praktyce brydżowej. Oto niepełna lista tych zjawisk.

3.1 Wskazówki i manewry

Wiadomo, że ograniczeniem automatów grających w szachy jest ilość wariantów, które trzeba wygenerować i ocenić. Z grubsza można tą ilość oszacować jako 1000^k, gdzie k jest tzw. ilością ruchów naprzód. Na dobrym poziomie gry to k musi przekraczać 6! Mamy zatem do czynienia z liczbami „kosmicznymi”.

W brydżu ilość wariantów jest nieporównywalnie mniejsza. Spójrzmy na to z perspektywy gracza „ludzkiego”. Jest absolutnie realistycznym (a nawet przesadnym!) założenie, że w miarę kwalifikowany gracz ma za każdym razem, gdy podejmuje decyzję, średnio dwa możliwe „sensowne” ruchy do wykonania. W rzeczywistości w sporym procencie sytuacji jest tylko jedna karta do dodania lub jedna odzywka do zalicytowania!!

Zatem jakby chcieć przewidywać 6 ruchów do przodu, to mielibyśmy zaledwie 64 warianty do rozpatrzenia. Ten szacunek jest na dodatek na ogół przesadzony.

Mimo tej stosunkowo niewielkiej (no powiedzmy dla człowieka to nie tak mało…) ilości wariantów, które musi rozpatrzyć gracz lub program grający, zdumiewa ogromna ilość wiedzy jaka nie tylko jest potrzebna ale jest wręcz niezbędna do gry nawet na poziomie 10% profesjonalizmu (patrz niżej co przez to rozumiemy).

Np. znany teoretyk i nauczyciel brydża Edwin Kantar sformułował ok. 150 wskazówek (a w ogóle ta liczba w jego publikacjach grubo przekroczyła 500!!), bez znajomości których gra jest wyraźnie słabsza!! Wskazówki te na ogół są bardzo dalekie od oczywistości!!

Oprócz wskazówek każdy gracz musi mieć opanowany pewien arsenał manewrów. Każdy wie co to jest impas, ale innych manewrów jest też około stu. Niestety ich znajomość jest niewystarczająca. Dochodzi do tego, że niektóre manewry nie mają nawet nazwy(!). Mimo to wiadomo, że bez znajomości manewrów, brydż staje się własną karykaturą.

Postawmy się zatem na miejscu nowego adepta brydża, któremu „na dzień dobry” proponuje się nauczenie ze zrozumieniem powiedzmy 80–ciu wskazówek i 40–tu manewrów. Sytuacja absurdalna…

Nic tylko uciekać, a przecież jeszcze trochę się trzeba nauczyć o konwencjach i zwyczajach licytacyjnych. A jest to szczególnie stresujące, bo pomyłki w trakcie licytacji wywołują natychmiastową nieprzyjemną reakcję partnera. A jeszcze dodatkowo trzeba znać chociaż elementy wistu…

Na marginesie dodam, że nawet impas nie jest wcale łatwym manewrem. Wiążą się z nim 2 elementy:

1. Jeśli jakaś znacząca karta znajduje się w ręce, z której wychodzi się do impasu, to należy ją zagrać czy nie? Problem ten jest różny w zależności czy zagrywamy z dziadka czy z zakrytej ręki.

2. Wykonanie impasu zakłada możliwość dojścia do ręki, z której dokonuje się zagrania. Czasami trzeba dwóch lub więcej dojść. To może być problematyczne.

Punkt 2 wskazuje, że w zasadzie każdy manewr posiada kontrmanewr. W przypadku impasu jest to próba niedopuszczenie do zagrania na impas a więc np. atak na komunikację.

3.2„Głębia” intelektualna

Średnio w co drugim rozdaniu mamy autentyczny problem czy wręcz kilka problemów, które sprowadzają owe rozdania do poziomu rozrywki intelektualnej wysokiego lotu. To prawda, że często mijają one niezauważone, ale jest również prawdą, że niektóre rozdania zaprzątają uwagę gracza przez wiele godzin już po skończeniu gry. Często – szczególnie w naszym kraju – jedno rozdanie może doprowadzić do czasowego rozpadu pary. Oczywiście rozdanie takie musi posiadać odpowiednią dla klasy pary głębię intelektualną.

Niektórzy w omawianej „głębi” dopatrują się przyczyny faktu, iż brydż dość często uzależnia (w sensie chorobowym) graczy. Zdarzają się sytuacje, że gracz znacznie więcej spędza czasu na grze niż śpi!! I to może trwać np. miesiąc!

3.3 „Profesjonalizacja”

Istnieje tzw. amatorski poziom gry. Jedną z jego cech zdefiniujemy w rozdziale KLASYFIKACJA ZMIENNYCH Z_i

Inną cechą pary amatorskiej jest używanie tzw. naturalnego systemu licytacyjnego i naturalnego systemu zrzutek w obronie. Do pojęcia „naturalności” jeszcze powrócimy [nie wiem czy w tej pracy].

Rosnące „procenty profesjonalizacji” dotyczą coraz węższej grupy graczy. Wzrost ten w karierze gracza nie jest tylko ilościowy. Często przy przejściu np. z 30% do 70% nawet przy generalnie tym samym systemie licytacyjnym i zrzutkowym, trzeba dokonać swoistej rewolucji ustaleń szczegółowych. A więc procenty profesjonalizmu umożliwiają zaobserwowanie zjawiska przejścia ilości w jakość.

W chwili obecnej brydż stał się pewnego rodzaju przemysłem zatrudniającym w skali światowej kilka tysięcy brydżowych profesjonalistów. Przemysł ten powiązany jest z innymi gałęziami gospodarki takimi jak np. turystyka i wypoczynek.

Procent profesjonalizmu graczy ma znaczenie komercyjne dla teoretyków brydża piszących artykuły, książki i oprogramowanie edukacyjne. Jeżeli opisywana metoda lub system dotyczy wysokiego procentu profesjonalizmu trudno liczyć na dużą ilość nabywców. Dotyczy to także usług szkoleniowych.

Z kolei przy bardzo niskim procencie profesjonalizacji domniemanego audytorium (opracowywanego produktu), trudno liczyć na nabywcę, gdyż gracze tacy bywają często „uodpornieni” na wiedzę.

3.4 Aspekty psychologiczne

W punkcie 2.5 wskazaliśmy na „podzielność” atomu czyli ruchu ze względów psychologicznych. To podstawowe dla gry praktycznej (i naszych rozważań) spostrzeżenie bynajmniej nie wyczerpuje aspektów psychologicznych brydża. Bardzo kontrowersyjne jest blefowanie (głównie w licytacji). Ponieważ istnieje zawsze podejrzenie tzw. blefu „kontrolowanego”, sprawa „obrosła” również ustaleniami z zakresu prawa brydżowego.

Innym motywem psychologicznym są zagrania mylące. Wymagają one na ogół najwyższych kwalifikacji, a zatem są dowodem 100%–wego profesjonalizmu gracza.

Nawet u słabo zaawansowanych graczy daje się zauważyć „styl” zarówno gry jak i analizy parozdaniowej. Co więcej zawodnicy często wykonują zagrania, które można określić mianem kaprysu. Również często w analizie rozdania podkreślana bywa możliwość wykonania tego typu zagrań. Nazywa się to czasami zagraniami intuicyjnymi. Znaczenie „intuicji” jest psychologicznie uzasadnione probabilistycznym charakterem gry.

Styl dotyczy nie tylko pojedynczych graczy ale również całych grup. Np. jest już niepodważalnym faktem istnienie tzw. stylu juniorskiego. Dochodzi do tego, że niektórzy juniorzy podkreślają, że chcą za wszelką cenę uniknąć stylu juniorskiego.

4 GENERALNE KRYTERIUM OPTYMALIZACYJNE

We wszystkich trzech fazach (z tym że rozgrywka i obrona są równoległe) każdy gracz musi wielokrotnie wybrać ruch r optymalizujący następującą podwójną wartość oczekiwaną:

E_Π [ E_Δ(r) [ Z(r);P_r) ]; Dir] → max (1)

Zapis: E_X[X;Q)] oznacza wartość oczekiwaną zmiennej losowej X o wartościach w zbiorze X, mającą rozkład prawdopodobieństwa Q.

Funkcja Z (od Zapis) jest zmienną losową określającą przewidywany wynik rozdania z punktu widzenia gracza wykonującego ruch. Oczywiście dla strony przeciwnej ów wynik jest odwrotny w skali odpowiadającej zapisowi, w którym toczy się gra. Jeśli gra liczona jest w IMP–ach, to, jeśli Z dla linii NS wynosi 2 IMPy to dla WE: –2. Przy zapisie maksowym następuje odjęcie od 100%.

Wewnętrzna wartość oczekiwana zakłada „znajomość” rozkładu prawdopodobieństwa możliwych do uzyskania wyników rozdania. W rzeczywistości owe prawdopodobieństwa są też zmiennymi losowymi. Oczywiście owe zmienne zależą też od danego ruchu r, stąd też nim są indeksowane.

Zewnętrzna wartość oczekiwana „uśrednia” wewnętrzną wartość oczekiwaną, która jest zmienną losową zależną od r – czyli jej rozkład (a w pewnych sytuacjach również zbiór wartości) zależy od r.

Dir oznacza proces Dirichleta, a więc rozkład prawdopodobieństwa na dyskretnych rozkładach wyników możliwych do uzyskania w danym rozdaniu, z użyciem systemu zapisu, w jakim to rozdanie jest grane.

W ostatnich latach teoretycy brydżowi zaczęli określać rozkłady prawdopodobieństwa związane z licytacją, jednak metodologia jest w stadium embrionalnym. Dużo więcej wiadomo o obronie a przede wszystkim rozgrywce w interesującym nas aspekcie probabilistycznym. Dla tego też zaczniemy od tej ostatniej.

Najpierw zatem sprecyzujemy wzór (1) w przypadku gracza realizującego pewien kontrakt. Tą adaptację (1) rozbijemy na 2 etapy.

Osoba grająca (lub program komputerowy) w danym momencie l rozgrywki/obrony winna optymalizować swój ruch z punktu widzenia następującego wzoru:

Kryt ( r ) = Oczekiw₂ (∑ W_i ( r ) Z_i )→ max (2)

i= 0, 1,… 13

tzn. wybieramy ruch r (spośród rozpatrywanych przez gracza g), który maksymalizuje powyższe kryterium. Niech R będzie zbiorem dopuszczalnych ruchów, czyli możliwych do dołożenia kart w danej pozycji.

Istnieje ograniczenie: ∑ W_i ( r ) = 1, dla każdego r є R.

W_i ( r ) ≥ 0 jest prawdopodobieństwem wzięcia przez stronę gracza g ilości: i lew przy założeniu zagrania r. W_i ( r ) odpowiadają prawdopodobieństwom {P_r} ze wzoru (1).

Z_i jest zapisem za wzięcie i lew.

Zarówno współczynniki W jak i Z są – z punktu widzenia gracza podejmującego decyzję w danym momencie oraz dla każdego ruchu r – zmiennymi losowymi. Tylko w dwóch szczególnych przypadkach (opisanych w rozdziale 10) współczynniki Z są stałe.

Elementy wektora losowego W dla danego ruchu są prawdopodobieństwami., zatem argument operatora wartości oczekiwanej: Oczekiw₂ można interpretować jako zmienną losową, która sama jest wartością oczekiwaną. Jest to zgodne z ogólnym kryterium (1), odnoszącym się również do licytacji.

Rozpiszmy (2) dla bardziej konkretnej pozycji rozgrywającego zmniejszając stopień abstrakcji tej formuły o szereg mniej istotnych jej składowych.

Załóżmy, że rozgrywający jest w trzeciej lewie kontraktu 3 pik. Pierwszą lewę wzięli wistujący. Drugą lewę wziął rozgrywający na stole. Zagrał stamtąd w trójkę pik i prawy obrońca już dołożył piątkę. Teraz rozgrywający musi coś dołożyć z ręki. Ma on w tym momencie 5 atutów, powiedzmy: AD942. Zatem zbiór jego ruchów (czyli dołożeń karty) składa się z pięciu elementów.

R = {♠2, ♠4, ♠9, ♠D, ♠A}

Suma występująca w (2) ma w tym momencie nie 14 lecz tylko 11 składników. Rozgrywający weźmie bowiem co najmniej 2 lewy (tę co już wziął i asa atutowego) i nie weźmie więcej niż 12 lew, bo jedną już oddał. Czyli suma jest od 2 do 12.

Powracając do oznaczeń w (1), które implicite są użyte w (2), łatwo stwierdzić, że:

Δ(r) składa się z jedenastu (na ogół nieznanych) wartości zapisu po skończonym rozdaniu,

Π jest zbiorem wszystkich możliwych rozkładów prawdopodobieństwa zmiennych losowych przyjmujących 11 wartości.

Z reguł gry wynika, że dodanie przez rozgrywającego ♠2 lub ♠4 da na pewno ten sam efekt tzn:

Kryt ( ♠2 ) = Kryt ( ♠4 )

5 ZNACZENIE HEURYSTYKI DLA ROZGRYWKI BRYDŻOWEJ

Zarówno sformułowanie (1), jak i bardziej specyficzne (i bardziej intuicyjne) sformułowanie (2) zawierają tyle nieznanych dla gracza wartości i funkcji, że od tych sformułowań do efektywnego znalezienia najlepszego ruchu „wiedzie jeszcze daleka droga”. Na pewno tą „drogę” inaczej pokonują gracze „ludzcy” a inaczej programy grające w brydża i ich twórcy. Ci ostatni mają do dyspozycji bardzo już rozpowszechnioną metodę szacowania wartości oczekiwanej: symulację typu Monte Carlo. Problem szacowania wartości oczekiwanej przy pomocy symulacji posiada w teorii probabilistyki i statystyki szeroką literaturę. Monte Carlo już dawno przestało być tylko generacją niezależnych wersji zadanego rozkładu prawdopodobieństwa. Bez wchodzenia w szczegóły odsyłamy Czytelnika do pracy przeglądowej: (Greenwood, Wefelmeyer, 2003).!

Zarówno graczy (a przede wszystkim ich trenerów) jak i twórców programów grających powinno zainteresować inne podejście do tego problemu. Pojęcie: „heurystyka” ma dwa znaczenia w pewnym sensie różne, a jednak na przykładzie brydża zbliżone!!

Na terenie informatyki – ale również matematyki stosowanej – dominuje następujące rozumienie pojęcia: „heurystyka”.

Załóżmy, że mamy do rozwiązania pewien trudny problem obliczeniowy. Najprostszym przykładem jest tu znalezienie maksimum globalnego funkcji rzeczywistej (funkcjonału) mającej nieskończenie wiele maksimów lokalnych w swojej dziedzinie.

Są też przypadki kiedy znamy algorytm dojścia do rozwiązania trudnego problemu praktycznego, ale realizacja tego algorytmu jest zbyt kosztowna. Wtedy na pomoc przychodzi mądra heurystyka! Taka metoda – chociaż nie gwarantuje dojścia do rozwiązania – bywa:

1. Czymś często zupełnie wystarczającym

2. Pomocna przy rzeczywistym rozwiązaniu problemu.

Istnieje jeszcze co najmniej jedno znaczenie terminu: „heurystyka”. W metodologii nauk i logice, heurystyka to nie: METODA–ALGORYTM a raczej specyficzna: UMIEJĘTNOŚĆ, ZDOLNOŚĆ, DOCIEKLIWOŚĆ, METODYKA badacza. Chodzi o umiejętność wykrywania ukrytych związków np przyczynowych. Owo wykrywanie odbywa się na ogół przy pomocy stawiania inteligentnych albo wręcz twórczych hipotez.

Jak zobaczymy poniżej dwie pierwsze heurystyki (probabilistyczne) użyteczne dla optymalizacji rozgrywki brydżowej są bliskie pierwszej z powyższych definicji, natomiast trzecia (deterministyczna) podpada raczej, pod drugą definicję heurystyki!

To, że różnica między obiema – formalnie innymi – definicjami pojęcia „heurystyka” zanika jest widoczne z monografii Michalewicza i Fogela (2006).

Przedstawione heurystyki mogą być świadomie zastosowane tylko przez graczy kwalifikowanych. Gracze słabsi często nieświadomie wykorzystują w swojej rozgrywce tylko pewne elementy prezentowanych heurystyk.

Heurystyki mogą być pomocne przy projektowaniu i ulepszaniu programów (automatów) grających w brydża. Płyną z nich jednak nieco inne zalecenia niż dla graczy i ich trenerów.

6 TRADYCYJNA MATEMATYZACJA ROZGRYWKI I JEJ UOGÓLNIENIE – heurystyka 1

Kontynuujemy rozumowanie rozgrywającego pewien kontrakt. Przedstawimy, bez nadmiernego wchodzenia w szczegóły, tzw. tradycyjną probabilistyczną metodę optymalizacji rozgrywki. Ta metoda istnieje już co najmniej 60 lat, ale w żadnym opracowaniu nie została ona wielostronnie opisana. A wymaga takiego opisu!

Wyspecyfikujmy dość typową sytuację rozgrywającego.

Pozostało k lew do rozegrania (k ≤ 13).

Rozgrywający do realizacji kontraktu potrzebuje wziąć (1<) n (≤k) lew.

Załóżmy, że są możliwe dwie tzw. linie rozgrywki.

Przykładowo:

1. Linia L₁ polegająca na jednostronnym impasie damy w jednym z kolorów.

2. Linia L₂ polegająca na wyrobieniu jednego z kolorów bocznych.

Wybór optimum wg tej heurystyki polega na obliczeniu prawdopodobieństw sukcesu obu linii, a następnie wyboru linii o większym prawdopodobieństwie (wzięcia n lew). Linii może być więcej niż dwie.

Do obliczenia posiłkujemy się prawdopodobieństwami układów obu obrońców, które są niewidoczne dla rozgrywającego w sytuacji decyzyjnej. Prawdopodobieństwo L jest funkcją prawdopodobieństw zdarzeń elementarnych. Prawdopodobieństwa elementarne wylicza się z uwzględnieniem następujących danych:

1. Apriorycznych prawdopodobieństw układów kolorów. W praktyce następuje odpowiednia modyfikacja tych prawdopodobieństw.

2. Wnioskowaniu o położeniu istotnych figur u obrońców.

3. Danych dodatkowych wynikających z licytacji i z dotychczasowego przebiegu rozgrywki.

Słabości metody

Czasami trzeba rozważyć np. wynik rozdania jako wpadkę bez jednej. Taka wpadka może być opłacalna. Optymalna linia na wygranie kontraktu może się różnić od linii na wpadkę bez jednej. Problem ten komplikuje się dodatkowo, jeśli trzeba dodatkowo rozpatrywać wpadkę bez dwóch i nadróbkę.

Problemem też jest praktyczne wyliczenie przy stole prawdopodobieństw linii. Być może w dającej się przewidzieć przyszłości dopuszczone zostaną do użytku graczy (i/lub komentatorów pewnego typu rozgrywek sportowych) odpowiednio skonstruowane kalkulatory do wyliczania prawdopodobieństw sukcesu linii rozgrywkowej. Na pewno z czasem wszelkiego rodzaju tradycyjna lub nowa potwierdzona profesjonalnie wiedza będzie ujęta w formie hardware’owo–software’owej po to by wykorzystywać np. przy grze internetowej. Tak jak to ma miejsce przy korespondencyjnej grze w szachy.

Możemy zdyskontować pierwszą korzyść wynikającą z wprowadzenia kryterium optymalności (2). Otóż opisywana metoda istnieje już kilkadziesiąt lat a jednak:

1. Nie jest dobrze udokumentowana.

2. Jest niechętnie wykładana.

3. Jest niechętnie słuchana.

4. Rzadko się pojawia w periodykach profesjonalnych.

Oprócz wymienionych słabości możemy obecnie stwierdzić, iż metoda tradycyjna nie daje rozwiązania optymalnego a jedynie jest heurystyką. Zatem irracjonalny opór przed podejściem uważanym za naukowe i jedynie słuszne było całkiem racjonalne.

7 ZAWODNICZA OPTYMALIZACJA ROZGRYWKI CZYLI

WALKA O MAKSYMALIZACJĘ SPODZIEWANEJ ILOŚCI LEW – heurystyka 2

Większość doświadczonych graczy posiłkuje się metodą inną niż tradycyjna. Różnica polega nie tylko na algorytmie obliczeniowym, ale również na „filozofii”. Nie przede wszystkim szukają oni linii optymalnej – jest ona raczej skutkiem.

Przedstawimy pewną formalizację owej metody, a następnie opiszemy jej aspekty bardziej praktyczne.

Już na początku rozgrywki (po ukazaniu się „dziadka”) taki gracz szacuje oczekiwaną ilość lew, którą może wziąć. Następnie tak dobiera ruchy swoje i „dziadka” by zmaksymalizować ową wartość oczekiwaną, obserwując oczywiście kolejne ruchy obrońców.

Po ukazaniu się dziadka rozgrywający określa zwykle strategię rozgrywki, a następnie wzbogaca ją ruchami taktycznymi.

Ta metoda ma (w dystansie) tą przewagę nad metodą tradycyjną, że reaguje dynamicznie na wszystkie wydarzenia przy stole, a więc:

1. Namysły obrony. Namysły te są często specjalnie prowokowane poprzez nietypowe zagrania rozgrywającego.

2. Zrzutki obrony, zmieniające prawdopodobieństwa określonych konfiguracji zakrytych rąk.

3. Szybkość analizy – gracz rozpoczynający rozgrywkę po kilku sekundach, ma dużo większe szanse na to, że przeciwnicy przeciwko niemu popełnią więcej błędów.

4. Szybkość analizy – gracz rozpoczynający rozgrywkę po kilku sekundach, ma dużo większe szanse na to, że przeciwnicy przeciwko niemu popełnią więcej błędów.
Rozpoczynanie rozgrywki natychmiast lub szybko po wyłożeniu dziadka, szczególnie w intencji sprowokania przeciwnika do błędu a nie w płaskim rozdaniu, jest faulem i II obrońca ma prawo wstrzymać rozgrywkę. W ważnych rozgrywkach byłem świadkiem tego typu wstrzymań nawet jak obrońca miał zagranie oczywiste. Dotyczy to tylko sytuacji po pierwszym wiście, potem tempo jest dowolne.

5. Każda profesjonalna para, stara się kamuflować używane przez siebie konwencje wistowe.
To nieszczęśliwe sformułowanie, które traktowane dosłownie jest równoważne twierdzeniu że każda profesjonalna para oszukuje. Wszystkie ustalenia muszą być jawne i równo dostępne dla każdego z graczy przy stole. Stąd zakaz nie tylko ukrywania ustaleń, ale także stosowania kryptotechnik (ustaleń zależnych od klucza, w konkretnym rozdaniu znanego obrońcom, a nieznanego rozgrywającemu). Oczywiście patalogie się zdarzają, sam znam przypadek pary, która grała totalną ilościówką, ale nie raczyła o tym wspominać. Włosi też są na liście podejrzanych o niejawne ustalenia, ale dowodów brak (??, Leśniewski, który jest fanem analiz, ponoć ma teczkę z podejrzanymi rozdaniami, stąd ponoć taka niechęć do niego Bocchiego głośna przed paroma latami po wydrukowaniu wywiadu z nim w "Brydżu"). Również techniki w rodzaju zrzutki odwrotne z permutacją blotek (np. umawiamy się że 5 jest młodsza od 2 i informujemy o tym), mimo że dozwolone, są uznawane (i słusznie) za głęboko nieetyczne.

6. Toczy się walka o informację. Umiejętność selekcji i określenie prawdopodobieństwa prawdziwości uzyskanych informacji jest zdecydowanie niedoceniana przez brydżystów.

7. Ogromną pomoc w rozgrywce przynosi wiedza, kiedy przeciwnicy muszą zrzucić prawidłową ilościówkę. Można dostosować plan, nie do szans matematycznych, ale do rzeczywiście zastanych rozkładów.

Zupełnie nie opisuje się w materiałach teoretyczno–treningowych krzywych oczekiwanej ilości lew. Są to (w przypadku rozgrywki) krzywe, które mają 48 argumentów, gdyż po każdym ruchu oczekiwana ilość lew może ulec zmianie. Nie jest to sprawa prosta, bo przy publikacji trzeba nie tylko odtworzyć oceny gracza w trakcie rozdania ale także podać bardziej dokładne oszacowania zagranych kart i również odchylenia od optymalnych ruchów (czyli błędy gracza). Tego typu analiza musiałaby być skomputeryzowana, a wcześniej szczegółowo przedyskutowana.

Przedstawimy bardziej sformalizowaną formę tej heurystyki, nawiązując do kryteriów ogólnych (1) i (2):

Kryt ( r ) = Oczekiw₂ (∑ W_i ( r ) N_i )→ max (3)

i

gdzie:

N_i – ilość lew, które zostaną wzięte na końcu rozdania,

i – przebiega zbiór lew „znajdujących się jeszcze w grze”, tzn. po uwzględnieniu lew

już wziętych i takich, które gracz uważa za pewne zarówno dla siebie jak i dla obrony.

Słabości metody

Maksymalizowanie oczekiwanej ilości lew (do wzięcia przez rozgrywającego) nie zawsze prowadzi do maksymalnego zapisu.

W rzeczywistości gracze czasami uwzględniają jednak podejście tradycyjne i wówczas może dojść do konfliktu utrudniającego podjęcie decyzji.

Trzeba się przyzwyczaić do tego, że oczekiwana ilość lew nie jest liczbą całkowitą.

8 HEURYSTYKA „HIPOTEZOWA” – heurystyka 3

8.1 Wprowadzenie

Od zarania brydża istnieje problem „łapania” dam. Chodzi o sytuacje, w których rozgrywający może impasować brakującą mu damę w obie strony. Istnieją pewne ogólne wskazówki pomagające dokonać właściwego wyboru w konkretnej sytuacji, ale… gracze na ogół przedkładają irracjonalne (a nawet z lekka niecenzuralne) reguły typu: damę bierze się pod siebie.

Problem łapania dam w rozgrywce brydżowej można by uznać za zbyt płaski by go rozważać w sposób pogłębiony gdyby nie fakt, iż jest to jedynie wierzchołek góry lodowej. „Górę” tą można by nazwać wykrywaniem rozkładów sprzyjających.

O ile w przypadku konieczności zlokalizowania damy układy sprzyjające dla rozgrywającego są 2 i wiadomo jakie (tylko ciężko się zdecydować, na który zagrać), o tyle w wielu rozdaniach wykrycie takich układów bywa trudne. Aby „zbliżyć” tą problematykę do kryterium (2) i zdefiniować kolejną heurystykę przytoczymy w kolejnym punkcie jedną z zasadniczych wskazówek, która mądry nauczyciel daje dobrze zapowiadającemu się adeptowi brydża.

8.2 Pierwsza karta z dziadka

Wskazówka ta brzmi następująco:

„Nigdy nie dokładaj natychmiast pierwszej karty z dziadka”

Jest bardzo wiele powodów potwierdzających słuszność tej maksymy. My zwrócimy uwagę na jeden z nich. Okaże się on być jednym z kluczowych i chronologicznie pierwszym elementem przedstawianej heurystyki.

Moment wyłożenia dziadka zwiększa gwałtownie informację dla wszystkich trzech graczy, którzy za chwilę stoczą walkę. Jednak rozgrywający ma pewną przewagę, choć musi wykazać również maksymalną rozwagę Przewaga rozgrywającego wynika ona z dwóch powodów:

1. Rozgrywający w tym momencie dokładnie zna swój potencjał. Zna swoje silne i słabe strony. Strona przeciwna na ogół rozpoznaje swój potencjał stopniowo.

2. Z natury rzeczy rozgrywający będzie stroną aktywniejszą od obrony, bo poza skrajnie „dziwnymi” kontraktami, to rozgrywający bierze większość lew. A zatem ma on więcej możliwości inicjowania swoich PLANÓW niż przeciwnicy swoich!

8.3 Kolejne kroki algorytmu heurystyki 3

Przewagę swoją rozgrywający powinien wykorzystać w następujący sposób. Opiszemy tą metodę przy założeniu, że chce on wygrać zapowiedziany kontrakt.

Powinien on wyszukać takie rozkłady niewidocznych rąk obrońców, które zapewnią mu sukces. Jest to zadanie na ogół bardzo trudne, ale powinno być wykonane właśnie w momencie ukazania się dziadka. Załóżmy, że są 3 typy tych rozkładów.

Teraz rozgrywający powinien przejść do drugiego, równie trudnego jak pierwszy, etapu realizacji swego PLANU. Powinien „rozpisać” każdy z tych trzech typów sprzyjających mu rozkładów na ruchy czyli sekwencje dokładanych kart.

Wreszcie owa już zarysowywująca się heurystyka winna zostać ostatecznie dopracowana w następujący sposób. Otóż rozgrywający powinien poszukać najdłuższego ciągu ruchów (poczynając od tego pierwszego czyli dołożenia pierwszej karty z dziadka), który zapewnia realizację kontraktu przy założeniu prawdziwości wszystkich trzech hipotetycznych rozkładów.

To jest główny wariant tej heurystyki. W przypadku, gdy się okaże, że rzeczywisty rozkład kart obrońców odbiega od wszystkich założonych lub (tutaj nieco upraszczamy obraz autentycznej walki) rozgrywający poszedł „złą ścieżką”, należy dokonać korekty omawianej heurystyki (dostosowując ją do już ujawnionych kart). Owa konieczna korekta jest jednak już ewidentną porażką rozgrywającego – również ze względu na to , że na ogół informacje rozgrywającego są porównywalne w tej fazie gry z tym o czym wiedzą obrońcy.

8.4 Porównanie z poprzednimi heurystykami

Jak widać pomiędzy poprzednimi a obecną heurystyką jest zupełnie zasadnicza różnica. Nie sprowadza ona się jedynie do wcześniej zaanonsowanych charakterystyk:

1. Istotnym składnikiem „intelektualnym” heurystyki 3 jest świadomość tego, że dla każdego założonego układu kart w rękach obrońców istnieje deterministyczny optymalny algorytm rozgrywki. Jest to tzw. rozgrywka dla czterech rąk.

2. Heurystyki 1 i 2 podobnie jak teoretyczne kryterium mają charakter probabilistyczny, zaś heurystyka 3 jest deterministyczna.

Oto kolejne różnice:

1. 1 i 2 są zasadniczo dostosowane do kolejnych 24–ech ruchów rozgrywającego (rozgrywający ma do dyspozycji 26 kart, ale ostatnie dwie już nie podlegają jego wyborowi, bo muszą być dołożone), zaś heurystyka 3 „patrzy” na rozdanie wyłącznie całościowo.

2. Istotnym składnikiem „intelektualnym” heurystyki 3 jest świadomość tego, że dla każdego założonego układu kart w rękach obrońców istnieje deterministyczny optymalny algorytm rozgrywki. Jest to tzw. rozgrywka dla czterech rąk.

9 KRYTERIUM OPTYMALIZACYJNE DOTYCZĄCE RÓWNIEŻ OBRONY I LICYTACJI

Przedstawione metody rozgrywkowe można po pewnych modyfikacjach zastosować również do obrony. W przypadku metody tradycyjnej w jej głównym wariancie, obrońcy szukają linii prowadzącej do obłożenia kontraktu bez jednej z maksymalnym prawdopodobieństwem. W przypadku metody „zawodniczej” chodzi o maksymalizowanie wartości oczekiwanej ilości lew obrońców (a więc: 13–[ilość lew rozgrywającego]). W przypadku heurystyki 3, szuka się takich układów niewidocznych rąk, które umożliwiają obłożenie kontraktu.

Oprócz analizy należy używać odpowiednich zrzutek.

10 KLASYFIKACJA ZMIENNYCH Z_i

Przy istniejącej praktyce rozgrywek brydżowych zmienne Z_i wyliczane są w jeden z poniższych sposobów.

1. Zapis robrowy. Często zapis robrowy przelicza się na tzw. zapis jedno–rozdaniowy a ten z kolei czasami na IMP–y. We wszystkich przypadkach od razu po rozdaniu znany jest wynik. Amatorzy w najlepszym przypadku są w stanie optymalizować tylko przy tym sposobie zapisu. W trakcie rozgrywki współczynniki Z są stałymi.

2. Zapis miltonowy (Russian Chicago). Wynik rozdania zależny jest od siły połączonej pary rąk. Dla obrońców siła ta do końca praktycznie pozostaje nieznana. Natomiast dla rozgrywającego po otwarciu dziadka zapisy są wartościami stałymi.

3. Zapis turniejowy. Wynik rozdania zależy częściowo od wyników tego rozdania rozegranego na innych stołach turnieju. Tu wchodzi element statystyczny uwzględniony w tytule artykułu. Innych graczy można bowiem traktować jako próbę losową z określonej populacji.

4. Zapis meczowy. Porównuje się wynik rozdania z wynikiem uzyskanym na drugim stole przez drugą parę teamu przeciwko drugiej parze przeciwników. Efekt na ogół przelicza się na IMPy.

11 KOMENTARZE DO KRYTERIUM DOTYCZĄCE LICYTACJI

W wielu sytuacjach naprawdę decyzyjnych – tzn. wtedy gdy licytacja zbliża się do maksymalnej możliwej (dla rozdania) wysokości – licytujący musi się liczyć z kontrą karną strony przeciwnej. Zatem zapisy Z muszą być traktowane jako zmienne losowe o parametrze będącym prawdopodobieństwem kontry. Z minimalnym prawdopodobieństwem dodatkowym trzeba uwzględniać rekontrę.

Trzeba też brać pod uwagę przelicytowanie nawet najbardziej „napiętych” własnych kontraktów, przez przeciwników

Nie istnieje dotychczas matematyczna teoria licytacji, która uwzględnia specyfikę brydża.

12 PRZEGLĄD STRON INTERNETOWYCH I LITERATURY SPECJALISTYCZNEJ ZWIĄZANYCH Z OMAWIANYMI ZAGADNIENIAMI

Mówiąc z pewną przesadą można potraktować większość problemów teoretycznych i dydaktycznych brydża jako wprowadzanie, uzasadnianie i dydaktyka heurystyk poszukujących rozwiązania problemu optymalizacyjnego (1). Oczywiście dotychczas nikt w ten sposób nie stawiał sprawy. W ogóle w brydżu matematyka i podejście naukowe były dotychczas traktowane “po macoszemu”. W dotychczasowej niezwykle rozbudowanej literaturze przedmiotu znajduje zaledwie kilka pozycji w pełni naukowa. Na dodatek dotyczą ona aspektów (a jest ich jeszcze sporo), które tu nie były rozważane, dlatego ich nie zacytujemy.

Poniższe cytowania należy traktować jako próbkę – w założeniu reprezentatywną – dotyczącą zagadnień poruszanych w tym artykule. Są one 100%–owo profesjonalne w zakresie brydża, czy też według obecnie funkcjonującej nomenklatury: eksperckie.

Strony zajmujące się szeroko rozumianą działalnością dydaktyczną to:

www.dannykleinman.com/ www.michaelslawrence.com/ www.bridgedoctor.com/ www.kantarbridge.com/

Organizacje brydżowe prowadzące działalność dydaktyczną to:

Internetowa Szkoła Brydża Ryszarda Kiełczewskiego, www.PZBS.pl.

Polska ma niekwestionowane osiągnięcia we wszystkich sportowych dyscyplinach brydża.

http://web3.acbl.org/internet/websiteForms.nsf/ltpbForm?OpenForm

Największa i najbardziej wpływowa organizacja brydżowa” American Contract Bridge Ligue

Matthew Granovetter (wraz z małżonką) również prowadzi działalność dydaktyczną, jednak w znacznym stopniu opiera ją o oryginalną koncepcję teoretyczną przeznaczoną dla wistujących. Koncepcja ta jest częściowo opisana w książce: A SWITCH IN TIME by Pamela and Matthew Granovetter. Dalsze informacje na bieżąco na stronie: www.bridgetoday.com/. Koncepcja Granovetterów ma wysoki stopień „naukowości”.

Inna koncepcja, tym razem dotycząca licytacji, mająca wysoki procent naukowości, to tzw. prawo lew łącznych, zainicjowane przez Jean–Rene Vernesa w 1968 roku. Metodologię tą rozwijał następnie Larry Cohen w książkach: „Тo Bid Or Not To Bid.”, “Following Law”

Dobrze udokumentowaną (ale jednak nie 100% naukową…) krytykę tego prawa zawiera książka Mike’a Lawrence’a i Andersa Wirgrena: “I Fought The Law Of Total Tricks”, posiadająca polskie tłumaczenie: Jak walczyłem z prawem lew łącznych.

Dalsze dyskusje na stronie: www.newbridgelaw.com/

Symulacja Monte Carlo: http://www.solver.com/sdkplatform.htm

Pierwszy poważny software oparty na symulacji Monte Carlo: http://www.gibware.com/

Strony intelektualisty brydżowego Richarda Pavlicka oraz najbardziej teoretycznego czasopisma branżowego (obie ok. 80% “naukowości”). Prezentują wiele opracowań probabilistycznych i z zakresu teorii gier: http://www.rpbridge.net/bgtc.htm http://www.bridgeworld.com/

Pierwszy poważny program dotyczący analizy czterech rąk, wspominanej w związku z heurystyką 3:

http://www.deepfinesse.com/dfentry.html

LITERATURA MATEMATYCZNA CYTOWANA

Greenwood P. E., Wefelmeyer W., "Empirical estimators based on MCMC data",

w: Shanbhag D. N., Rao C. R., "Stochastic processes: modelling and simulation", Elsevier, pp.337–370, 2003.

Michalewicz Z., Fogel D. B., "Jak to rozwiązać czyli nowoczesna heurystyka", WNT, Warszawa, 2006.

Matematyka		Co nowego...		do Spisu
1 VI 2007	redakcja@pikier.com		© Pikier.com
brydż, brydz, bridge, brydż sportowy, brydz sportowy, bridge sportowy, Pikier, Sławiński, Slawinski, Łukasz Sławiński, Lukasz Slawinski,

http://niusy.onet.pl/niusy.html?t=watek&group=pl.rec.gry.brydz&tid=9069448&aid=54266623

---