일반화된 게임

스도쿠(4×4)

스도쿠(9×9)

스도쿠(25×25)

일반화된 스도쿠에는 다양한 크기의 퍼즐이 포함되어 있습니다.

계산 복잡도 이론에서, 일반화 게임은 모든 크기의 보드나 그리드 위에서 플레이할 수 있도록 일반화 된 게임 또는 퍼즐입니다.예를 들어, 일반화된 체스는 각 면에 $2개씩$ $2n$ n $×$ $n\times n$ n $디스플레이$ 스타일 $n$ $\$ $times$ n $)$ 보드 $2n$ 상에서 진행되는 $n\times n$ $n\times n$ 게임입니다.일반화된 스도쿠에는 n $n\times n$ × $n\times n$ (\ $displaystyle$ n $\times$ n $)$ $n\times n$ 에 $n\times n$ 구축된 스도쿠가 포함됩니다.

복잡도 이론은 문제의 점근적 난이도를 연구하기 때문에, 고정된 크기의 보드상의 게임은 유한한 문제이기 때문에 게임의 일반화가 필요하다.

기판의 사이즈로 다항식으로 여러 번 이동하는 일반화된 게임의 경우, 주어진 위치에서 첫 번째 플레이어의 승리가 있는지 여부를 판단하는 문제는 PSPACE-complete이다.일반화된 16진수 및 역수는 PSPACE-완전입니다.^[1]^[2]

기판의 사이즈가 지수적으로 변화하는 다수의 일반화된 게임에 대해 주어진 위치에서 첫 번째 플레이어의 승리가 있는지 여부를 판단하는 문제는 EXPTIME-complete이다.일반 체스, 바둑(일본어 ko 룰 포함), 키호,^[3] 체커는 EXPTIME 완료입니다.^[4]^[5]^[6]

「」를 참조해 주세요.

레퍼런스

^ Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/bf00288964
^ Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an $n\times n$ board is PSPACE-complete", Theoretical Computer Science, 123 (2): 329–340, doi:10.1016/0304-3975(94)90131-7
^ Mishiba, Shohei; Takenaga, Yasuhiko (2020-07-02). "QUIXO is EXPTIME-complete". Information Processing Letters: 105995. doi:10.1016/j.ipl.2020.105995. ISSN 0020-0190.
^ Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$ ", Journal of Combinatorial Theory, Series A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9
^ Robson, J. M. (1983), "The complexity of Go", Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417
^ Robson, J. M. (May 1984), " $N$ by $N$ checkers is Exptime complete", SIAM Journal on Computing, Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi:10.1137/0213018

이 게임 이론 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.

P np NP

이 이론적인 컴퓨터 공학 관련 기사는 짧은 글이다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.

[1] Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/bf00288964

[2] Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an $n\times n$ board is PSPACE-complete", Theoretical Computer Science, 123 (2): 329–340, doi:10.1016/0304-3975(94)90131-7

[3] Mishiba, Shohei; Takenaga, Yasuhiko (2020-07-02). "QUIXO is EXPTIME-complete". Information Processing Letters: 105995. doi:10.1016/j.ipl.2020.105995. ISSN 0020-0190.

[4] Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$ ", Journal of Combinatorial Theory, Series A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9

[5] Robson, J. M. (1983), "The complexity of Go", Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417

[6] Robson, J. M. (May 1984), " $N$ by $N$ checkers is Exptime complete", SIAM Journal on Computing, Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi:10.1137/0213018

[1]

[2]

[3]

[4]

[5]

[6]

Search

일반화된 게임

네임스페이스

더

「」를 참조해 주세요.

레퍼런스

Search

일반화된 게임

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.