Artificial Intelligence - A Modern Approach

Artificial Intelligence: A Modern Approach

Consider the following quotes from "Artificial Intelligence: A Modern Approach" by Russell and Norvig, Eastern Economy Edition, 2003: (If you are involved in the field of computer chess and have not read this book, I would strongly recommend it.) This textbook is not easy to read but the concepts it discusses are critical for anyone who wishes to build an intelligent system, or who wishes to have discussions about such systems.

Russell and Norvig argue that the human thought process should be studied in order to make a machine think like a human:

p. 3 "If we are going to say that a given program thinks like a human, we must have some way of determining how humans think. We need to get inside the actual workings of human minds. There are two ways to do this: through introspection - trying to catch our own thoughts as they go by - and through psychological experiments. Once we have a sufficiently precise theory of the mind, it becomes possible to express the theory as a computer program."

The field of Artificial Intelligence (often abbreviated AI) uses terms that often do not appear in the computer chess literature:

p.32 "An agent is anything that can be viewed as perceiving its environment through sensors and acting on the environment through actuators... We use the term percept to refer to the agent's perceptual inputs at any given instant. An agent's percept sequence is the complete history of everything the agent has ever perceived."

In order to determine if an agent is successful at its tasks, we need to establish what we mean by success:

p.35 "A performance measure embodies the criterion for success of an agent's behavior. ...an agent ...generates a sequence of actions according to the percepts it receives."

An agent is rational if it takes its inputs and uses them to maximize its performance measure:

p.36 "a definition of a rational agent: For each percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has."

How does a game-playing rational agent add "intelligence" to its efforts? One way is to use a special kind of measuring and counting algorithm called a heuristic function:

p.95"Heuristic functions are the most common form in which additional knowledge of the problem is imparted to the search algorithm."

But evaluating the strengths and weaknesses of a chess position is a complicated problem. Where do we begin?

p.107"A problem with fewer restrictions on the actions is called a relaxed problem. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem."

"relaxed problem" techniques can be applied to other games or puzzles and with surprising results:

p.108"A program called ABSOLVER can generate heuristics automatically from problem definitions, using "relaxed problem" method and various other techniques (Prieditis, 1993). ABSOLVER generated a new heuristic for the 8-puzzle [a variation of the famous Sam Loyd 15-puzzle, with sliding squares] better than any preexisting heuristic and found the first useful heuristic for the famous Rubik's cube puzzle."

I wonder if ABSOLVER could be used to find an evaluation function for chess.

Using computers to play games is almost as old as programming computers themselves:

p.162"Game playing was one of the first tasks undertaken in AI [Artificial Intelligence]. By 1950, almost as soon as computers became programmable, chess had been tackled by Konrad Zuse (the inventor of the first programmable computer and the first programming language), by Claude Shannon (the father of information theory), by Norman Wiener (the creator of modern control theory), and by Alan Turing. Since then, there has been steady progress in the standard of play, to the point that machines have surpassed humans in checkers and Othello, have defeated human champions (although not every time) in chess and backgammon, and are competitive in many other games. The main exception is [the game] Go, in which computers perform at the amateur level."

Claude Shannon suggested that a computer chess program need not search all the way to checkmate or stalemate. By stopping the search early and "evaluating" the winning chances of the end-positions with a reasonably accurate heuristic algorithm, a machine can play a reasonable game of chess:

p.171 "Shannon's 1950 paper, Programming a computer for playing chess, proposed instead that programs should cut off the search earlier [not proceed to checkmate] and apply a heuristic evaluation function to states in the search, effectively turning nonterminal nodes into terminal leaves. In other words, the suggestion is to alter minimax or alpha-beta in two ways: the utility function is replaced by a heuristic evaluation function EVAL, which gives an estimate of the position's utility [winnability], and the terminal test is replaced by a cutoff test that decides when to apply EVAL..."

Here is what Russell and Norvig have to say about an evaluation function for a game playing agent:

p.171 "An evaluation function returns an estimate of the expected utility [winnability] of the game from a given position... It should be clear that the performance of a game-playing program is dependent on the quality of its evaluation function. ...How exactly do we design good evaluation functions? First, the evaluation function should order the terminal states in the same way as the true utility function... the evaluation function should be correlated with the actual chances of winning... Given the limited amount of computation that the evaluation function is allowed to do for a given state, the best it can do is make a guess about the final outcome."

It seems difficult to correlate an evaluation function with the actual chances of winning when we are not looking at what each chess piece can accomplish several moves into the future.

Each chapter in "Artificial Intelligence; A Modern Approach" contains problems or exercises at the end. Perhaps this particular exercise led Vasik Rajlich to construct Rybka:

p.191"Problem 6.4: Implement move generators and evaluation functions for one or more of the following games: ...chess. Construct a general alpha-beta game-playing agent that uses your implementation. Compare the effect of... improving the evaluation function."

It seems that there is a special kind of agent that uses a database of information to accomplish its mission:

p.194-195 "This chapter introduces knowledge-based agents... Our final reason for studying knowledge-based agents is their flexibility. They are able to accept new tasks in the form of explicitly described goals, they can achieve competence quickly by being told or learning new knowledge about their environment, and they can adapt to changes in the environment by updating the relevant knowledge... The central component of a knowledge-based agent is its knowledge base, or KB."

Perhaps we should consider a knowledge based agent, as defined above, when building our evaluation function.

There is a special process, for Russell and Norvig, that enables a software engineer to build a Knowledge Base:

p. 261 "The knowledge engineering process

Knowledge engineering projects vary widely in content, scope, and difficulty, but all such projects include the following steps:

1. Identify the task 2. Assemble the relevant knowledge 3. Decide on a vocabulary of predicates, functions, and constants 4. Encode general knowledge about the domain 5. Encode a description of the specific problem instance 6. Pose queries to the inference procedure and get answers 7. Debug the knowledge base."

If you think about it, playing the game of chess involves making decisions about which move to play in an uncertain environment, with limited time available. Uncertainty can be reduced by performing deep and thorough analysis, but cannot be eliminated completely.

p.464"Probability provides a way of summarizing the uncertainty that comes from our laziness and ignorance."

p.466"The fundamental idea of decision theory is that an agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action. This is called the principle of Maximum Expected Utility (MEU)... the agent can make probabilistic predictions of action outcomes and hence select the action with highest expected utility [usefulness]."

The chess programs Rybka and Zap!Chess Zanzibar presently have the highest performance ratings (source: CEGT or Chess Engine Grand Tournament) of all chess-playing programs that do not run on customized hardware. These ratings are based on win/ draw/ loss performance in CEGT-managed tournaments between chess programs which feature several hundred games. What conclusions could we draw from these high-rated chess programs?

p.585 "If an agent maximizes a utility function that correctly reflects the performance measure by which its behavior is being judged, then it will achieve the highest possible performance score if we average over the environments in which the agent could be placed."

Perhaps a better evaluation function will lead to a better performing chess program, at least when averaged over several hundred games. Perhaps there are other reasons.

What is the value of information? What must we do when trying to act strategically in the absence of information?:

p.601 "The value of information derives from the fact that with the information, one's course of action can be changed to suit the actual situation. One can discriminate according to the situation, whereas without the information, one has to do what's best on average over the possible situations. In general, the value of a given piece of information is defined to be the difference in expected value between best actions before and after information is obtained."

[The traditional evaluation function for a chess-playing computer program lacks specific, detailed information on what each chess piece can do several moves into the future. Therefore, we must rely on "averages". This seems to explain the concept behind giving pieces points for sitting on squares.]

Russell and Norvig speak again on the value of information:

p.602 "In sum, information has value to the extent that it is likely to cause a change of plan and to the extent the new plan will be significantly better than the old plan."

What do we need to consider when we construct an agent that gathers information?:

p.603 "Implementing an information-gathering agent: A sensible agent should ask questions of the user in a reasonable order, should avoid asking questions that are irrelevant, should take into account the importance of each piece of information in relation to its cost, and should stop asking questions when that it appropriate. All of these capabilities can be achieved by using the value of information as a guide."

An agent uses sensors to perceive its world:

p.863 "Perception provides agents with information about the world they inhabit. Perception is initiated by sensors. A sensor is anything that can record some aspect of the environment and pass it as input to an agent program."

More on sensors: active and passive. It seems that the future mobility of chess pieces is a kind of probe that gathers information:

p.903 "Sensors: Sensors are the perceptual interface between robots and their environments. Passive sensors, such as cameras, are true observers of the environment: they capture signals that are generated by other sources in the environment. Active sensors, such as sonar, send energy into the environment. They rely on the fact that this energy is reflected back to the sensor. Active sensors tend to provide more information than passive sensors, but at the expense of increased power consumption and with the danger of interference when multiple active sensors are used at the same time."

An intelligent agent needs to perceive its world as well as to update the database that represents knowledge of its environment:

p.969 "Keeping track of the state of the world: This is one of the core capabilities required of an intelligent agent. It requires both perception and updating of internal representations."