In the process of understanding minmax algorithm (pruning alpha – beta) I have references numerous articles and feel your posts QUANG WILD'S BLOG relatively straightforward and detailed. We thank the author of the article and the author for permission to be quoted, refer to the content of your posts.

Consider a game in which two people turn to their country as chess, chess, caro,… The game has a starting state and every move will change the current state to a new state. The game will end in a certain provisions, according to which the game will result in a state reflects a winner or a state that both players can not develop their moves, I call it peace flag status. We sought to analyze whether from a state that will result in the player will win the condition that both players have the same level.

One such games can be represented by a tree, called the game tree. Each node of the tree represent a state. The root node representing the start state of the game. Each leaf node representing a final state of the game (winning state or air). If the state x is represented by node n n is the son of performances for all the results of the state of water can go from state x.

Example 3-5: At the checkers game with 9 umbrella. Two people turn to X or O. Those who go are 3 straight umbrella (transverse, along, oblique) the winner. If all cells go without inconclusive, the two players tie. Part of this game is represented by a tree after:

In the game tree, leaf nodes are shaded background and borders distinctive double to other nodes. We can assign to each leaf node values ​​to reflect a state of peace or winning players. For example we assign to the leaf node values ​​as follows:

· 1 if there riders have won X,

· -1 if people go there and lost X

· 0 If two players have the same air.

Thus from any state, turn, X riders will choose a move that led to the state with the largest value (in this case is 1). We say that X make the move MAX, from which the X button choose their moves are called nodes MAX. O turn riders will choose a move that led to the state with the smallest value (in this case is -1, then X will be lost and thus O wins). I say make the move MIN O, O nodes from which choose their moves called MIN button. Because the two players take turns away his water so the tree each game as well as MAX and MIN luanphien. Trees also play so called tree MIN-MAX. We can offer a set of rules for the nodes in the tree to reflect the state of peace and a winner or winners possibility of two players.

If a node is a leaf node, then its value is the value assigned to that button. Contrary, MAX button, the button if the value of it by the maximum value of all the values ​​of its children. If the node is a node, then its value MIN is the minimum value of all the values ​​of its children.

This treatment also rules similar to the rules of arithmetic expression tree, the difference here is that the operator is the max or min function takes and each node can have multiple children. Therefore we can use the technique to turn back the value for the node of the tree game.

To install a number of assumptions we have the following:

· We have schools information gives the value of.
· Constants 2 and -2 respectively the largest and the smallest value of each node.
· A transformer c char to determine the value for the X or O button to go.
· One type pointer declared an appropriate way to represent a node in the tree reflects the state of the game.
· I have a function nutLa() to determine whether there is a node or a leaf node?
· Jaw max and min respectively take the maximum value and the minimum value of the two values.

Exhaustive treatment algorithm for game tree
Jaw hours admitted to a node q and c character returns the value of the node.

If q is a leaf node, it returns the value assigned to the leaf node. Conversely, we give a temporary value q value is -2 or 2 depending q is X or O button and the review of q. After a q-value of V is reset val = max(hours,The) If q is the X button and value = min(hours,The) if q is O button. When all the children of q was considered temporary, the value of q val become its value.

{Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax}
function val(var q: pointer; c: char; Vp: item): item;
var
	i: integer;
begin
	if (nutLa(q)) then      {Neu la nut la thi lay ngay KQ gia tri cua nut do}
        begin
                {writeln(q^.lab,'->>> ', q^.info);}
                val:= q^.info;
        end
	else
	begin
		for i:= 1 to q^.numChild do   {Duyet cac nut con cua q}
		begin
			if c = 'X' then       {Neu dang la luot X}
			begin
				q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
				val := q^.info;
            end
			else                    {Nguoc lai la luot O}
			begin
				q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
				val := q^.info;
				break;
			end;
		end;
	end;
end;

Apply to the general tree T we have installed:

procedure catTia(var T: pointer);  {Dua thuat toan vao cay}
var
	p: pointer;
	i: integer;
begin
	if T <> nil then
	begin
		T^.info := val (T, 'X', T^.info);
	end;
end;

The program you can complete the look here

Read more: General tree