a) Initial State
b) Successor Function
c) Terminal Test
d) Utility Function
Explanation: The initial state includes the board position and identifies the player to move. A successor function returns a list of (move, state) pairs, each indicating a legal move and the resulting state. A terminal test determines when the game is over. States where the game has ended are called terminal states. A utility function (also called an objective function or payoff function), which gives a numeric value for the terminal states. In chess, the outcome is a win, loss, or draw, with values +1, -1, or 0.
d) MIN/MAX Algorithms
Explanation: Given a game tree, the optimal strategy can be determined by examining the min/max value of each node, which we write as MINIMAX- VALUE(n). The min/max value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game. Obviously, the min/max value of a terminal state is just its utility. Furthermore, given a choice, MAX will prefer to move to a state of maximum value, whereas MIN prefers a state of minimum value.
c) Alpha-beta pruning
Explanation: The alpha-beta search computes the same optimal moves as minimax, but eliminates the branches that can't influence the final decision.
a) Pruned leaves x and y
Explanation: The minimax decision are independent of the values of the pruned values x and y because of the root values.
d) Both a & b
Explanation: Alpha and beta are the values of the best choice we have found so far at any choice point along the path for MAX and MIN.
d) Any depth
Explanation: Alpha-beta pruning can be applied to trees of any depth and it is possible to prune entire sub-tree rather than leaves.
b) Depth-first search
Explanation: The minimax search is depth-first search, So at one time we just have to consider the nodes along a single path in the tree.
a) Along the path of search
Explanation: Alpha-beta search updates the value of alpha and beta as it gets along and prunes the remaining branches at node.
b) Hash table of previously seen positions
Explanation: Transposition is the occurrence of repeated states frequently in the search.
a) Evaluation function
Explanation: Because we need to cut the search off at some point and apply an evaluation function that gives an estimate of the utility of the state.
c) Transposition table
a) Depends on the nodes
a) Same as of DFS
b) Space - bm and time - bm
Explanation: Same as DFS
a) True
Explanation: Refer definition of minimax algorithm.
b) Game Tree
Explanation: An example of game tree for Tic-Tac-Toe game.
c) Multiplayer
Explanation: Zero sum games could be multiplayer games as long as the condition for zero sum game is satisfied
b) False
Explanation: Utility values are always same and opposite.
a) Competitive Environment
Explanation: Since in cooperative environment agents' goals are I conflicts. They compete for goal.
d) Only a and b
Explanation: Depending upon games it could be single agent (Sudoku) or multi-agent (Chess)
21. Is this artificial intelligence lives over the other software programs and their flexibility?
Yes artificial intelligence Games lives over the other software programs and their flexibility
Some game playing programs are getting quite good and I expect that in the long run all the best "players" will be programs. While that is wonderful and while those programs that learn to play their games get a rating of minimal intelligence from me remember that what's impressive about people is that not only can they do games, they do heuristic search, theorem proving, use natural language and cope with the real world. The real challenge is to get programs to do that. If you simply pursue techniques for game playing will you ever end up with all these human capabilities in one program?
This section looks at Berliner's program, two backprop versions by Tesauro and a temporal difference method by Tesauro. This latter program is VERY good and has found strategies that now human backgammon players acknowledge are better than some of the old humanly devised strategies
The main programs here are Arthur Samuel's, the rote learning method which is a lot like a memory based method, generalization learning which is a lot like backprop and a signature table approach that also gives you a feed-forward type network. One of Samuel's programs did beat a checkers champion and the AI community has often make a fuss over that saying that this AI program played a "championship-level" game however that expert beat the program in the next 6 games. Note too, what Samuels says: "the program is quite capable of beating any amateur player and can give better players a good contest".
This covers a number of game playing techniques, notably checkers and backgammon because so much good research has been done on these problems and because so many different techniques have been tried.
