Game Derandomization
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911887494479872 |
|---|---|
| author | Epstein, Samuel |
| author_facet | Epstein, Samuel |
| contents | Using Kolmogorov Game Derandomization, upper bounds of the Kolmogorov complexity of deterministic winning players against deterministic environments can be proved. This paper gives improved upper bounds of the Kolmogorov complexity of such players. This paper also generalizes this result to probabilistic games. This applies to computable, lower computable, and uncomputable environments. We characterize the classic even-odds game and then generalize these results to time bounded players and also to all zero-sum repeated games. We characterize partial game derandomization. But first, we start with an illustrative example of game derandomization, taking place on the island of Crete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16353 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Game Derandomization Epstein, Samuel Computational Complexity Using Kolmogorov Game Derandomization, upper bounds of the Kolmogorov complexity of deterministic winning players against deterministic environments can be proved. This paper gives improved upper bounds of the Kolmogorov complexity of such players. This paper also generalizes this result to probabilistic games. This applies to computable, lower computable, and uncomputable environments. We characterize the classic even-odds game and then generalize these results to time bounded players and also to all zero-sum repeated games. We characterize partial game derandomization. But first, we start with an illustrative example of game derandomization, taking place on the island of Crete. |
| title | Game Derandomization |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.16353 |