Geodesic
Police and robber game on infinite chessboard
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 3, pp. 3-20.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is considered two variants of the game "Policeman and a robber" on an infinite chessboard that is a graph giving a regular partition of the plane into squares. Heuristic and precise definitions of the concepts "the initial state is winning for the pursuer" and "the initial state is winning for the evader" are formulated. Then, criteria for determining if a given initial state is winning for the pursuer or for the evader is given.
Keywords: game on graphs, integere net, "Cops$\&$Robber" game, qualitative problem, pursuit problem, evading problem, strategy, alternative. 
@article{MGTA_2023_15_3_a0,
     author = {Abdulla A. Azamov and Fatxull {\CYRA}. {\CYRK}uvatov and Hasan U. Tuyliyev},
     title = {Police and robber game on infinite chessboard},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {3--20},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a0/}
}
TY  - JOUR
AU  - Abdulla A. Azamov
AU  - Fatxull А. Кuvatov
AU  - Hasan U. Tuyliyev
TI  - Police and robber game on infinite chessboard
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2023
SP  - 3
EP  - 20
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a0/
LA  - ru
ID  - MGTA_2023_15_3_a0
ER  - 
%0 Journal Article
%A Abdulla A. Azamov
%A Fatxull А. Кuvatov
%A Hasan U. Tuyliyev
%T Police and robber game on infinite chessboard
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2023
%P 3-20
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a0/
%G ru
%F MGTA_2023_15_3_a0
Abdulla A. Azamov; Fatxull А. Кuvatov; Hasan U. Tuyliyev. Police and robber game on infinite chessboard. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 3, pp. 3-20. http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a0/

[1] Azamov A.A., Osnovaniya teorii diskretnykh igr, Institut matematiki im. V.I. Romanovskogo, Tashkent, 2011

[2] Azamov A.A., “O zadache kachestva dlya igr prostogo presledovaniya s ogranicheniem”, Serdika (Bo'lgarsko matem. spisanie), 12:1 (1986), 38–43 | MR | Zbl

[3] Azamov A.A., “Ob alternative dlya differentsialnykh igr presledovaniya-ubeganiya na beskonenchneom intervale vremeni”, Prikl. mat. i mekh., 50:4 (1986), 561–566 | MR | Zbl

[4] Azamov A.A., Kuchkarov A.Sh., Kholboev A.G., “Igra presledovaniya-ubeganiya na rebernom ostove pravilnykh mnogorannikov. I–III”, MTIiP, 7:3 (2015), 3–15 ; 8:3 (2016), 3–13 ; 11:4 (2019), 5–23 | Zbl | Zbl | Zbl

[5] Azamov A.A., Ibaidullaev T., “A pursuit-evasion differential game with slow pursuers on the edge graph of simplexes. I”, MTIiP, 13:4 (2020), 7–23 | MR

[6] Aizeks R., Diffrentsialnye igry, Nauka, M., 1967

[7] Blagodatskikh A.I., Petrov N.N., Konfliktnoe vzaimdoistvie grupp upravlyaemykh ob'ektov, Izhevsk, 2009

[8] Grossman I., Magnus V., Gruppy i ikh grafy, Mir, M., 1971 | MR

[9] Krasovskii N.N., Subbotin A.I., Pozitsionnyem differentsialnye igry, Nauka, M., 1974

[10] Kuchkarov A.Sh., “Zadacha prostogo presledovaniya-ubeganiya v share rimanovogo mnogoobraiya”, Matem. zametki, 85 (2009), 204–213 | DOI | Zbl

[11] Neiman Dzh., Morgenshtern O., Teoriya igr i ekonomicheskoe povedenie, Nauka, M., 1970 | MR

[12] Petrosyan L.A., “Esche odno obobschenie teoremy Kuna”, Pozitsionnye igry, Nauka, M., 1967, 230–245

[13] Pontryagin L.S., “K teorii differentsialnykh igr”, DAN SSSR, 156:4 (1964), 738–741 | Zbl

[14] Pshenichnyi B.N., “Prostoe presledovanie neskolkimi ob'ektami”, Kibernetika, 1976, no. 3

[15] Subbotin A.I., Chentsov A.G., Optimizatsiya garantii v zadache upravleniya, Nauka, M., 1981

[16] Chernousko F.L., “Odna zadacha ukloneniya ot mnogikh presledovatelei”, Prikl. matem. i mekh., 40:1 (1976), 14–24 | Zbl

[17] Chikrii A.A., “O lineinykh igrakh kachestva”, Kibernetika, 1971, no. 5, 90–99 | Zbl

[18] Azamov A.A., Kuchkarov A.Sh., “Generalized "Lion and Man" game of R. Rado”, Contributions to Game Theory and Management, 2, SPbU, 2009, 8–20 | MR

[19] Berge C., Theorie generale des jeux a N persons, Gauthier-Villars, Paris, 1957 | MR

[20] Bonato A., Nowakowskii R.J., The game of cops and robbers on graphs, Student Mathematical Library, 61, AMS, Providence, RI, 2011 | DOI | MR | Zbl

[21] Bonato A., An invitation to pursuit-evasion games anf graph theory, AMS, Providence, RI, 2022 | MR

[22] Bopardikar Sh.D., Suri S., “$K$-capture in multiagent pursuit evasion or the lion and the hyenas”, Theoretical Computer Sci., 522 (2014), 13–23 | DOI | MR | Zbl

[23] Bradshaw P., Hosseini S.A., Turcotte J., “Cops and robbers on directed and undirected abelian Cayley graphs”, European J. Combin., 97 (2021), 103383 | DOI | MR | Zbl

[24] Ibragimov G.I., “Optimal pursuit with countably many pursuers and one evader”, Differential equations, 41:5 (2005), 627–635 | DOI | MR | Zbl

[25] Ibragimov G., Luckraz S., “On a characterization of evasion strategies for pursuer-evasion games on graphs”, J. Opt. Theory and Appl., 175:2, 590–596 | DOI | MR | Zbl

[26] Konstantinidis G., Kehagias A., “Simultaneously moving cops and robbers”, Theor. Comp. Sci., 645:1 (2016), 48–59 | DOI | MR | Zbl

[27] Kuhn H.W., “Extensive games and the problem of information”, Coll "Contributions to the Theory of Games", v. 2, Princeton, 1953 | MR

[28] Kummer B., Spiele auf graphen, Springer, Basel, 1980 | MR

[29] Luccio F., Pagli L., “Capture on grids and tori with different numbers of cops”, International conference on parallel computing technologies, 2019, 431–444 | DOI

[30] Luckraz Sh., “A survey on the relationship between the game of cops and robbers and other game representations”, Dyn. Games and Appl., 9:2 (2019), 506–520 | DOI | MR | Zbl

[31] Megrabian A., “The capture time of grids”, Discrete Mathematics, 311 (2011), 102–105 | DOI | MR

[32] Nowakowski R.J., Winkler P.M., “Vertex-to-vertex pursuit in a graph”, Discrete Math., 43:2-3 (1983), 235–239 | DOI | MR | Zbl

[33] Petrosyan L.A., Differential games of pursuit, World Scientific Publisher, 1993 | MR | Zbl

[34] Quilliot A., Jeux et pointes fixes sur les graphes, these de 3eme cycle, Univ. de Paris VI, 1978 | MR