Adversarial Search and α-β pruning

Can you beat what you just created?

Photo by Andrew Pons on Unsplash

The Minimax Algorithm

As stated earlier, AIs which employ the adversarial search, play in a defensive manner, with a prime target not to win, but to minimize the loss as much as the situation allows. This is known as loss aversion. Note that in case such decisive games mentioned above, the entire game can be represented by a decision tree, where each initial decision leads to a specific, unique leaf.

  1. For each possible moves, recur down the hierarchy until a leaf is found
  2. If the current node is a leaf, do the following,

How long does it take

Say, the time it takes to expand a node happens to be a constant and is of the value c and we’ve got a tree with a branching factor of 3, i.e. each time any node is expanded, it expands into 3 more nodes (usually the branching factor decreases with depth, as in tic-tac-toe, as you’ll see later in this episode). Observe, initially there is one node, the root, nodes at level 0 is 3⁰ (=1), it expands into 3 nodes as the branching factor is 3, so at level 1 there are 3¹ nodes, in the next level each of 3 node expands into 3 more nodes, so at level 2 there are 3x3 = 9 =3² nodes. Noticed the pattern? At level d, there are 3^d nodes. If branching factor is b then at level d, there are b^d nodes.

Can we do better?

Minimax is a great leap forward for AIs competing with human counterparts but is way too naive for most of the strategic games. The fact that it expands each and every node up to the leaves makes it stumble on the ground. The AI can be taught to cut off some branches if they do not seem promising enough. This is called α-β pruning. This is not an algorithm by itself, rather like Minimax 2.0.

The Simulation

Let’s actually employ the algorithm in an actual near end tic tac toe gam and see it in action. Consider the following stage of the game, O for AI, X for human.

  • the first value denotes the number of the node as per order of traversal, like node (3, 1, 2) is the 3rd node to be visited
  • second value denotes the depth and thrid denotes number of empty slots at this stage
  • numbers on the edge also denote the depth, red numbers below each leaf denotes the final score, +/- (10-depth)
  • finally, the red circled nodes are the ones pruned

Developer, writer, artist. Total blend. Visit me at https://safwan.netlify.app/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store