Warning

This page is located in archive.

Prisoner's dilemma (PD) and its iterated variant (IPD) is a well-known problem in game theory. The goal of this project is to create and compare optimization algorithms that find a good player for a particular IPD problem instance.

An IPD problem instance is given by

- the payoff matrix and
- the number of iterations.

The payoff matrix must be set up such that the game is fair for both players. For 4 positive numbers a, b, c, and d, the matrix has the following form:

P2 plays | |||

0 | 1 | ||

P1 plays | 0 | (A,A) | (B,C) |

1 | (C,B) | (D,D) |

where in each pair (r1, r2) denotes the rewards for player 1 and player 2, respectively.

Depending on relations among A, B, C, and D, the payoff matrix may be set up in such a way that

- there is a proper dilemma,
- no dilemma is present,
- there is no dominant strategy,
- the best strategy require the decisions of the players to alternate,
- etc.

You should choose several interesting PM setups and try to find players for them.

There are many possible representations of the players/strategies:

- finite state machine (that can be encoded in a binary string),
- set of rules,
- decision tree,
- neural network,
- …

The chosen representation shall be consulted with the teacher.

IPD is a two-player game. To evaluate the quality of a player is thus possible only by playing games against other players, i.e., the quality of a player depends on the set of chosen opponents. The choice of this reference set is up to you, it may be

- a static set of predefined players,
- the other players in population,
- a combination of the above options, …

The goal is to *maximize the sum of rewards across all played IPD games*.

In no particular order:

- What is the strategy used by the best player for individual PM setups?
- How does the initialization affect the resulting best player? What if we seed the population with a specified number of copies of known strategies?
- Is it possible to evolve a player, that plays well for any setup of PM?
- Is it possible to evolve a player, that plays well against any opponent?

Take these questions as an inspiration of what you can study in your project.

courses/a0m33eoa/semestral_tasks/pd/start.txt · Last modified: 2021/11/05 14:10 by xposik