Game play

A problem that arises in playing many games is choosing the best move from several possibilities.

This involves being able to evaluate any given position.

It also involves look-ahead.

• You think about the effect of making a given move in a given position, by looking ahead to the position that results and the moves your opponent could make from that position.
• This is just a different version of the same problem.
• Hence recursion can come into the picture.

You can look ahead for several moves. The more you look ahead, the better the decision you can make - but the number of possibilities gets enormous very quickly!

Algorithm: (not Ada code)

	function findgoodmove (board, side, bestmove, depth) return integer is
       	begin
		if (depth=0) return evaluateboard(board)
		newside := black
		if (side=black) then newside=white
		moves() := best moves
		for i in 1 .. (number of best moves) loop
		   newboard := changeboard(board, moves(i))
		   score(i) := findgoodmove (newboard, newside, dummy, depth-1)
		end loop
		tomove := the move with the highest score
		bestmove := move(tomove)
		return score(i)					
	end findgoodmove;

	begin	-- main program
		findgoodmove(board, black, themove, 6)
		put("Black moves at");
		put(themove);
	end main;