Question

Write pseudocode to implement the paranoid algorithm. (You vs 2 other players)

Answer 1

PSEUDOCODE:

Pseudocode is an informal way of programming description that does not require any strict programming language syntax or underlying technology considerations. It is used for creating an outline or a rough draft of a program. Pseudocode summarizes a program’s flow, but excludes underlying details. System designers write pseudocode to ensure that programmers understand a software project's requirements and align code accordingly.

PARANOID ALGORITHM:

The paranoid algorithm does this by reducing a n-player game to a 2-player game.

EXAMPLE OF PARANOID ALGORITHM:

The paranoid algorithm reduces the multi-player game to a two-player game by making the “paranoid” assumption. The algorithm assumes that all opponents have formed a coalition against the root player. By doing so, regular αβ pruning is possible. This leads to a larger search depth.depicts an example of the paranoid algorithm. It is the same tree, but now the leaf nodes are evaluated in a paranoid way.

Here, the sum of the evaluation scores of Player 2 and 3 are subtracted from the evaluation score of Player 1 . A second possibility is that Players 2 and 3 ignore their own score, and only minimize Player 1’s score. In Node (b), the right child is preferred with value -3. After finding -4 as value of the first child of Node (c), all the remaining children can be safely pruned according to the standard αβ rule. The root node (a) receives value -3. In the best case, O(b d/2 ) nodes are expanded for two-player games , where b is the average branching factor and d the search depth. Sturtevant and Korf showed that the paranoid algorithm expands O b d×(n−1)/n nodes in the best case fomulti-player games, which is a generalization of the best case for two-player games. Paranoid may outperform maxn due to the larger lookahead (e.g., for Chinese Checkers or Hearts).

Because of the unrealistic paranoid assumption, suboptimal play can occur [3]. Furthermore, if an infinite amount of time would be available, the root player might assume that all moves are losing, leading to poor play. For the game of RolitTM, Saito and Winands [5] showed that for three players on the 6×6 board, the first and second player cannot gain any points under the paranoid assumption (and the third player only 1 point because he places the last stone). Usually, it is not possible to win when all opponents form a coalition. As a general observation, the deeper the search goes, the more pessimistic the value of the root becomes.