Minimax problem: alpha-beta not working

Started by edotorpedo October 31, 2004 09:05 AM

2 comments, last by edotorpedo 20 years, 1 month ago

Author

198

October 31, 2004 09:05 AM

Hi all, I've created a minimax algorithm for my checkers application. Minimax itself works fine, but I've implemented alpha-beta cutoffs and it ins't working... For example, it returns a different opening move with alpha-beta than from the same algo without alpha-beta. This is never supposed to happen (right?..) Here's the code


	private int MaxMove(int depth, CheckerBoard cb, int alpha, int beta) 
		{
			if (depth < 1) return cb.RateBoard(turn);
			
			ArrayList allowedMoves = cb.AllowedMoves(turn);
			int bestValue = -MAXIMUM_VALUE + 1;
			int moveValue = 0;
			foreach (Move m in allowedMoves) 
			{
				CheckerBoard newBoard = (CheckerBoard)cb.Clone();
				newBoard.MakeMove(m);
				moveValue = MinMove(depth - 1, newBoard, alpha, beta);
				if (moveValue > bestValue) 
				{
					bestValue = moveValue;
					alpha = moveValue;
				}
				
				if (beta > alpha) return bestValue;
				
			}

			return bestValue;

		}
		
		private int MinMove(int depth, CheckerBoard cb, int alpha, int beta) 
		{
			if (depth < 1) return cb.RateBoard(turn);

			ArrayList allowedMoves = cb.AllowedMoves(4 - turn);
			int worstValue = MAXIMUM_VALUE - 1;
			int moveValue = 0;
			foreach (Move m in allowedMoves) 
			{
				CheckerBoard newBoard = (CheckerBoard)cb.Clone();
				newBoard.MakeMove(m);
				moveValue = MaxMove(depth - 1, newBoard, alpha, beta);
				if (moveValue < worstValue) 
				{
					worstValue = moveValue;
					beta = moveValue;
				}

				if (beta < alpha) return worstValue;
				
			}

			return worstValue;

		}

I can't figure it out: at the start I call MinMove (with a move from max already made) with alpha = -INFINITY and beta = +INFINITY. Does anybody know what I can be doing wrong here. Nothing is wrong with the minimax, except for the alpha-beta part Thanks, Edo

Edo

paulecoyote

1,065

October 31, 2004 11:25 AM

May be should be <= and >= rather then just < and > when comparing movevalue?

Would be easier to see if you could step thru it I guess :-/

Anything posted is personal opinion which does not in anyway reflect or represent my employer. Any code and opinion is expressed “as is” and used at your own risk – it does not constitute a legal relationship of any kind.