I generated a tree diagram of a minimax search versus an alpha beta search. Interesting to see how much gets pruned.

[JimmyRustles]

This assumes a very good move ordering... I hope my engine is somewhere in between the two

On reddit he mentioned this uses no move ordering at all, which I find impressive. How impressive will depend on the concrete position this was generated from.

That something is mentioned doesn't mean it is true.

The diagram shows a tree where the best move is searched first, so that all other moves could be refuted by a single move, and that this refutation was found on the first try. The odds that this would happen with random move ordering are less than astronomically small.

Unless, of course, all moves are really equivalent. Which is what you would get when you evaluate every position as 0. Then every order will automatically have the/a best move fist in every possible permutation of the moves, as every move is the best one. But then they are ordered by score.

It does indeed use no move ordering. Alpha beta, even with no move ordering, still produces a very high rate of beta cut offs on the first move.

Here is the source of the alpha beta function that I used to confirm that it doesn't use any move ordering:

Code: Select all

def alphabeta(board, alpha, beta, depth, abovex, abovespace, ply):
    global nodes
    if depth == 0: return evalBoard(board)
    if board.legal_moves.count() == 0:
        if board.is_checkmate(): return -9999
        else: return 0
    spacepernode = abovespace / board.legal_moves.count()
    i = 0
    for move in board.legal_moves: # loop through legal moves - board.legal_moves provides an unordered list of legal moves
        board.push_san(str(move))
        nodes+=1
        newx = abovex - abovespace / 2 + i * spacepernode
        if board.legal_moves.count() > 0: newabovespace = abovespace / board.legal_moves.count()
        else: newabovespace = abovespace
        pygame.draw.line(screen, (255,255,255), (abovex, 70 + ply * 100) , (newx, 70 + (ply + 1) * 100))
        score = -alphabeta(board, -beta, -alpha, depth - 1, newx, newabovespace, ply + 1)
        board.pop()
        if (score > alpha):
            alpha = score
        if (score >= beta):
            return beta
        i+=1
    pygame.display.flip()
    return alpha
    

[hgm]

So how do you explain that the best move in the root was searched first? You have 20 moves in the root, so without ordering that alone would be a 1-in-20 probability.

And on most other moves (except for two, as Chris correctly pointed out) you pick a cut-move on the first try (also out of 20?). This also would be rather unlikely with random ordering.

I stick to my conjecture that this is because you evaluate all positions equally, so that virtually all moves have the same score. So that virtually every permutation is in fact still ordered by score.

[Pio]

So how do you explain that the best move in the root was searched first? You have 20 moves in the root, so without ordering that alone would be a 1-in-20 probability.

And on most other moves (except for two, as Chris correctly pointed out) you pick a cut-move on the first try (also out of 20?). This also would be rather unlikely with random ordering.

I stick to my conjecture that this is because you evaluate all positions equally, so that virtually all moves have the same score. So that virtually every permutation is in fact still ordered by score.

+1

Yes, probably his evaluation is only counting pieces and their values. Of course he can be very lucky but that is highly unlikely

[JimmyRustles]

So how do you explain that the best move in the root was searched first? You have 20 moves in the root, so without ordering that alone would be a 1-in-20 probability.

And on most other moves (except for two, as Chris correctly pointed out) you pick a cut-move on the first try (also out of 20?). This also would be rather unlikely with random ordering.

I stick to my conjecture that this is because you evaluate all positions equally, so that virtually all moves have the same score. So that virtually every permutation is in fact still ordered by score.

I have to say I hadn't considered this. I checked the evaluations that were being returned and they were all 0, since I was using material-only eval and the search didn't hit any captures at depth 3.

I tried it again at depth 5 where it encounters some captures and it has a much lower rate of first-move cutoffs because of the captures.