3. Dynamisch programmeren bij Risk
english
Het wordt nu tijd om even met andere ogen naar het werpen van de dobbelstenen te kijken, maar eerst nog even wat notatie:

A: aantal legers van de aanvaller A ÎS = {1,2,....}).
V: aantal legers van de verdediger ( V ÎT = {0,1,2,....}).

Pr{(A,V)}: kans dat de aanvaller van de verdediger wint bij een gegeven aantal legers. Dit noemen we ook wel de slagingskans.

In deze definities ligt het kroonjuweel van mijn Risk-analyse besloten. Het aantal legers van de aanvaller en de verdediger wordt als een toestand in de toestandsruimte S´ T. Een soort Markov-proces als het ware. Vanuit dit standpunt bezien zijn de verlieskansen toestandsovergangskansen van de toestand (A,V) naar een lager gelegen toestand. Welke toestanden zijn dat? Simpel, er zijn maar maximaal vijf mogelijkheden:

(A-1,V): De aanvaller heeft één leger verloren.

(A,V-1): De verdediger heeft één leger verloren.

(A-2,V): De aanvaller heeft twee legers verloren.

(A-1,V-1): Beiden hebben één leger verloren.

(A,V-2): De verdediger heeft twee legers verloren.

In het algemeen is het nu zo dat:

Deze formule geldt vanaf het moment dat zowel de aanvaller als de verdediger met minimaal twee dobbelstenen kan gooien. Of equivalent als de aanvaller minimaal drie en verdediger minimaal twee legers heeft. Alle toestanden die hier onder zitten zullen we apart moeten beschouwen.

Beginnen we met de nulde kolom. We definiëren Pr{(A,0)}º1. Dit is logisch als de verdediger geen legers meer heeft, heeft de aanvaller met 100 procent zekerheid gewonnen. Analoog voor de eerste rij, de nulde rij bestaat niet, kunnen we stellen dat Pr{(1,V)}º0. Voor de toestand (1,0) zijn deze definities conflicterend, daarom laten we Pr{(1,0)} ongedefinieerd. Dat is geen probleem want deze toestand komt nooit voor. Kijken we nu naar de eerste kolom, dit zijn de toestanden (A,1) met A>=2. Vanuit toestand (2,1) kan ik naar toestand (1,1) of (2,0). De aanvaller en verdediger kunnen immers maar met één dobbelsteen gooien. Er geldt nu:

Pr{(2,1)}=Pr{(1,1)}*Pr{verlies verdediger=0}+Pr{(2,0)}*Pr{verlies verdediger=1}

Met behulp van de tabel op bladzijde 3 en de hiervoor gedefinieerde kansen kunnen we nu Pr{(2,1)} uitrekenen door gewoon de getalletjes in te vullen.

Pr{(2,1)}=0*21/36+1*15/36=15/36

Dezelfde truc passen we toe bij toestand (3,1). Vanuit (3,1) kan ik naar (2,1) of (3,0). Voor de slagingskans geldt dan:

Pr{(3,1)}=Pr{(2,1)}*Pr{verlies verdediger=0}+Pr{(3,0)}*Pr{verlies verdediger=1}

dus: Pr{(3,1)}=15/36*91/216+1*125/216

En tenslotte geldt op analoge wijze voor de toestand (4,1) dat:

Pr{(4,1)}=Pr(3,1)*Pr{verlies verdediger=0}+Pr{(4,0)}*Pr{verlies verdediger=1}

ofwel: Pr{(4,1)}=Pr{(3,1)*441/1296+855/1296

Na de toestand (4,1) veranderen de overgangskansen in kolom 1 niet. Voor elke volgende toestand gebruiken we dus de recursieve formule:

Pr{(A,1)}=Pr{(A-1,1)}*441/1296+855/1296 met A³ 5

Komen de toe aan de tweede rij. Dat zijn de toestanden (2,V) met V>=2. Nu mag de aanvaller maar met één dobbelsteen gooien terwijl de verdediger met twee kan gooien. We gaan ervan uit dat de verdediger dit ook echt doet. Het is immers de optimale verdediging voor hem/haar om met twee dobbelstenen te gooien. Voor elke toestand geldt:

Pr{(2,V)} = Pr{(1,V)}*Pr{verlies verdediger=0} +

Pr{(2,V-1)}*Pr{verlies verdediger=1}

ofwel: Pr{(2,V) = Pr{(2,V-1)}*55/216 voor alle V>=2

Vanaf de derde rij, de toestanden (3,V) met V>=2, wordt de verdediger de mogelijkheid geboden om met één of twee dobbelstenen te gooien. Vanaf dit moment is de algemene formule toepasbaar. Er is echter één maar. De aanvaller mag in dit geval maar met twee dobbelstenen gooien. Dit beïnvloed de overgangskansen en dus moet deze rij apart opgebouwd worden. De procedure die de slagingskansen uitrekent bevat daarom een speciaal blok coëfficiënten voor deze rij.

Vanaf de vierde rij en de tweede kolom, kan de aanvaller met drie dobbelstenen gooien en kan de verdediger kiezen voor één of twee dobbelstenen. We nemen aan dat de aanvaller dan altijd met drie dobbelstenen gooit. Met één of twee gooien zou dom zijn nu de verdediger de mogelijkheid heeft met twee dobbelstenen te gooien. De tabellen laten duidelijk zien dat de aanvaller dan in het nadeel is. De aanvaller gooit dus met drie dobbelstenen. De verdediger reageert hierop door die strategie kiezen die de slagingskans minimaliseert. Zodoende ontstaan er twee tabellen. Voor de verdediger één met optimale strategieën (de strategieverdedigingsmatrix) en voor de aanvaller één waarin de minimale slagingskansen staan (de slagingsmatrix).

Dat klinkt ideaal, maar er zijn toch enkele problemen. Het is namelijk zo dat het zojuist beschreven algoritme steeds meer in de problemen komt naarmate de minimale slagingskansen in de buurt van de 0 of 100 procent komen. Dit is logisch want een grote overmacht van de aanvaller of verdediger zal de slagingskansen sowieso naar 0 of 100 procent drukken ongeacht de gehanteerde strategie. Daarbij komt ook nog eens het feit dat de strategieën onderling weinig van elkaar verschillen (zie hiervoor de tabellen met de gemiddelden). De slagingskansen die aldus gegenereerd worden zijn echt de optimale, maar in de praktijk zullen de overige strategieën weinig verschil laten zien met de minimale slagingskans. Dit maakt de cijfers die in de slagingsmatrix staan dus alleen nog maar harder. De strategieën die in de strategieverdedigingsmatrix staan moeten dus wel gerelativeerd worden. Neemt echter niet weg dat ook deze waarden echt de optimale zijn.

Het tweede probleem is technisch van aard en heeft te maken met de beperkingen van de Turbo-Pascal en Turbo-C. Om een slagingskans te berekenen worden alle onderliggende slagingskansen in een array opgenomen. Dit kost flink wat geheugen terwijl de compilers deze slechts in beperkte mate kunnen aanspreken. Ook het feit dat alle berekeningen in 'double double precision' moeten worden uitgevoerd beperkt de ruimte die aanspreekbaar is. De C-code van het programma staat daarom niet toe dat het aantal legers van de aanvaller of verdediger boven de 80 komt.

Het moet echter niet uitgesloten worden geacht dat het algoritme met behulp van pointers in C efficiënter kan worden gemaakt. Om berekend te kunnen worden heeft ieder element van de slagingsmatrix in principe slechts 5 andere elementen keer 11 strategieën nodig. De slagingsmatrix zou onder deze omstandigheden in principe onbeperkt uitgebreid kunnen worden.

vorige
INDEX
volgende