Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
Figure 11.5
Hill climbing search. downwards, whereas the south-east path involves initially climbing a small rise. My goal is at sea level and I want to expend as little e ffort as possible so I take the north-east path. It turns out, however that the north-east path is meandering and involves climbing many rises along the way. The south-east path though, after cresting the initial rise, descends quickly to the beach, dropping in elevation all the way. In the scenario described, a hill climbing search causes me to miss the quickest search path to the solution, as that path appeared initially disadvantageous. One way to accommodate such situations is to do a best first search. A best first search is just like a hill climbing search save that our choice of nodes to move to is not restricted solely to immediate descendant nodes. We also keep a record of the heuristic values of all the nodes we have searched so far and we choose from among the col- lection of immediate descendent nodes and these other nodes. This means that if, during a search, we reach a node where all the immediate descendant nodes are rated by our heuristic as further from our solution than a node we searched earlier, we can go back up the tree and search from the better rated node next. As with hill climbing, best first search involves taking the path of least resistance. The di fference is just that we expand our available choices from any given node – we no longer require that search paths always lead down a branch to the next iteration. Figure 11.6 shows how the same tree from Figure 11.5 would be searched according to a best first search. 120 Figure 11.6 Best first search. As we can see, using best first search allows us to discover, in this case, a shorter derivation for our solution state – we find a solution node at a prior iteration. Best first search is clearly the most e fficient search procedure we have examined. It should be clear, however, that it is also the most computationally expensive per node. Not only do we have to apply a heuristic function to nodes, but we also need the memory space in which to record the values of all the nodes we have searched so far. As the complexity of the tree increases, this computational expense can become significant. It is still the case, though, that the computa- tional savings in terms of the number of nodes we need to search far outweigh the computational cost the heuristic procedure incurs. There is a lot more for us to say about heuristics, so in the following chapter we are going to examine how me might employ heuristic search for a classical artificial intelligence application – playing games. 121 C H A P T E R 1 2 GAMES Now that we have a basic understanding of search procedures and heuristic functions, it is time to apply this understanding in consider- ation of automated methods of game play. This provides us with an entry point to a broader examination of how we might employ formal systems to enact functions which are taken to be constitutive of intelligence. We are also going to compare these formal methods for game play to our reflective understanding of how humans play such games, before moving on in the following chapters to a more detailed and informed such comparison with respect to the cognitive functions implicated in reasoning and language. 12.1 A SIMPLE GAME If a game is su fficiently simple, we can very easily automate a proced- ure for playing it. It is fairly trivial, for instance, to determine an algo- rithm for playing tic-tac-toe such that following the algorithm will always result in either a win or a draw. In such cases, all we need do is construct the generation tree for the game, then work backwards from the terminal nodes to determine a strategy. For instance, suppose we have a game that is played as follows. First an initial position is chosen. From that position, and each subsequent position, there are exactly three ways in which a player might move. Players flip a coin to determine who begins, then the first player makes a move, the second player makes a move and the first player makes a final move. After these three moves, the game ends in a position which is a clear win for one of the players. The generation tree for this game is easily constructed. It will have three iterations and a branching factor of three, so there will be 122 twenty-seven terminal nodes, each of which is discernible as a win for one player (white) or the other (black). The generation tree depicted in Figure 12.1 assumes we have chosen an initial position for the game and assigns to each terminal node the player for whom it is a winning position. We needn’t know the particulars of the game or its play – its form is all we’re concerned with here. I’ve merely stipulated which nodes are wins for which player for illustrative purposes. With the information depicted in Figure 12.1, we can work our way back up the tree and determine who the chosen initial position will be a win for. Let’s suppose, for instance, that white wins the toss and is to make the first move. That means that on the last iteration before the termi- nal nodes, it is white’s move. A node at that iteration will count as a win for white – given that it is white’s move – if there is at least one descendant node which results in a win for white, otherwise it will count as a win for black. In other words, if white can move to a winning position and it is white’s turn, then the position is already a winning position for white. If, however, the only available moves are to positions which are winning positions for black, then the position is already a winning position for black. Similarly, at the previous iteration it will be black’s turn. A node at that iteration will count as a win for black if there is at least one descendant node which counts as a win for black, and will count as a win for white otherwise. Figure 12.2 applies this procedure to the tree depicted in Figure 12.1 and demonstrates that if white wins the toss, white has a winning strategy available. This is not, however, to say that white will win the 123 Download 1.05 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling