home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 1 / crawlyvol1.bin / apps / math / euler / progs / opti.e < prev    next >
Text File  |  1993-02-06  |  4KB  |  167 lines
  1. .. Optimization routine
  2.  
  3. function opti (A,b,z)
  4. ## Minimizes z.x' with contraints A.x'>=b and x'>=0. Works only,
  5. ## if z>=0. Returns {x,K}.
  6.     si=size(A); m=si[2];
  7.     K=id(m); Kb=zeros(m,1);
  8.     x=Kb;
  9.     A1=A; b1=b;
  10.     repeat
  11.         r=A1.x-b1;
  12.         if r>=0; break; endif;
  13.         e=extrema(r'); i=e[2];
  14.         ir=nonzeros(r'~=e[1]); i=ceil(random(1,1)*length(ir)); i=ir[i];
  15.         v=A1[i];
  16.         mu=K'\v'; lambda=K'\z'; j=nonzeros(mu>epsilon());
  17.         if size(j)==[1,0];
  18.             error("No admissable point!");
  19.         else;
  20.             q=lambda[j]/mu[j];
  21.             e=extrema(q'); jj=e[2]; j=j[jj];
  22.         endif;
  23.         tt=K[j]; K[j]=v; A1[i]=tt;
  24.         t=Kb[j]; Kb[j]=b1[i]; b1[i]=t;
  25.         x=K\Kb;
  26.     end;
  27.     return {x',K}
  28. endfunction
  29.  
  30. function game (A)
  31. ## Maximizes G such that A'.q>=G, sum q_i = 1, q_i>=0.
  32. ## Returns {q,G,flag}. flag is 1 if its a strongly unique solution.
  33.     m=max(max(A)');
  34.     B=A'-m; si=size(B);
  35.     M=(B|ones(si[1],1))_(ones(1,si[2])|0)_(-1*ones(1,si[2])|0);
  36.     r=zeros(si[1],1)_1_-1;
  37.     z=zeros(1,si[2])|1;
  38.     {q,K}=opti(M,r,z);
  39.     return {q[1:si[2]],m-q[si[2]+1],!any((K'\z')~=0)};
  40. endfunction
  41.  
  42. function knobeln (n=3)
  43. ## Berechnet die beste Strategie beim Knobeln.
  44. ## A und B nehmen insgeheim je 0 bis n Hölzer.
  45. ## A nennt eine Zahl und B eine davon verschiedene.
  46. ## Wer näher an der Summe ist gewinnt die Hölzer des Gegners plus 1.
  47.     m=2*n+1;
  48.     A=zeros((n+1)*m,(n+1)*(m-1));
  49.     for i=0 to n;
  50.         for ik=0 to m-1;
  51.             for j=0 to n;
  52.                 for jk=1 to m-1;
  53.                     if i+j==ik;
  54.                         A[i*m+ik+1,j*(m-1)+jk]=j+1;
  55.                     else
  56.                         if (i+j>ik && jk<=ik) || (i+j<ik && jk>ik);
  57.                             A[i*m+ik+1,j*(m-1)+jk]=j+1;
  58.                         else
  59.                             A[i*m+ik+1,j*(m-1)+jk]=-i-1; 
  60.                         endif;
  61.                     endif;
  62.                 end;
  63.             end;
  64.         end;
  65.     end;
  66.     "Matrix berechnet",
  67.     {q,G,flag}=game(A);
  68.     "Gewinn für zuerst ansagenden : "|printf("%10.5f",G),
  69.     for i=0 to n;
  70.         for ik=0 to m-1;
  71.             if q[i*m+ik+1]~=0;
  72.             else
  73.                 printf("%7.5f : Nimm ",q[i*m+ik+1])| ..
  74.                 printf("%2.0f, sage ",i)|printf("%2.0f",ik),
  75.             endif;
  76.         end;
  77.     end;
  78.     if flag; "Einzige Lösung!", endif;
  79.     {p,G,flag}=game(-A');
  80.     "Gewinn für zweiten : "|printf("%10.5f",G),
  81.     for j=0 to n;
  82.         printf("Nimm : %2.0f",j),
  83.         for jk=1 to m-1;
  84.             if p[j*(m-1)+jk]~=0;
  85.             else
  86.                 printf("%7.5f : unterbiete ab ",p[j*(m-1)+jk])|..
  87.                 printf("%2.0f",jk),
  88.             endif;
  89.         end;
  90.     end;    
  91.     if flag; "Einzige Lösung!", endif;
  92.     return {q,p};
  93. endfunction    
  94.  
  95. function schere
  96. ## Berechnet die optimale Lösung für das Schere-, Papier-, Brunnen- und
  97. ## Steinspiel.
  98.     q=game([0,1,-1,-1;-1,0,1,1;1,-1,0,1;1,-1,-1,0]);
  99.     "Wähle mit Wahrscheinlichkeit",
  100.     "Schere  : ", q[1],
  101.     "Papier  : ", q[2],
  102.     "Brunnen : ", q[3],
  103.     "Stein   : ", q[4],
  104.     return q;
  105. endfunction
  106.  
  107. function pokern (w=5,e=5)
  108. ## Löst ein einfaches Pokerspiel. A und B bekommen ein Karte im Wert
  109. ## 1 bis w. A passt oder setzt e. B kann dann passen
  110. ## oder halten. Der Grundeinsatz ist 1.
  111.     A=zeros(w,w);
  112.     for i=1 to w; ## Setze bei Karte i bis w
  113.         for j=1 to w; ## Halte bei Karte j bis w
  114.             if j<=i;
  115.                 A[i,j]=(w-i+1)*(j-1)+(e+1)*(w-i+1)*(i-j)-w*(i-1);
  116.             else
  117.                 A[i,j]=(w-i+1)*(j-1)-(e+1)*(w-j+1)*(j-i)-w*(i-1);
  118.             endif;
  119.         end;
  120.     end;
  121.     A=A/(w*w);
  122.     "Matrix erzeugt!",
  123.     {p,G,flag}=game(A);
  124.     "Gewinn : "|printf("%10.5f",G),
  125.     "Strategie für A:"
  126.     for i=1 to w;
  127.         if !(p[i]~=0);
  128.         printf("%7.5f : ",p[i])|printf("Setze bei %2.0f bis ",i)|..
  129.         printf("%2.0f",w),
  130.         endif;
  131.     end;
  132.     {q,G,flag}=game(-A');
  133.     "Gewinn : "|printf("%10.5f",G),
  134.     "Strategie für B:"
  135.     for i=1 to w;
  136.         if !(q[i]~=0);
  137.         printf("%7.5f : ",q[i])|printf("Halte bei %2.0f bis ",i)|..
  138.         printf("%2.0f",w),
  139.         endif;
  140.     end;
  141.     return {p,q};
  142. endfunction
  143.  
  144. function simulhelp (w,a,k1,b,k2)
  145.     return -(a<k1)+(a>=k1)*((b<k2)+(b>=k2)*(w+1)*((a>b)-(a<b)))
  146. endfunction
  147.  
  148. function simul (k,w,pa,k1,k2,pb,k3,k4,n=1000)
  149. ## Simuliert eine Pokerspiel mit den Regeln aus function poker.
  150. ## A setzt mit Wahrscheinlichkeit pa ab k1, mit (1-pa) ab k2.
  151. ## B hält mit Wahrscheinlichkeit pb ab k3, mit (1-pb) ab k4.
  152.     a=floor(random(1,n)*k)+1;
  153.     b=floor(random(1,n)*k)+1;
  154.     ra=random(1,n);
  155.     rb=random(1,n);
  156.     win = sum( ..
  157.         (ra<pa) * (rb<pb) * simulhelp(w,a,k1,b,k3) + ..
  158.         (ra>=pa) * (rb<pb) * simulhelp(w,a,k2,b,k3) + ..
  159.         (ra<pa) * (rb>=pb) * simulhelp(w,a,k1,b,k4) + ..
  160.         (ra>=pa) * (rb>=pb) * simulhelp(w,a,k2,b,k4)),
  161.     return win
  162. endfunction
  163.  
  164. "opti(A,b,z) definiert."
  165. "game(A) definiert."
  166. "knobeln, pokern, schere und simul definiert."
  167.