1

I successfully implemented the minimax algorithm, and am looking for an improvement with Alpha-Beta.

Currently both algorithm's take an outrageously long time at a search depth of 3+, however minimax works, and Alpa-Beta is making really horrible moves. The algorithm below is based off the pseudocode found at the chess programming wiki.

Strength of current position

calculatePositionStrength()    //currently very simple
    return (My piece material - opponent's piece material)

Algorithm: chessjs.move(m) makes a move. chessjs.undo() undo's it.

var score = 0, bestMove;

function alphaBetaMax(alpha, beta, depthleft) {
    if(depthleft==0) {
        return calculatePositionStrength();
    }
    chessjs.moves().forEach(function(move) {
        chessjs.move(move);
        score = alphaBetaMin(alpha, beta, depthleft-1);
        chessjs.undo();
        if(score>=beta) {
            return beta;   // fail hard beta-cutoff
        }
        if(score>alpha) {
            bestMove = move;
            alpha = score; // alpha acts like max in MiniMax
        }
    });
    return alpha;
}

function alphaBetaMin(alpha, beta, depthleft) {
    if(depthleft==0) {
        return -calculatePositionStrength();
    }
    chessjs.moves().forEach(function(move) {
        chessjs.move(move);
        score = alphaBetaMax(alpha, beta, depthleft-1);
        chessjs.undo();
        if(score<=alpha ) {
            return alpha; // fail hard alpha-cutoff
        }
        if(score<beta ) {
            beta = score; // beta acts like min in MiniMax
        }
    });
    return beta;
}
alphaBetaMax(-Infinity, Infinity, 3);

What's wrong with my logic? Am I placing move making/undoing in the correct spots? Also, why is it so slow?

Max
  • 2,710
  • 1
  • 23
  • 34
  • Just guessing, but your evaluation function is probably too elementary to guide search space pruning - most times it will evaluate either to 0 or to the same value as in the previous board position. – collapsar Oct 30 '15 at 14:36
  • All it does is compare piece material, nothing else at the moment. I will add a random additive between 1 and 0 to see if it makes a difference.... update: no difference – Max Oct 30 '15 at 14:46
  • Random additive b/w 1 and 0?? How does that work in js? And, in calculating positionStrength, this formula is obvs quite trivial. – vish4071 Oct 30 '15 at 16:29
  • `Math.random()` is used to differentiate the positionStrength, allowing certain values to be cut off. And I'm just starting the chess engine so the formula is very minimal indeed. – Max Oct 30 '15 at 16:36
  • That won't do. Say, this gives larger value to a bad move, then, even while differentiating, that bad move would be chosen. I've written an answer taking into consideration logic part. – vish4071 Oct 30 '15 at 17:17
  • Ok, 1 more thing. Are you creating and storing actual boards' scenario when making a move (through a copy of current board + move) or not. If you are not, bug can be there as well. – vish4071 Oct 30 '15 at 22:13

1 Answers1

2

The calculatePositionStrength() in your code is very trivial, and, for any AI algorithm for bot's play, it is the heart and soul of the code. If your weighing is wrongful, you just cannot even think your code would produce (even near to) optimal moves. Now, at every step where pieces are equal in game, your computation would say, positions are equal which is essentially not the case.

Now, eg. There are a large number of attack openings in chess, in which, a side gives up material for position (called Gambits). Your engine would, in that case say that the position of that side is weaker, which is essentially not the case.

A few things that you can include in your weight calculation functions can be:

  • Yes, of course, material strength is one of the most important things.
  • Number of squares potentially occupied by pieces of any side. eg. A knight on f3 would potentially occupy any of the empty 8 squares (h2,h4,d2,d4,g1,g5,e1,e5).
  • Almost all pieces are potentially stronger in the center that on the sides of the board. So, you can distribute some weight over the squares as well.
  • Also, if you are making a chess engine, I'd suggest you having a database of most common openings, positional sacrifices and end games.
  • Also, your weight must consider tactics like discovered attacks, pin, skewer, fork and this all is only possible considering point 2.

And, to conclude, good luck in developing a great chess engine. :)

EDIT: I didn't see the second part of your question. I'd say, probably the alpha-beta pruning is not able to prune off the edges it should, because the weights are not distinctly distributed. This should also improve if you implement a better weight calculation function. Also, alpha-beta pruning works well when depth of game tree is large. In small depth trees, performance difference between alpha-beta and min-max is hardly visible. So, if you increase depth of your tree to 6, even with a basic implementation, performance difference should be visible.

EDIT2: A few links:

How to implement efficient Alpha-Beta pruning Game Search Tree?

https://chessprogramming.wikispaces.com/Alpha-Beta

Alpha-beta pruning for Minimax

EDIT3: Depth 3 means, you make a move, your opponent makes one and then you make one. Lets take an example. Your bishop is on c1,Knight on d2,enemy pawn on d5 and enemy knight on h6. You make a move, Ne6. Opponent makes move pawn takes knight. You move bishop takes knight. Now, in the next move, if enemy knight on h6 is supported by any piece (pawn/bishop etc) your bishop is gone, but that is move 4, which, your position calculation function is unable to understand. According to it, its an equal trade of pieces. Say, no move order in next 3 moves give you any advantage in material, so, this move order is likely to be selected, which you say is a stupid move (obvs it is), but your alpha-beta pruning is not to blame here. Now, if this Nf6 is selected, your knight is a goner and on the next move, its again a new board and a new situation. So, if you try to understand, you will. I rest my case here.

Community
  • 1
  • 1
vish4071
  • 5,135
  • 4
  • 35
  • 65
  • This doesn't really answer the question why the alpha-beta is making stupid moves/is slow. The position strength is currently very simplistic because I just started yesterday, and will look into implementing a better one once the search algorithm works. – Max Oct 30 '15 at 20:34
  • Actually this does. Read 1st paragraph again, and last one also. – vish4071 Oct 30 '15 at 21:12
  • By stupid moves, I mean purposefully jumping in front of the line of fire to for no reason. It has no sense of the enemy, while the min-max algorithm did. I would appreciate if you could post code, rather than just write your opinions in a paragraph. Also the suggestion to increase the depth to 6 would never work because I first need to make the algorithm work. If I was to increase it to 6, it would take 20 minutes to make a move(not even a good one). – Max Oct 30 '15 at 21:17
  • I'm not very familiar with js. Though I have experience in game-programming. And in almost every case, my min-max or alpha-beta algorithm has improved with better heuristic. But anyway, I've added a few links that can be of help to you. – vish4071 Oct 30 '15 at 22:06
  • Also, I've done another edit to explain what is the problem with depth 3 in implementation. – vish4071 Oct 30 '15 at 22:14
  • I think I've figured out why the algorithms where so slow. I blame it on chess.js `move` and `undo` methods being so slow. It may be because of the fact that chess.js is built upon string board representations. – Max Oct 30 '15 at 23:11