Long pawns

We started talking about gameplay last week and looked kind of at the basic mechanics,

in other words Minimax search.

The idea is we are using search algorithms just like we were learned before, only that

with an opponent we have to take into account that the opponent tries to harm us in a zero

some game, anything they gain is what we lose.

Therefore we have this idea that Max is trying to maximise and Min is trying to minimise.

In a turn taking game that leads to these two layered trees.

So the prototypical game we are thinking of is

chess, turn taking, zero sum, discrete state, game, fully observable, deterministic, all

the things that make our life easy.

Essentially the problem description is exactly like in search except that we have these two

layers, the max layer, the min layers and max actions turn max states into min states

and the other way around and so on.

So that is a very simple way of expressing this and it gets us into a very simple kind

of algorithm which is the Minimax algorithm, which is kind of epitomised here.

Then it is Max's turn, then in this game he has nine choices and wants to take the best

one, no matter what Min does, in this case Min has eight choices because one field is

already taken and Min tries to maximise for herself which hurts Max.

So Max wants to find the best choice given that Min tries to minimise his chances.

The important thing to realise is the utility you get at the end.

You know that you have won or lost only very much at the end, in principle.

So the thing that happens here is we are propagating the utilities back through the Minimax tree

and that directly gets us to the algorithm.

So we looked at this example in detail, we will look at it more.

So given utilities at the base here, we can see that Max can expect a minimal utility

of three because Min cannot force the utility lower than three if Max has the choice.

Min always takes the minimum of the utility whereas Max takes the maximum which gives

us three in this case.

That's the basic algorithm.

Very easy to write down in a mutually recursive algorithm and it's also very easy to implement.

There is a couple of problems.

The problem is even though the algorithm works exactly as we are expecting, updating these

Max and Min values, in this case we are doing essentially a breadth first search.

As we know, this grows very rapidly which basically means we have to keep the fringe

in mind and the fringe may grow too big before we get the utilities.

That is the main problem.

That is also something we are going to optimise around later today.

Minimax is wonderful, it's completely infeasible because it's breadth first search.

There is no way, if you think about it, you can't really do iterative deepening search

here because you want to maximise over all of those if you want to be systematic.

One way out is to have evaluation functions where you estimate how good your board looks

even though you don't know the utilities.

As with the heuristics before, this is something which is informed search.

You are looking at the states.

You are looking at the board, in chess you are counting pieces, which is not something

that is given in the problem description.

Remember in the problem description for chess we only have states, black box states, we

cannot look into them but we can allow the heuristic or evaluation function to do that

anyway because external information, that is kind of the way we encapsulate information