block diagram and software description, as well. Or, you can go to the electronic museum: Getting started with thermionic valves!Although a human player will only concentrate on 'reasonable moves', it is very difficult for the computer to do that. It will probably have to explore all possible moves (to a limited lookahead, of course), though this is not necessarily a drawback as it has a superior calculating power. The algorithm for a computer program can chiefly contain the following routines:
A procedure to find all possible moves for a single player from a given point in the game. Allowable moves are restricted by the edges of the board and by the presence of other pieces. Promotion, 'en passant' capturing, and castling, in particular, complicate matters. A procedure to assess each move. A (more or less) internationally agreed standard on the value of each piece is availiable for all but one of the pieces: Obviously, the King should have a very high value when being threatened (in order to avoid an exchange with any number of pieces), but a smaller value when being defended- this is to prevent an excessive number of pieces gathering around their own King. The ratio of these two values affects the computer's strategy (defensive/ attacking.) If the Queen has been captured, pawns acquire an increasing value the closer they get to the promotion line.The number and type of pieces being supported or being capable of being captured by the piece which has just moved is a good starting point for awarding a mark to the move. However, the number of pieces supporting or threatening the piece which has just moved, and its own value should be taken into account, as well. The move may also block support/ capturing possibilities for other pieces, such as Queens, rooks and bishops which have another piece to a directly opposite position (with respect to the piece which has just moved.) Considering this blocking action will only affect computation time marginally. Even though it may seem logical that such masking will become apparent (and get accounted for) during the subsequent opponent move, there is an an excellent reason not to count on this, as will be explained shortly. Rather than evaluating the absolute advantage (or otherwise) of a move to a specific position, it is best to consider the difference of scores between the intended and the former positions. This will aggravate the computer's time and, again, may look superfluous, but it pays dividents to opt for as sophisticated an algorithm as possible: Increasing the level of the lookahead by a single move for one player may well increase the execution time thirtyfold!
This is all very well as far as 'positional' advantage is concerned, but the 'manpower' advantage must be considered, too. The value of a captured piece should be added to the positional score, after being multiplied by a suitable coefficient, in order to obtain the composite score. To encourage the capture of unsupported pieces, this coefficient should clearly be greater than unity- its exact value will also determine how defensive a game the computer will play. The aggregate score for a combination of moves is obtained by adding the partial scores for each move by one player while subtracting the associated scores for the opponent. A procedure to store previous moves and partial scores during lookahead. A procedure to pick out the best move (after a suitable level of lookahead.) Simply choosing the highest score will be no good; that would involve one side doing everything perfectly while the opponents make a complete mess of the game- they almost certainly will not oblige! Rather, for each combination of your moves, the opponent's combination of moves which minimizes your advantage must by found, and your optimal move selected out of those minimized scores only. The time (and space) required to do that is basically proportional to the average number of possible options for one move by a single player, raised to the power 'L', L being the lookahead level. This algorithm is ideally suited to parallel processing, since exploring the lookahead tree of a given primary move is independent of performing the same task for a different primary move (other than comparing the partially best scores.) At the beginning of the game, the amount of lookahead required to obtain reasonable results is too great, so the above algorithm will fail, unless combined with a database of openings. Finally, it is possible to use the computer for variants of the conventional game, such as different board sizes, different numbers and types of pieces and so on. Even a lookahead of one move for each player could require almost a thousand move combinations (or more), and clearly a deeper lookahead than that is necessary for a reasonable performance, so a machine code implementation and excellent programming skills look indispensable.
This site is also accessible via www.netword.com after typing in the netword foti.simulation