6.034 'Cheat sheet': MiniMax with Alpha-Beta Pruning                           10/1/03, R. Berwick

Two Player Games: MiniMax

	function MINIMAX(N) is
	begin
	   if N is a leaf then
	        return the estimated score of this leaf
	   else
	        Let N1, N2, .., Nm be the successors of N;
	        if N is a Min node then
		    return min{MINIMAX(N1), .., MINIMAX(Nm)}
	        else
		    return max{MINIMAX(N1), .., MINIMAX(Nm)}
	end MINIMAX;

   function MINIMAX-AB(N, A, B) is
   begin
      Set Alpha value of N to A and Beta value of N to B;
      if N is a leaf then
         return the estimated score of this leaf
      elsif N is a Min node then
	 For each successor Ni of N loop
	    Let Val be MINIMAX-AB(Ni, Alpha of N, Beta of N);
	    Set Beta value of N to Min{Beta value of N, Val};
	    When Beta value of N <= Alpha value of N then exit loop;
         Return Beta value of N;
      else
	 For each successor Ni of N loop
	    Let Val be MINIMAX-AB(Ni, Alpha of N, Beta of N);
	    Set Alpha value of N to Max{Alpha value of N, Val};
	    When Alpha value of N >= Beta value of N then exit loop;
	 Return Alpha value of N;
   end MINIMAX-AB;

		NODE	TYPE	ALPHA	BETA	SCORE	

		A	Max	-I	+I
		B	Min	-I	+I
		C	Max	-I	+I
		D	Min	-I	+I
		E	Max	10	10	10
		D	Min	-I	10
		F	Max	11	11	11
		D	Min	-I	10	10
		C	Max	10	+I
		G	Min	10	+I
		H	Max	9	9	9
		G	Min	10	9	9
		C	Max	10	+I	10
		B	Min	-I	10
		J	Max	-I	10
		K	Min	-I	10
		L	Max	14	14	14
		K	Min	-I	10	10
		J	Max	10	10	10
		B	Min	-I	10	10
		A	Max	10	+I
		Q	Min	10	+I
		R	Max	10	+I
		S	Min	10	+I
		T	Max	5	5	5
		S	Min	10	5	5
		R	Max	10	+I
		V	Min	10	+I
		W	Max	4	4	4
		V	Min	10	4	4
		R	Max	10	+I	10
		Q	Min	10	10	10
		A	Max	10	10	10

---