The Minimax and Alpha Beta

As usual, a change of plans. And I cancelled my guitar lesson last night. Way too much to do. It worked out well though. I found myself focusing on the minimax search. Minimax is one of the worst searches, but needs to be done first for the experience. It's better than the simple go to all the leaf nodes and pull back the highest score though. The reason why it's the worst is because it still evaluates every leaf node, so you get no performance enhancements. But the improvement it gives you over the "what's the best leaf node" is that it assumes your opponent would make the best move. For example, my previous exhaustive search would work as follows:

9
9 6 3
987 654 321

Since it would go as deep as it could and simply pull back what it evaluated as the best move at that ply, deciding that's the best line. With minimax, it assumes that your opponent will make the best move as well, leaving you having to play the worst best move. That would mean:

7
7 4 1
987 654 321

Which in that example still leads you to the same move, but if the tree were as follows:

6
6 4 1
876 594 321

That previous code would have played the "9" line, instead of the "6" line that it will now choose. So, this causes the engine to make better moves. As soon as I had this working, it was time to move on to Alpha Beta pruning. What is that? It's what kept me up until 1:15AM and is making me very cranky today!

Alpha Beta would handle that last tree as follows:
6
6 - -
876 5-- 3--

This will speed up your search and allow you to go deeper into the tree. The way it works is that it says (Hey, you're less than my minimum from another line, so assuming that my opponent was making the best moves I know that this line is inferior to the line that I've already identified as my best, so why waste time checking the rest of the moves in this variation (branch). )

So I'm working on that now. What drove me crazy is that the later it got, the better I understood it... and the more I needed to get to bed. It felt like one of those no-win situations. Next Thursday is coming up quickly...

So tonight I'm praying that I can get Alpha Beta finished and then get the quiescent search coded. The reason I held off on the quiescent search is that I did implement it, and it slowed things way down. I think it was too much for it before implementing a pruning technique such as Alpha Beta. Let's hope I'm right about that.

Alright, I need to pick my brother up at 7:30 at Northampton Ford and bring him back home, then get to work. So I better get going. A new day awaits!

I hope it's a good one!

Ed.