课程: AI Algorithms for Game Design with Python

免费学习该课程！

今天就开通帐号，24,700 门业界名师课程任您挑！

Time complexity of brute-force approaches

Time complexity of brute-force approaches - Python教程

课程: AI Algorithms for Game Design with Python

开始一个月试用 购买团队方案

Time complexity of brute-force approaches

“

- [Instructor] 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 three, 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 smaller number. Let me show you why. In our example, let's pay attention…

内容