Sudoku is one of those NP-Complete problems that brute force solutions have a problem with. Consider a board with a single blank space, we would have to work through 9 possibilities to find the right answer. For two blank spaces, we would work through 9 possibilities for the first space, and then for each of those possibilities, 9 for the second.
This simplifies to a time complexity of O(n^m) where n is the number of possibilities for each square (9 in normal Sudoku) and m is the number of blank spaces. A hard Sudoku problem with 50 blank spaces would take about 5.15 * 1047 computations, which would take longer than the age of the universe to solve with a decent computer.
This is where artificial intelligence (AI) comes into play. Think of AI less as a Skynet robot and more as a set of hacks to solve exponential problems like Sudoku. Code for this post can be found here.
Continue reading “Programming #10: AI Sudoku”
Thomas Kuhn, in his book The Structure of Scientific Revolutions, provides us with a framework for modeling the historic progression of scientific progress. Opposing the prevailing view of scientific progress as an accumulation of accepted facts and theories, Kuhn argued that scientific progress took a more episodic path, in which periods of normal science were interrupted by periods of revolutionary science.
According to Kuhn, when enough anomalies have accrued against a current scientific consensus (some level of error is always inevitable), the field is thrown into a state of crisis, in which new ideas are tried, eventually leading to a paradigm shift. Investment of time and money pure in as the new paradigm proves successful in solving old and new problems. Eventually, this new paradigm may run into intractable problems of its own and the cycle repeats.
It is with this framework in mind that we will dive into the history of Artificial Intelligence. It’s a history littered with so-called “AI Summers” and “AI Winters”, where new ways of thinking spark rampant enthusiasm, followed by rampant pessimism when the lofty promises aren’t kept. It’s the boom and bust cycle that shows up again and again throughout human history.
Continue reading “History #17: Artificial Intelligence”