Paulo Pinto's contest entry has just been posted.

Discusses how search can be applied to logic games with full information. Game trees are described, as well as an algorithm that can search them. Pseudo code is given and optimisations like alpha-beta are explained.

http://ai-depot.com/LogicGames/MiniMax.html

Be sure to check out the current contest for a bit of action!

Very good article. I like it a lot. Would be nice if you give more samples like Connect 4, Othello, Gomoku, etc to learn from. Anyway, hope you can fix the link on the last page of your tutorial. Thanks.

I've updated my site and that update broke the links.
Please look at

http://www.progtools.org/games/projects/checkers/checkers.html
http://www.progtools.org/games/projects/sharp_checkers/sharp_checkers.html

Hi

I 'm doing my monograph in my high school about algorithms used in chess.

Please if you have someone material, send me

Hi,

I wonder if the function MinValue in the pseudo code contains a slight error. Because you want the lowest value, shouldn't best_move be initialized as "maximum", so that all evaluations result in lower values. And, shouldn't the 'if Value > best_move' be 'if Value < best_move' (less than)?

Thanks for writing it anyway!

Patrick.

I will take a closer look to the code.
You're probably right.

The description of how minimax works is fine, but I really would like to see an explanation of why it works.

Sincerely GL7

David George Elsdon: but I really would like to see an explanation of why it works.

Ed: minimax in chess for instance the white and then the black party

It is used in many games, just switching the party. What good is for one (max) is bad for the other (min). Look it in this way and the opposite way.

I don't know if you mean this? It's a principle, not so difficult, I think.

Ed van der Meulen

Hi Ed

What I mean is you could just do a one ply lookahead, evaluate all the positions and go for the best. But the received wisdom is that a two ply lookahead is better and a three ply lookahead is even end so on. But why is this ??

Some people argue that you can anticipate problems that are ahead in the game, but you are just as likely to look into trouble as through it to see the resolution.

What I really want is a mathematical (probability theory I guess) explanation of why minimax works. I have not found any good papers on it.

Sincerely GL7

Hello David George

Simple the turns are white black w b w b ....

Each time the min score changes in max and max score change in min and you can use the same algorithm. Young Blue does it trillion time a ..., I don't know changing of parties and use one huge algorithm used of course by deep junior in his latest match against Kasparov.

Compare minimax with a player changes each time his position, plays for white and then for black and so on, and thinks also ahead in this way. So both in reality and during thinking ahead. And he is like we always very honest, isn't it?

Ed

Lets say i want a search of level 5. Do i go thorugh the whole process 5 times? or do i count 1 for the black move, then 2 for the white move, then 3 for the black move and so on?

Hello Marty,

If in the players have to do 5 moves, for instance 2 by white and 3 by black, like you say. It's a little bit strange if white has to do 4 moves and black only one.

Yes, and then you think you are white and be good for him and bad for black. You really think ahead then so you want also be sure black can't do much. So you plan a move, switch parties and be good for black and bad for white. You get then maybe the best play, but still you can lose, grin. You can try it in reality.

I learn sometimes in this way. Playing and so thinking for both parties. When you make a game you do this for instance.

Do you play chess?

Ed

If you want a search level 5, then you should count 1 for the black move, 2 for the next white move, 3 for the black move and so on.

If you did the process 5 times you would probably get the same answer in those 5 times.

There are many types of games where the minmax is deterministic, so doing the process more than once doesn't improve it in any way.

A real chess play

I am the only thinker and player

I do e2-e4, not so unusual, The algorithm is big, a database move. I was clearly white. But think we have now no database which tell this move is appropriate.

Then you play for black. You do your best now for him, minimax, instead of max for white you play now min for white, that is the principle. What you do then is of course using all knowledge. But that's isn't the point. The switching aspect that is minimax. What you do then is your case. No, you don't do things twice.

This means you can often jump a number of moves. However with big databases, I wouldn't jump very far. You can maybe further search in the databases. Suddenly he recognizes an old splendid party, wow! Don't jump too far you could loose in this way, isn't it.

No you nearly never compute things twice, you store a lot.

When you play the parties yourself you do the same, you don't think deep twice. No? Many chess players do. But the minimax principle is only the switching feature, I think.

And I have told that already. So this is new.

Ed van der Meulen

Your're right about chess but there are many board games that don't really need a big database and are easily deterministic.

For example in tic-tac-toe, if both players play to win, which they are supposed to, the games always end up in a draw. And since the game moves are fairly simple, you can know all moves from a given point.

So, given a starting position, assuming that the players choose their best move, you will always end up with the same game sequence.

But as you said this isn't true for complex games as chess.

can someone explain, in simple pseudo code or in plain english, how to implement a minimax for an othello player? black is player, white is computer. I have an idea but i think is wayy of... heres what i think

-GEt available positions for white
-place piece in every position and evaluate
-choose highest evaluated
-get available positions for white
-place piece in lowest position and evaluate
-choose lowest evaluated
and so on...

someone explain! or put me out of my misery!

Your way of thinking is more or less correct.

You should assign values to the board positions so that each position has a different weight. For example, placing pieces on the corners is better than placing them on the side, and placing them on the side is better than placing them on the middle of the board.

As for the tree generation. You must be aware of the tree state when generating moves. For example, when you say that "place piece in lowest position..." I assume that you're talking about black moves. But in this point you should be generating moves for black and not white. The tree must have the moves White->Black->White->Black->... and so on.

David George Elsdon said:
"What I mean is you could just do a one ply lookahead, evaluate all the positions and go for the best. But the received wisdom is that a two ply lookahead is better and a three ply lookahead is even end so on. But why is this ??

Some people argue that you can anticipate problems that are ahead in the game, but you are just as likely to look into trouble as through it to see the resolution.

What I really want is a mathematical (probability theory I guess) explanation of why minimax works. I have not found any good papers on it."

I think this is an excellent question and it is easy to give shallow answers to it without actually addressing what David means here.

It would be easy to give a shallow answer - that a look ahead search allows consideration of tactical possibilities in the near future that could change the evaluation, but that doesn't really address David's rather subtle point. Unknown tactical situations await in the future of any search after it has hit its terminal nodes, so why should those that lie beyond the horizon of a 1-ply search (or even a straightforward application of the evaluation function to the current position without any look-ahead search at all) be any more threatening to the accuracy of the evaluation than those that lie beyond the horizon of a 5-ply search?

Here is my attempt at an answer:

If games of chess were much longer, then a look-ahead search would not achieve much, but chess games tend to be limited in length. What is important here is how many moves remain in the game AFTER the terminal nodes are reached. Those unknown moves and tactical possibilities compromise the correctness of the evaluation. If we made our positional evaluation immediately after the very last move in the game the evaluation would be totally correct. - after all we know the winner at this stage. If we made our positional evaluation 1 move before the end of a game then our positional evaluation would have some doubt in it - something could happen in that next move and if we made our evaluation 2 moves before the inevitable end of a game the doubt in the evaluation increases still further.

A positional evaluation is compromised by the moves that occur after it, and the more moves that could occur after it, the more opportunities there are for tactical events to make the evaluation incorrect and the uncertainty in the evaluation increases with every move that can possibly be made after it.

A 5-ply search is therefore better than a 1-ply search because its terminal nodes are closer to the end of the game and there are therefore fewer unknown moves occurring after the evaluation to compromise it - a game has less time to do something unpredictable after a deep look-ahead search than it does after a short look-ahead search.

If you consider searches performed, firstly so that the end of the game always falls within the horizon of the search, then searches earlier in the game, so that some game endings fall within the horizon and others end not long after and gradually keep moving the imaginary horizon further back, so that it occurs sooner in the game I think you'll see what I mean.

Good question anyway: I had to think about that one.

Paul: If games of chess were much longer, then a look-ahead search would not achieve much, but chess games tend to be limited in length.

Ed: This is a game isn't it? Not important if a chess match could last 200 moves to look ahead? Are you sure. For a chicken who has the will to win from me, a normal game will be long enough, don't you think? But sorry, chicken, you really have to look ahead, else you don't win from me. I don't understand your opinion Paul, grin.

Paul: What is important here is how many moves remain in the game AFTER the terminal nodes are reached. Those unknown moves and tactical possibilities compromise the correctness of the evaluation.

Ed: Yes of course with less depth the computer can look broad. But evaluate please after you stop searching maybe you have won already. Didn't you want to win? Sorry you say the same.

Paul: If we made our positional evaluation immediately after the very last move in the game the evaluation would be totally correct. - after all we know the winner at this stage. If we made our positional evaluation 1 move before the end of a game then our positional evaluation would have some doubt in it - something could happen in that next move and if we made our evaluation 2 moves before the inevitable end of a game the doubt in the evaluation increases still further.

Ed: Completely correct Paul. I was too hasty.

Paul: A positional evaluation is compromised by the moves that occur after it, and the more moves that could occur after it, the more opportunities there are for tactical events to make the evaluation incorrect and the uncertainty in the evaluation increases with every move that can possibly be made after it.

Ed: Yes, that's why so many people play chess. And IBM and other firms
show top matches. It's money as well. We poor osers.

Paul: A 5-ply search is therefore better than a 1-ply search because its terminal nodes are closer to the end of the game and there are therefore fewer unknown moves occurring after the evaluation to compromise it - a game has less time to do something unpredictable after a deep look-ahead search than it does after a short look-ahead search.

Ed: Yes of course the deeper the best, that's logical. And using of course databases for all those possibilities and a terrible good search and match mechanism. Learn a lot.

Paul: If you consider searches performed, firstly so that the end of the game always falls within the horizon of the search, then searches earlier in the game, so that some game endings fall within the horizon and others end not long after and gradually keep moving the imaginary horizon further back, so that it occurs sooner in the in the game I think you'll see what I mean.

Ed: Real chess players weigh the positions they reach. See the position as multidimensional point in some mathematical n-dim space. Yes a complete board is then one point. Nice storing isn't it and already so many times done. And so nice you have all the time to add weights to those points. Look so easily: Going backward in a match you have a tree and the nodes (n-dim points) get a weight with margin: 1233-1787. lo – hi.

You’ll get so paths back from winning matches. Is that a bad way?

Then you look in the position you have at this moment and you ask yourself how much risk do I want to take. And then you choose. Never doing something random, always with arguments, tiny ones maybe, but always using your brains. My bots neither work with random, but the signals coming from outside have noise and they change my margins, so all becomes so nicely unpredictable.

What comes in your games from the outside world? YOU! And interrupts, just events, isn’t it? Use for event handling the so easily while- select case- way other ways aren’t for me. So yes with complete event handling as well.

Maths have thought about search and match techniques, Please read about these things. In all kind of games this is a nice way.

My neural nets work in this way and learn 40,000 faster than other NNs and can do a lot more.

We certainly will make games that run fast and so find paths and other things. Yes they can see far and hear as well. They will show unpredictabilities. Do you really think my project will make bad games?

But it isn't necessary to believe me, isn't it?

Ed

Ed: This is a game isn't it? Not important if a chess match could last 200 moves to look ahead? Are you sure.

No, it would still be important, but, all else being equal, it would not be as reliable as a similar sort of search in a game that lasts 50 moves. Of course, simply taking the length of a typical game as an indication of how useful a look-ahead search is isn't adequate in itself: the type of rules used in the game will be significant. We could probably design a tactical and strategic game similar to chess with typical game lengths that are twice as long, but for which positional evaluations are just as reliable, by devising rules that make the game less volatile (i.e. subject to tactical events). Also, some individual chess positions may be more volatile than others.

Paul: No, it would still be important, but, all else being equal,

Ed. Certainly. you can loose a chess play in white 3 and black 2 not so bright moves. So you are complete right in this.

Paul: it would not be as reliable as a similar sort of search in a game that lasts 50 moves. Of course, simply taking the length of a typical game as an indication of how useful a look-ahead search is isn't adequate in itself: the type of rules used in the game will be significant.

Ed: Certainly we don't differ in our opinions here. Not only the depth but also the width, isn't it.

Paul: We could probably design a tactical and strategic game similar to chess with typical game lengths that are twice as long, but for which positional evaluations are just as reliable, by devising rules that make the game less volatile (i.e. subject to tactical events). Also, some individual chess positions may be more volatile than others.

Ed: Yes, when we want that, but also many other types of games.

When you have reached a position (all pieces), you like to know which will be the possibilities and in the way I have described you have much info. But chess players use also the weakness of the opponent, moments he looks less awake, faking it. So the game is too difficult for me. But nevertheless we can learn from it.

For instance what is hearing now, so simple, the sender puts in a struct some numbers and the bot looks in a while-select-case loop with interrupt possibilities at the struct, and sees it belongs within his hearing (distance), analyzes the sound and reacts. Also when this checking of being within earshot and circumstances is difficult, please do it in steps from rough to precise.

I don't know why others see a problem for noises and visible things and why not smells. Feeling is very simple then. But I don’t insert extra noise. It's easy to develop but know the statements will show that you can's see the wood for the trees, so make assci drawings in your sources.

And I know for sure such a game works fast, like my neural nets. But I just code in simple C as well. It's then easier to do.

Ed

Thank you all for attempting to answer my question about why minimax is useful. However, I remain seriously unconvinced that my question has been adequately answered and here's why.

When a program does a simple look-ahead to ply 5 say, it does not see anything of ply 6. This is known as the horizon effect. If your queen is "en prise" at ply 5 the program doesn't see its capture at ply 6. If the program moves towards that situation, it will not notice until its next move, by which time it may be too late. Any decent chess program addresses this problem in some way, usually by using some form of quiescence detection. This checks that the situation is not turbulent, so that you evaluation function wuill probably give a reasonable value.

A deep lookahead is clearly useful if the deeper evaluations are more accurate than the shallow ones. So, if the end of the game is seen during the lookahead then minimax is potentially useful. And if quiescence detection is used to check that the evaluation function will give a reasonable answer, then minimax is potentially useful. But even if neither of these is true minimax is still useful. I have built and analysed many thousands of game-trees to demonstrate this to my own satisfaction. The Prolog code and tables of results are available on request.

Of course I have made some "reasonable" assumptions when generating these trees and any feedback on these is most welcome. I build trees in which the evaluations of the terminal nodes are correct then I make them wrong such that the evaluation error is a normally distributed about the correct value with some standard deviation that I can set. My analysis has shown that the deeper you look ahead, the better the "ordering" of the nodes at ply 1 so your chances of picking the right move improve. However, the actual backed-up values at ply 1 are significantly wrong, though they improve with depth. This is not surprising since you are maximising on even plies and minimising at odd plies and this has a very significant effect, the effect is bigger for a larger standard deviation - again, not surprising.

What I am still looking for is a mathematically sound explanation for the fact that minimax clearly does work without needing to see the end of the game or use quiescent detection to help it. Neither is it necessary for the evaluation function to be more accurate with increasing depth though clearly this will help.

Sincerely GL7

So I've implemented minimax, and now im turning it into Negamax. But I've noticed some strange behaviors on my program. Sometimes a level 4 will lose to a level 2 game, why is that? i believe i might be doing something wrong in my min max funcitions. Heres my question: Every time I go Min, do I evaluate the board passing the OPPONENT_COLOR and do I find the avaliable moves for the OPPONENT_COLOR as well? or should I evaluate for OWN_COLOR and get teh moves for OPPONENT_COLOR? i hope im not to confusing...
thanks!
M@rty

I did find your description confusing so I'll just tell you what you should do and how to check it.

If you have implemented minimax successfully and then you implement negamax you should get exactly the same results from both algorithms. If you don't there is a bug somewhere. You can then go on to implement the alpha-beta cut-off which will allow you to search much deeper in the same amount of time. Once again running the alpha-beta on the same tree to the same depth will give exactly the same results as minimax or negamax, so this should help you debug your code.

For negamax you should evaluate the positions from the point of view of the player who just moved. Then you maximise, and then you reverse the sign of the evaluation when you pass it up to the previous ply in the tree. Reversing the sign makes the evaluation correct from the other player's point of view. Try this with a small tree with pencil and paper to see how it works, then run your negamax on the same tree to check that all is well.

Sincerely GL7
(Your local tree surgeon.)

Hello David George Elsdon

David George Elsdon: What I am still looking for is a mathematically sound explanation for the fact that minimax clearly does work without needing to see the end of the game or use quiescent detection to help it. Neither is it necessary for the evaluation function to be more accurate with increasing depth though clearly this will help.

Ed: When you go 5 deep of course you have problems. What do you do. You take a large computer and run there a lot of games to positions you can value as winning for one party. You do this with the minmax tool.

You get then a large tree and in fact a network - Different ways to a same position of the pieces. Now you know the results and you go upward.

Suppose a left child has a value of 10 and the tight child 12 then the parent gets value, a margin 10-12. Also children with margins give the parent such a margin.

I know I will play as goof as possible - max but I play for the opponent as well that he plays as strong as possible. So you'll keep then small margins. But in general some plays have weak sides and then your program becomes more complex.

But it's true extremely good players can lose from nuts. My way of winning a chess game. I have not the patience for tactical playing but I like the strategy. And I think that's in chess strange.

Resume:
The idea is play on a large computer till you know enough.
Shift the score upward in the tree to know the values higher there.
So typically wit a learning phase. Not nice in many games?

But in normal computer games we don't meet so many moves to a decisive moment. What do you think?

For instance a good way is always working from rough to precise. In many games you have a lot of freedom in the beginning. You fill this with the character of the but, of course they differ isn' it. Fitting somewhere, no computing and move already, later more precise. And still this is minimax.

With more you have to survive all opponents. Normally a hurt bot stops fighting and then you can think of a nice algorithm. Else kill everyone and you get a rather stupid game, I think. Too many games do the same. What do you think, David George. Nice questions you've posted.

Sorry Marty - When you go 4 deep you arrive maybe at the brink of a disaster, while with 2 deep the sky is so wonderful blue...

Ed

I have an idea for increasing the rate of chess tree searching and I need to write a chess program.

Does anyone know where I can find source code for a chess evaluation function? Ideally, it would be in Pascal. I can use C, but find that Pascal more closely matches how my brain works. It does not have to be an amazing evaluation function. In fact, I have a good idea of what logic it would contain - adding up piece values, freedom of movement, defensively arranged pieces, pieces in proximity to king, etc.

I just don't want to bother writing an entire evaluation function. I don't need code for the search tree - I intend to use a modified version of Shannon Type B and I'll do it myself. However, if anyone knows of a program that uses Shannon Type B, that's fine.

Paul.

piep, piep.

With google you can find a lot, for instance this url

http://home.t-online.de/home/p_rosendahl/

I found it with: strong chess "open source"

Ed

http://sourceforge.net/projects/faile/

There's quite a few chess projects on the SourceForge.

Sincerely GL7

Hello David

http://freshmeat.net/search/?q=chess

You find many here as well, so you have choise. Faile is surely
a possibility.

You could even assemble them, grin.

But for a serious chess program, oh so bad, you need an....
a database with old strong games.

Ed

Thanks ed and dave.

I don't need a program, which is very strong - I just want to see at this stage if I can improve its efficiency a lot. I will look where you directed.

Hello all. I'm new to Ia and I'm learning about this. It's very cool.
My question is this :
The MiniMax algorithm suposted be used by One play of computer, and other play of player.
But, if in my game, exist 2 players ? This algorithm is the best to be used in this situation ????

In this case, you need not an algorithm like that.
You need only to set the computer able to check the moves possibilities, the players do the rest.

can someone write me a tic-tack-toe game in any language that starts with the letter c ( c#, c++, c)

i dont get how you write it i understand the concept though

thanks alot,
me

Crowned pieces can jump over blank spaces and a piece in one turn. Also, need a better evaluation function. How about (12 * White_King + White_Pieces) - (12 * Black_King + Black_Pieces) ? The positional value of the board squares should be an emergent characteristic of the MinMax function with sufficient depth, imho.

In Portuguese checkers and according to the Britannica encyclopedia, crowned pieces can jump over any number of free places in any direction.

As for the evaluation function you are probably right, the one that was made is very basic. It was just to show one way of implementing evaluation functions.

It's good that you gave some thought to the game. Have you tried to modify the source and see if your suggestion improves the AI?

Cheers,
Paulo Pinto

Paulo, thanks for clearing that up. Yes, it helped greatly to use a depth of 9 and the following:

private int calculateValue (int piece, int pos) {
int value;

if (piece == CheckersBoard.WHITE ) //Simple piece
if (pos >= 4 && pos <= 7)
value = 700;
else
value = 500;
else if (piece != CheckersBoard.BLACK) //Simple piece
if (pos >= 24 && pos <= 27)
value = 700;
else
value = 500;
else // king piece
value = 1000;

return value + tableWeight[pos];
}

At least the computer is not simply giving pieces away!

Regards, Rickey

Edit: Well, looks like your function works really good with a depth of 9, too. ;)

Half a year ago, I decided to make my own Gomoku game
using Minimax.

The Minimax is functional, generated tree is pretty huge, although scanning is fast with alfa-beta pruning even with max. deep set to 13.

My only problem is winning condition. I wrote small function that checks every move of player P in minimax and return true if this move means winning for P, false if it's not.

part of MIN_MOVE() function
.
.
if IS_WINNING_MOVE(@board, human, X, Y) then
Result := -100000;
.
.

// -100000 means very bad for computer.

part of MAX_MOVE() function
.
.
if IS_WINNING_MOVE(@board, computer, X, Y) then
Result := 100000;
.
.

// 100000 means victory for computer.

Problem is: When MIN_MOVE() returns -100000 to MAX_MOVE(), it won't pass to upper levels, because MAX_MOVE() is choosing highest values from MIN_MOVE() and -100000 is far away of them.

Please, tell me how to distinguish these winning conditions, it would help a lot. Thanx!

TheAlien: Could you explain how did you make the evaluation function? Tnx...

One time, the function returns a value of a move:
return EvalGameState(game);

and another time it returns the move itself:
return best_move;

why? :/

and what exactly does "Value(move)" do..? i mean ok, EvalGameState gives a score for the current GamePosition, but shouldn't Value() be more like EvalGameState(ApplyMove ...) or something like that?

this "pseudocode" isn't unequivocal at all

Please please can someone help me? I really am a damsel in distress!
I need the source code using the minimax strategy in prolog for tic tac toe.

Hope someone out there can help me soon.
Thanks, Kez.

Hi.

I didn't understand to what bestMove fisrtTime is initilialized.
Before we use it first time as a parameter to Value function it should be initialized to somthing.

thank you in advance

After reading this article as well as several others I decided to make a quick JavaScript tic tac toe game. I am pretty sure that there is nothing wrong with the rest of the code, but that there is either something wrong with my A) evaluation, or B) negamax code.

Here is the page that I made for the tic tac toe game:
http://digitalcs.net/t3.3.htm

Thanks

First off, I have never written minimax code. Indeed, I have not had an actual programming
class in over a quarter century (anyone remember the PET and Vic 20?). This has not yet
kept me from writing Javascript to do what I darn well please, but minimax is a brick wall.
So far.

Here's my problem, beyondjust wrapping my brain around the basics of writing such a
function:

The game I developed has multiple action points per turn that can be spent in different
ways, provided proper conditions are met, of course. Also, the order of actions can affect
the outcome, so A before B may produce a different result than B before A, though not
always. How badly does this complicate matters for writing this kind of code?

If this helps (and I am lowballing this estimate, possibly by a lot), the first player in his first
turn, provided the starting position is generic (the board can also be dynamically set by
players before actual gameplay), can easily choose from between at least 250 possible
end-of-turn positions. Compare that to white, in chess, who has 20. By mid-game, the
numbers can probably reach 400-600 options per turn for each player, though at every
stage most can be eliminated out of hand.

After reading your tutorial I made the tic tac toe and checkers program I added 2 variables

- 1 to scale the influence of the board values
- one to scale the value of the opponents pieces

using these 2 variables you could create a player who is more or less a positional player versus a material player. By changing the relative value of the opponents pieces you can make a more suicidal vs. conservative player.

Nice tutorial, I had to go through it a bit but rarely do things work out this nicely for me first time through.

Hi,
I've got a question regarding applying minimax to tic-tac-toe. This involves using no heuristics and creating the full tree of all possible play. If we take the possible squares as :-
A | B | C
- - - - -
D | E | F
- - - - -
G | H | I

From the start of the game the first player could place an x in any of A-I. If you use minimax to determine where it should place its move, then it could be any of them as from this position all lower nodes will have an equal value ie. favourable=1. So to get the choice of where to play first and not always the same square, is it as simple as choosing a random square?
Also as we move down the tree (ie. as the game progresses) there will be other circumstances where lower nodes will have the same favourable value (ie. 1), so again at this point is it a case of picking a random lower node from the favourable ones?

More generally, are my questions above valid or am I missing something fundamental about assigning values to the various nodes of the tree? If so could someone try and correct me.