1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
comment
Optimization examples (two person games).
gambling, scissors, poker.
game(A), computes an optimal strategy for the game with matrix A.
endcomment
function opti (A,b,z)
## Minimizes z.x' with contraints A.x'>=b and x'>=0.
## Returns x.
{x,f}=simplex(-A,-b,z)';
if f!=0; error("Simplex failed!"); endif;
return x;
endfunction
function game (A)
## Maximizes G such that A'.q>=G, sum q_i = 1, q_i>=0.
## Returns {q,G}.
m=max(max(A)');
B=A'-m; si=size(B);
M=(B|ones(si[1],1))_(ones(1,si[2])|0)_(-1*ones(1,si[2])|0);
r=zeros(si[1],1)_1_-1;
z=zeros(1,si[2])|1;
{q,K}=opti(M,r,z);
return {q[1:si[2]],m-q[si[2]+1]};
endfunction
function gambling (n=2)
## Computes an optimal strategy for the following game
## player A and B take 0 to n stones each.
## A claims a number and B another,
## The number, which is closer to the sum of the stones, wins.
## The win is the stones of the opponent plus 1.
eps=setepsilon(1e-5);
m=2*n+1;
A=zeros((n+1)*m,(n+1)*(m-1));
for i=0 to n;
for ik=0 to m-1;
for j=0 to n;
for jk=1 to m-1;
if i+j==ik;
A[i*m+ik+1,j*(m-1)+jk]=j+1;
else
if (i+j>ik && jk<=ik) || (i+j<ik && jk>ik);
A[i*m+ik+1,j*(m-1)+jk]=j+1;
else
A[i*m+ik+1,j*(m-1)+jk]=-i-1;
endif;
endif;
end;
end;
end;
end;
{q,G}=game(A);
"Win for A : "|printf("%10.5f",G),
for i=0 to n;
for ik=0 to m-1;
if q[i*m+ik+1]~=0;
else
printf("%7.5f : Take ",q[i*m+ik+1])| ..
printf("%2.0f, say ",i)|printf("%2.0f",ik),
endif;
end;
end;
{p,G}=game(-A');
"Win for B : "|printf("%10.5f",G),
for j=0 to n;
printf("Take : %2.0f",j),
for jk=1 to m-1;
if p[j*(m-1)+jk]~=0;
else
printf("%7.5f : say less at ",p[j*(m-1)+jk])|..
printf("%2.0f or more.",jk),
endif;
end;
end;
setepsilon(eps);
return "";
endfunction
function scissors
## Computes the optimal strategy for the following game.
## A and B have a secret choice from scissors, paper, well or stone.
## scissors wins against paper.
## paper wins against well and stone.
## well wins against scissors and stone.
## stone wins againts scissors.
q=game([0,1,-1,-1;-1,0,1,1;1,-1,0,1;1,-1,-1,0]);
"Choose with probability",
"scissors : ", q[1],
"paper : ", q[2],
"well : ", q[3],
"stone : ", q[4],
return q;
endfunction
function poker (w=5,e=5)
## Solves a primitive poker game.
## A and B get a card valued from 1 to w.
## A and B place 1.
## A places e or passes. B can pass or hold.
A=zeros(w,w);
for i=1 to w; ## Setze bei Karte i bis w
for j=1 to w; ## Halte bei Karte j bis w
if j<=i;
A[i,j]=(w-i+1)*(j-1)+(e+1)*(w-i+1)*(i-j)-w*(i-1);
else
A[i,j]=(w-i+1)*(j-1)-(e+1)*(w-j+1)*(j-i)-w*(i-1);
endif;
end;
end;
A=A/(w*w);
{p,G}=game(A);
"Win for A : "|printf("%10.5f",G),
"Strategy for A:"
for i=1 to w;
if !(p[i]~=0);
printf("%7.5f : ",p[i])|printf("Place from %2.0f to ",i)|..
printf("%2.0f",w),
endif;
end;
{q,G}=game(-A');
"Win for B : "|printf("%10.5f",G),
"Strategy for B:"
for i=1 to w;
if !(q[i]~=0);
printf("%7.5f : ",q[i])|printf("Hold from %2.0f to ",i)|..
printf("%2.0f",w),
endif;
end;
return {p,q};
endfunction
function simulhelp (w,a,k1,b,k2)
return -(a<k1)+(a>=k1)*((b<k2)+(b>=k2)*(w+1)*((a>b)-(a<b)))
endfunction
function simul (k,w,pa,k1,k2,pb,k3,k4,n=1000)
## Simulates a poker game.
## A places with probabilty pa from k1,with (1-pa) from k2.
## B holds with probability pb from k3, with (1-pb) from k4.
a=floor(random(1,n)*k)+1;
b=floor(random(1,n)*k)+1;
ra=random(1,n);
rb=random(1,n);
win = sum( ..
(ra<pa) * (rb<pb) * simulhelp(w,a,k1,b,k3) + ..
(ra>=pa) * (rb<pb) * simulhelp(w,a,k2,b,k3) + ..
(ra<pa) * (rb>=pb) * simulhelp(w,a,k1,b,k4) + ..
(ra>=pa) * (rb>=pb) * simulhelp(w,a,k2,b,k4)),
return win
endfunction
|
