From the course: AI Algorithms for Gaming

Unlock the full course today

Join today to access over 22,600 courses taught by industry experts or purchase this course individually.

Time complexity of brute force approaches

Time complexity of brute force approaches - Python Tutorial

From the course: AI Algorithms for Gaming

Start my 1-month free trial

Time complexity of brute force approaches

“

- Now let's briefly talk about the complexity of this brute force approach. Notice that the tree for tic-tac-toe grows with a large branching factor at the beginning, and this branching factor goes down because less moves become possible as the game progresses. So at the first level of this tree, we have to analyze just one state of the game, the current state. Next, we have nine places where we can place our mark. Then the opponent has eight options, then we have seven. And so this number goes down one move at a time. That's why the total number of games we'd have to evaluate to produce the first move in tic-tac-toe is nine factorial. Which is a bit over 360,000. That's not so bad. Pretty much any desktop computer, tablet or smartphone today is capable of computing this whole tree in less than five seconds. And there are even better news. This is a pessimistic estimate. So we may aim for an even…

Contents