Howdy Everyone, I have been working on creating an AI for this checker game variant. It is my first attempt at AI through deep search and I am running into some troubles. There are a couple of points about the minimax algorithm that I am not quite understanding. How the evaluation function scores the games is a little puzzeling. I have read several articles that say to score game boards favorable to MIN as negative values, and game favorable to MAX's position as positive values. And a value of zero has neutral strength for both players..... Why score the boards that way? Why not just score both MIN's and MAX's positions as positive values? with the greater value representing that players greater advantage? How does that change the algorithm? The following will work with both MIN and MAX as positive score values, yes? Also, please note the depth cutoff in MaxMove AND MinMove .... is that correct? Should the depth cutoff ONLY be in MaxMove? Thanks for the help everyone! MaxMove(myPos, theirPos, depth) if( depth == maxDepth || endgame(myPos,theirPos) == true) { return score(myPos, theirPos); } bestScore = 0 bestMove = null movelist = generateMoves(myPos, theirPos) for(move in moveList) { myNewPos = makeMove(move, myPos) score = MinMove(theirPos, myNewPos, depth++); if(score > bestScore) { bestScore = score; bestMove = move; } } if(depth == 0) { return bestMove; } return bestScore; END MaxMove MinMove(myPos, theirPos, depth) if( depth == maxDepth || endgame(myPos,theirPos) == true) { return score(myPos, theirPos); } bestScore = 0 movelist = generateMoves(myPos, theirPos) for(move in moveList) { myNewPos = makeMove(move, myPos) score = MaxMove(theirPos, myNewPos, depth++); if(score > bestScore) { bestScore = score; } } return bestScore; END MinMove

The whole point of scoring in Minimax is to arrive at a single value for that branch of the tree. The higher the value of that score, the more favorable it is. The Min and Max +/- scoring is intuitively obvious. It's like a numberline of a pro/con list. This board is a win (or favorable position) so add one. This board sucks so subtract one. Wherever your little numberline ends up (be it positive or negative) is the final score for that whole branch of the tree. If a branch has many potential win boards under it, all of those +1s will add up to a large (>0) value. A lot of crappy boards will lead to a negative value (<0). If you were to use big and little positive values, you would have no idea if you were looking at one good board (e.g. +5) or a lot of bad ones (+1 * 5).


I think you may want to back out of the code for a minute and study why Minimax is designed the way it is. Use TicTacToe for example and only score win/lose/draw conditions.

Quote:

Original post by gfrommer How the evaluation function scores the games is a little puzzeling. I have read several articles that say to score game boards favorable to MIN as negative values, and game favorable to MAX's position as positive values. And a value of zero has neutral strength for both players..... Why score the boards that way? Why not just score both MIN's and MAX's positions as positive values? with the greater value representing that players greater advantage? How does that change the algorithm?

You can compute the strength of each player and then subtract them to compute a score. The evaluation function is supposed to answer the question "Who is winning?". If you look at a chess position and you want to know who is winning, you would probably count material and say something like "white is up a pawn"; we encode that usually as the score being +1.

Quote:

The following will work with both MIN and MAX as positive score values, yes?

Not sure, but probably not. When you have something called "score", what does it represent?

Quote:

Also, please note the depth cutoff in MaxMove AND MinMove .... is that correct? Should the depth cutoff ONLY be in MaxMove?

Yes, it is correct. Once you start experimenting with extensions (it can be argued that a forced move shouldn't count as a move at all), some leaves will have white to move and some black.

You should probably rewrite your code and use the NegaMax idea: If you use the convention that a positive score means "looking good for the side to move", you'll only need one function, and not two.

Thanks, you've given me new insight into how the evaluation function works. The rules of my game include a point score to determine winner or loser, I think I was confusing that score with what value the evaluation function is suppose to return. The negative/positive numbers make much more sense now.

So my minimax engine works better now, but not super. I think if I can increase my search depth that would help. A good question I have is, which will do more to increase the game play of my AI engine, to refine my evaluation function or to make deeper searches? My guess is deeper search, but at the same time the search is only as good as the results from the evaluation function.

I am now working on converting my minimax to negamax.... this is super fun code! I mostly do web development, and I haven't got into the nitty gritty of real computer problem solving in some time.
Aside from simplifying the code, does negamax give any better performance? I know alpha-beta pruning goes a long way. That will be my next optimization.

Thanks everyone!

Quote:

So my minimax engine works better now, but not super. I think if I can increase my search depth that would help. A good question I have is, which will do more to increase the game play of my AI engine, to refine my evaluation function or to make deeper searches? My guess is deeper search, but at the same time the search is only as good as the results from the evaluation function.

On the surface it would seem like a deeper search should yield a better result, but this is actually not true due to the "horizon" problem. The problem is, unless you reach a leaf node, you can't know how deep a particular branch is. There is always a chance that, even though the tree up to this point has tended to favor one player, if you just go one ply deeper the result could suddenly change. Only by reaching a leaf can you know for sure what the final outcome would be. Of course this is not usually feasible except for games with relatively shallow game trees (such as Tic Tac Toe). So concentrate on your evaluation function. You obviously want to go as deep as reasonably possible without spending too much computing time, and yes pruning can help speed things up, but just adding an arbitrary extra number of plies is not going to increase the accuracy of your AI. As far as the performance of negamax vs minimax, as I recall they should be pretty much identical.

That's great insight! So you're saying a more robust evaluation function will give a better AI because of killer moves that can happen just out of the search depth.

So from what I understand, the evaluation function produces an answer to the question, who is currently winning the game min or max. How much do I want to tweak my evaluation function to benefit various game strategies? I feel like the more I add code to the evaluation function that promotes specific strategies the more I am boxing my search in to only find good moves in what my limited human strategies thinks is beneficial. I suppose I am wrestling with the limitations of making a depth limited search.

Maybe I should create an opening book to deliver the game into my negamax engine after the game shifts into a particular strategy. And then set my evaluation function to benefit that particular strategy.

Also, I know the more I add to my evaluation function, the longer my searches will take, so that is a consideration on how robust it should be. My game produces around 40 possible moves each turn for the first ten turns, then it cuts down some.

Thanks everyone!

Quote:

Original post by CodeMunkie Quote: So my minimax engine works better now, but not super. I think if I can increase my search depth that would help. A good question I have is, which will do more to increase the game play of my AI engine, to refine my evaluation function or to make deeper searches? My guess is deeper search, but at the same time the search is only as good as the results from the evaluation function. On the surface it would seem like a deeper search should yield a better result, but this is actually not true due to the "horizon" problem. The problem is, unless you reach a leaf node, you can't know how deep a particular branch is. There is always a chance that, even though the tree up to this point has tended to favor one player, if you just go one ply deeper the result could suddenly change. Only by reaching a leaf can you know for sure what the final outcome would be. Of course this is not usually feasible except for games with relatively shallow game trees (such as Tic Tac Toe). So concentrate on your evaluation function. You obviously want to go as deep as reasonably possible without spending too much computing time, and yes pruning can help speed things up, but just adding an arbitrary extra number of plies is not going to increase the accuracy of your AI. As far as the performance of negamax vs minimax, as I recall they should be pretty much identical.

Quote:

Original post by gfrommer So my minimax engine works better now, but not super. I think if I can increase my search depth that would help. A good question I have is, which will do more to increase the game play of my AI engine, to refine my evaluation function or to make deeper searches? My guess is deeper search, but at the same time the search is only as good as the results from the evaluation function.

This depends on the game, but if you still haven't implemented alpha-beta, you should definitely try that. I don't think a better evaluation function will give you nearly as much playing quality.

Quote:

Aside from simplifying the code, does negamax give any better performance?

No. But code simplicity is very valuable.

If you haven't seen it already, you should visit Bruce Moreland's website.

The experience of chess programmers around the world is that greater depth generally trumps better position evaluations and that the horizon effect is greatly minimized using quiescent searches. The data structures used in chess engines primary improve search depth, rather than improve position evaluation.

Even though a position may be theoretically better or worse given an ideal position evaluator, the player (A.I. or Human) has to be able to prove it or else all that theory is for nothing.

Your best bet at proving the superiority or inferiority of a position is to search as deep as you can, showing that it is forced up to depth D

Clearly there is a threshhold point. Yes its true that you dont want a box-of-rocks for a position evaluator, but you shouldn't sacrifice search depth in the name of better position evaluation unless the enhancement to the position evaluator is very significant. The good news is that most games have a large enough branching factor that you can do quite a bit of position analysis for the sacrifice of a single ply.

But think Pareto's Principle. As you incrementally add knowledge to the position evaluator, the improvements that you can make to it will exhibit diminishing returns.

Quote:

Original post by Rockoon1 But think Pareto's Principle. As you incrementally add knowledge to the position evaluator, the improvements that you can make to it will exhibit diminishing returns.

I like this tip a lot. Thanks! I've got my engine to make a complete 7 ply search in around 30seconds, with my games branching factor at about 30+/-. The game is playing moderatly well, but its still quite beatable. My gut is telling me I need to add some more logic to the evaluation engine to focus differently during opening/mid game/end game.

I think adding a transposition table will help, especially if I preload it with 500megs worth of game positions/search results. But I want to nail my evaluation function before I create the transposition table.

------------------------

One question about Alpha/Beta searches before I wrap this up. In standard minimax processing loop, the line containing the A/B cutoff usualy goes

if(alpha > beta) { return alpha; } // MAX
if(beta <= alpha) { return beta; } // MIN

My question is regarding the use of less-then vs less-then-or-equal in the MIN cutoff, and alternatly the greather-then vs greater-then-or-equal in the MAX cutoff. What effect does leaving off the equal clause of those operators have?
What is the proper Alpha/Beta implementation of those?

This thread has really helped my game AI, I appreciate the advice everyone!!!!! I can't wait to get my game online for everyone to try! :)

Greg

The condition for cutoff should always include equality. You should think of alpha-beta as a function that returns the exact minimax value if it happens to be higher than alpha and lower than beta, but if it is outside of that window, it only tells you that it is less or equal to alpha, or greater or equal to beta.

You should be able to get much deeper than 7 in 30 seconds on a modern computer. Start by implementing some move-sorting heuristics (killer move, history heuristic). Transposition tables are very important. Make sure that their entries include which move was best (or created a beta cutoff), and then try that move first whenever you visit this node again.