Iteration

From Chessprogramming wiki
Jump to: navigation, search

Home * Programming * Algorithms * Iteration

Iteration [1]

In computer science, Iteration is the act of repeating instructions inside an algorithm, implemented either by the control structure of a loop or by direct or indirect recursive calls. Despite all kinds of low level loops supported by various programming languages, so called Iterators allow for traversing data container hiding the concrete implementation, i.e. linked list or array. While recursion can be considered as a special case of iteration, iteration describes the style of imperative programming in contrast to the more declarative nature of recursion. In a stricter sense, to distinguish iteration from recursion, iteration implies performing a loop inside the scope of a subroutine restricted to one stack frame in a call hierarchy, or equivalently processed by the same local iterator object.

Iterations

There are various macro- and micro-iterations going on within a chess program and/or its creator, game controller and/or learning framework, i.e. the process to develop and tune a chess program, to repeat a series of games against various opponents for learning and automated tuning purpose, to iterate over moves while playing a game, Iterative Deepening, the move loop and current variation inside a minimax depth-first search, processing exchange sequences in SEE, looking for repetitions, generating moves of one piece and for all pieces, serializing bitboards, and whatever else.

Learning

Learning and automated tuning in computer chess programming deals with algorithms that allow the program to change its behavior based on data acquired during game play against variations of itself or a variety of opponents considering the final outcome and/or the game record. Evolutionary computation, genetic programming and simulated annealing apply iterative processes where one iteration deals with one generation of the chess or game playing program.

Game Loop

Playing a game of chess versus a chess program, is a sequential, iterative process. The next iteration either starts after the program played its move and starts pondering, or the user entered a move. The Game Loop terminates when the game is finished or aborted.

Iterative Deepening

In the context of Iterative Deepening in search algorithms, an iteration refers the current call of the search routine with a certain search depth inside the loop body of the ID framework. The resulting sequence is a sequence of exact scores for subsequent incremented search depths.

Move Loop

The typical control structure inside a minimax depth-first search of a chess program is the Move Loop, a generator or iterator pattern traversing the moves of one node or position. The whole implementation details of move generation, move ordering, pruning, bookkeeping and accessing a move list, might be hidden behind an iterator object and its interface.

Search

While the "horizontal" iteration of the move loop appears in one node, the "vertical" edges of the search tree, that is actually making the move and recursively calling the negamaxed search routine for the child node, appear in the current depth-first variation started at the root. It can be considered as nested iterations of the move loops processed in all upper nodes. Keeping an explicit stack of move iterators per node further allows to reformulate the recursive search routine as iterative solution, with makes it simpler to unwind the search.

Recursion to Iteration

Tail recursion is trivially convertible to iteration [2] [3], and performed by various optimizing compilers. Since a call as used in recursion is nothing else than a jump to an address, remembering the next instruction on the stack for the return, recursion can always replaced by iteration using an array as explicit stack, an index (stack pointer) for the current nesting level, and goto instructions, as demonstrated in Iterative Search. Knuth and Moore already introduced an iterative solution of Alpha-Beta in 1975 [4] . Iterative solutions of otherwise recursive algorithms are harder to understand and to debug and tend to become Spaghetti code [5], but are required for certain parallel search algorithms like Dynamic Tree Splitting. There are jumps from inside the move loop body outside (call), and vice versa (return).

Iterative Algorithms

In computational mathematics, an iterative algorithm or method is a procedure that generates integer, fixed point, or floating point sequences and calculates Series. Iterative algorithms are used to approximate nonlinear equations [6] and to solve certain optimization problems. An iterative method is called convergent if the corresponding sequence converges for given initial approximations.

PRNG

In computer chess, iterative algorithms are used for instance directly or indirectly in initializing Zobrist keys with Pseudorandom number generators (PRNG), for instance the linear congruential generator, the Mersenne twister, the Xorshift by George Marsaglia or the KISS approach by Bob Jenkins similar as used in Stockfish [7].

Fill Algorithms

Flood-filling in bitboards is an iterative method as well, consecutively feeding back the propagated output as input. The loop terminates if either the flood stops or has reached a target set.

See also

Selected Publications

Forum Posts

External Links

General

Control flow

Iterator

Generator (computer programming) from Wikipedia

Programming languages

Iterative methods

Sequence

Series

References

  1. ↑ Iterationen from Strukturen in der Biologie (German)
  2. ↑ Recursion - Tail-recursive functions from Wikipedia,
  3. ↑ Replace Recursion with Iteration
  4. ↑ Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326
  5. ↑ Considered harmful from Wikipedia
  6. ↑ Brian J. Shelburne (1999). Zuse's Z3 Square Root Algorithm. » Konrad Zuse
  7. ↑ RKISS copyright? by Giorgio Medeot, CCC, March 07, 2011

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Iteration&oldid=6266"