《计算机科学导论》课件Unit 15Artificial Intelligence讲解材料.ppt

* (1) Search method There are two generals search methods: brute-force search and heuristic search. Brute-force search, also called blind search and uninformed search, can be described in one sentence: “Try every step (state) till the results are found”. For example, give a set of numbers and find all prime numbers. Breadth-first search and depth-first search are the brute-force techniques in which a special data structure is utilized. The data structure can be a tree, a graph, or other, which has been discussed in the previous chapter. Searching * (1) Search method Heuristic search, also called informed search, use some outer hint or direction. For example, the solution may be known in a subset of search space, and the algorithm performs searching only within the subset. It is well known that Deep Blue, a chess-playing computer developed by IBM, defeated world class champion, Garry Kasparov, on February 10, 1996 under regular time controls. Deep Blue was then heavily upgraded?and played Kasparov again in May 1997, and won the six-game rematch of 3?–2?, under standard chess tournament time controls. This proved to be a landmark event in the history of artificial intelligence. Searching * (1) Search method Deep Blue versus Garry Kasparov match is still cited as the symbolic turning point. The algorithms of Deep Blue were based on brute-force search. It can prejudge each possible chess position, evaluate it, and then choose the optimal position. Within one second, it can evaluate 200 million chess positions. The architecture used in Deep Blue was applied to financial modeling, data mining, and molecular dynamics. It is a massively parallel powerful supercomputerwith 30 nodes, with each node containing a 10 MHz P2SC microprocessor, enhanced with 480 special VLSI (Very Large Scale Integration) chess chips. Searching * (1) Search method However, the focus of chess play has now been shifted to software chess programs rather than using dedicated ch