Simple Example of MiniMax with Alpha-Beta Cutoff

In the game tree that you see, the root is a Max node. The scores of the leaf nodes are presented immediately below them.

Here is a trace of the execution of the Minimax strategy with Alpha Beta Cutoff.

	NODE	TYPE	 A	B	ALPHA	BETA	SCORE

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

ingargiola@cis.temple.edu