Chapter 1: Introduction, Microworlds, Minimax search Flashcards
The term AI can be defined along 2 axes: Thinking/Acting and anthropomorphic/rationality. For each of the following definitions, specify the pair of the two axes (e.g. thinking, rationality:
- The exciting new effort to make
computers think… machines with
minds, in the full and literal sense - A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes
- The art of creating machines that
perform functions that require
intelligence when performed by
people - The study of mental faculties
through the use of computational
models
- Thinking / anthropomorphic
- Acting / rationality
- Acting / anthropomorphic
- Thinking / rationality
What kind of artificial intelligence is this course focusing on?
A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes.
(Acting, Rationality)
When was the term AI first coined?
1956 (Darthmouth workshops)
What did Aristotle and Leibniz focus on?
Reducing logical thinking to a formal calculus.
Aristotle (4th century BC)
Leibniz ( 17th century)
Who designed the first programmable computer, when, and who wrote the first programs for it?
Charles Babbage, designed the analytical engine 1837, and Ada Lovelace developed programs for it.
What seminal work did Turing publish, when did he publish it, and why is it significant?
Alan Turing published the seminal work “Computing Machinery and Intelligence” in 1950. It was published in the journal Mind.
The paper is considered significant for several reasons. Firstly, it introduced the concept of the “Turing test” as a measure of a machine’s ability to demonstrate intelligent behavior that is indistinguishable from that of a human. The test proposed that if a machine can carry on a conversation with a human in such a way that the human cannot tell whether they are talking to another person or a machine, then the machine can be considered intelligent.
Secondly, the paper also discussed the possibility of creating machines that can think and learn, and it argued that there is no fundamental reason why a machine could not be capable of thought and intelligence
What topic did Shannon publish on in 1950, and what important concepts did it introduce?
Computer Chess. Shannon’s 1950 paper “Programming a Computer for Playing Chess” was important because it was one of the first papers to explore the idea of using a computer to play chess, and it laid out a general strategy for how a computer could be programmed to play the game. The paper discussed the potential for using heuristics and algorithms (minimax) to evaluate chess positions and make decisions, and it also touched on the idea of using a large database of chess games to train the computer to play better
What is ‘Logical Theorist’, by whom and when was it worked on and why was it significant?
Newell and Simon began work on Logical Theorist in 1955. It was one of the first artificial intelligence (AI) programs to be developed, and it was designed to be able to automatically prove mathematical theorems. The LT program used heuristics and a knowledge representation based on predicate logic to search for proofs of theorems.
The Logical Theorist was significant because it demonstrated that a machine could be programmed to perform tasks that were previously thought to be the exclusive domain of human intelligence, such as mathematical reasoning and problem-solving. It was also an early example of knowledge representation and automated reasoning, two important areas of AI research. Additionally, it was a major step towards the development of other automated reasoning systems such as Prolog, and it also paved the way for the development of more advanced AI systems such as expert systems and decision support systems.
Who is Samuel, and what did he study?
In the 1950s, Arthur Samuel, an American computer scientist and cognitive psychologist, published a number of papers and developed a program for playing checkers (also known as draughts) that used machine learning techniques. Samuel’s program was one of the first examples of a machine learning application, predating the well-known field of Machine Learning by several decades.
Samuel’s program used a technique called “self-play” to train itself to play checkers. The program would play against itself, and after each game, it would adjust its internal parameters based on the outcome of the game. This process allowed the program to gradually improve its playing abilities over time. Samuel’s program was able to play at a level that was competitive with human players and was able to beat some of the best human players of the time.
Why are games and microworlds useful test-beds for AI algorithms, in comparison to the real world?
Games and microworlds are useful test-beds for AI algorithms because they have:
- A clear and simple structure,
- Clear goals and tasks
- Are limited and complex enough to be interesting.
Unlike games, microworlds are not focused on competition. On the other hand, real-world problems are difficult and often involve a lot of engineering which can distract from understanding the fundamental concepts of AI. Therefore, it is more beneficial to test AI algorithms on simplified problems, like games and microworlds, from an academic point of view.
When was the term Microworld coined, by who, and what are some examples of microworlds?
The term microworld was coined by Minsky & Papert in 1970’s. Some examples are :
- Block worlds: SHRDLU was designed to understand and respond to simple commands in English, using a knowledge representation based on blocks worlds.
- Expert systems: MYCIN (antibiotics) and DENDRAL (mass spectometry)
- NLP: ELIZA (psychotherapy) and STUDENT (world algebra)
How can a deterministic two-player, turn-based game with perfect information be represented? What is an important issue with this representation? Give an example of this issue.
It can be represented using a game tree. Each node in the tree represents a state of the game, and the edges represent the possible moves from one state to another. However, creating a game tree for many games is intractable, as the search space becomes too large to be represented on computers.
Shannon wrote that there are 10^120 different chess board positions possible, which is evidently impossible to represent on a computer. (It is argued this is a larger number than the number of atoms in the universe)
What is an algorithm that can be used to play two-player, turn-based games with perfect information, and how does it address the limitation of the intractability of game tree representations?
The Minimax algorithm is a decision-making algorithm that evaluates all possible future moves and assumes that the opponent will always choose the move that is the most disadvantageous for the player. The algorithm then chooses the move that results in the lowest maximum potential loss, which is where the name minimax comes from.
In order to overcome the intractability of the game-tree, it searches up-to a given depth, and then scores the (non-terminal) leaf-nodes with an evaluation function. This function judges the game-state on what is good for the current player, and what would be bad for the opponent. Moreover, the algorithm can use heuristics to prune the search space, by identifying which branches are more promising and which ones are not worth exploring.
