| dbo:abstract
|
- The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely. The angel problem is: can an angel with high enough power win? There must exist a winning strategy for one of the players. If the devil can force a win then it can do so in a finite number of moves. If the devil cannot force a win then there is always an action that the angel can take to avoid losing and a winning strategy for it is always to pick such a move. More abstractly, the "pay-off set" (i.e., the set of all plays in which the angel wins) is a closed set (in the natural topology on the set of all plays), and it is known that such games are determined. Of course, for any infinite game, if player 2 doesn't have a winning strategy, player 1 can always pick a move that leads to a position where player 2 doesn't have a winning strategy, but in some games, simply playing forever doesn't confer a win to player 1, so undetermined games may exist. Conway offered a reward for a general solution to this problem ($100 for a winning strategy for an angel of sufficiently high power, and $1000 for a proof that the devil can win irrespective of the angel's power). Progress was made first in higher dimensions. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win. Bowditch proved that a 4-angel (that is, an angel with power k = 4) can win and Máthé and Kloster gave proofs that a 2-angel can win. (en)
- El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway El juego se suele conocer por el nombre Ángeles y Demonios. El juego tiene dos jugadores, llamados el ángel y el diablo. Se juega sobre una tablero de ajedrez infinito (o lo que es lo mismo, los puntos de una cuadrícula bidimensional). El ángel tiene poder k (un número natural mayor o igual que 1), el cual es fijado antes de que el juego comience. El tablero está inicialmente vacío, con el ángel en el origen. En cada turno, el ángel salta a otra casilla vacía, la cual podría ser alcanzada por un máximo de k movimientos correspondientes a los del rey en ajedrez; es decir, la distancia a partir de la casilla inicial no es mayor que k con la norma infinito). El diablo, en su turno, puede bloquear una casilla cualquiera en la que no esté el ángel. El ángel puede saltar sobre casillas bloqueadas, pero no puede terminar su turno en ellas. El diablo gana si el ángel no puede moverse. El ángel gana si puede sobrevivir indefinidamente. El problema del ángel consiste en: ¿Puede un ángel con poder suficientemente alto ganar? Debe existir una estrategia ganadora para uno de los jugadores. Si el diablo puede forzar una victoria, entonces puede hacerlo en un número finito de movimientos. Si el diablo no puede forzar una victoria, entonces siempre hay un movimiento que el ángel puede hacer para evitar perder, y una estrategia ganadora para él sería escoger siempre este movimiento. A un nivel más abstracto, el "conjunto de ganancias" (es decir, el conjunto de todas los juegos en los que el ángel gana) es un conjunto cerrado (en la topología natural de los conjuntos de todos los juegos), y se sabe que estos juegos son determinados. Conway ofreció una recompensa por una solución general a este problema (100 dólares para una estrategia ganadora con un ángel de poder suficientemente alto, y 1000 dólares para una demostración de que el diablo puede ganar cualquiera que sea el poder del ángel). Se progresó primero en dimensiones mayores que 2, con algunas bellas demostraciones. A finales de 2006, el problema se resolvió cuando aparecieron demostraciones independientes, probando que un ángel puede ganar. demostró que un 4-ángel puede ganar y Mathé y Kloster demostraron que un 2-ángel puede ganar. (es)
- Le problème de l'ange est un jeu mathématique conceptuel inventé par le mathématicien John H. Conway en 1982 dans le livre Winning Ways for your Mathematical Plays. Sur un échiquier de taille supposée infinie, un diable tente de piéger un ange. À chaque coup, le diable élimine l'une des cases du plateau, puis l'ange doit sauter à une case quelconque non éliminée, distante de N cases au maximum, N étant un entier positif fixé au préalable (dénommé « pouvoir » de l'ange). L'ange pouvant « voler », les cases intermédiaires entre sa case de départ et sa case d'arrivée peuvent avoir déjà été éliminées ou non. Seule la distance entre ces deux cases est limitée par le pouvoir de l'ange. L'objectif du diable est de piéger l'ange sur une « île » située à une distance d'au moins N cases de toute autre case non éliminée du plateau, empêchant ainsi l'ange de se déplacer. On peut penser a priori que l'ange est beaucoup plus puissant que le diable, car il peut se déplacer tous azimuts sur un plateau de taille infinie, tandis que le diable ne peut éliminer qu'une case à la fois. Toutefois, le diable est lui-même très puissant puisqu'il peut éliminer des cases qui se trouvent à une grande distance de la position actuelle de l'ange et en quelque sorte « piéger le terrain » en prévision du passage de l'ange dans ces régions. Conway et ses collaborateurs avaient ainsi montré très vite qu'un ange de pouvoir 1 perd en moins de 150 coups, et qu'un ange de pouvoir arbitraire, mais qui n'a jamais le droit de reculer (d'aller vers le sud) de plus de 1000 cases, se fait finalement piéger. La question principale que posait ce jeu a été finalement résolue en 2006 :
* l'ange peut-il échapper indéfiniment au diable, à condition que son pouvoir soit suffisant ? La réponse est positive, dès que ce pouvoir est supérieur ou égal à 2 : une stratégie gagnante (pour l'ange), due à est décrite ici (en anglais) : [1], et peut être testée à l'adresse suivante : [2] (fr)
- エンジェル・プロブレム (angel problem) はジョン・ホートン・コンウェイによって提起された組合せゲーム理論の問題である。一般に天使と悪魔 (Angels and Devils) ゲームとも呼ばれている。ゲームは、天使と悪魔と呼ばれる二人のプレイヤーによって、無限の広さのチェスボード（正方格子）の上で行われる。ゲームの開始前に、天使は力k（kは正の整数）を持つことを決めておく。開始時点で盤上には天使がひとつの場所にいるだけで他は空である。天使と悪魔は交互に手順が回ってくる。天使は、自分が今いる地点からチェビシェフ距離で最大kの範囲内にある空いている地点へジャンプする。悪魔は、天使のいない任意の地点にひとつブロックを置く。天使はブロックを飛び越えることはできるが、ブロックの上に乗ることはできない。天使が動けなくなったら悪魔の勝ちとなり、無限に動き続けることができれば天使の勝ちである。 このとき、十分な力を持つ天使であれば悪魔に勝てるだろうか。 このゲームには必ずどちらかのプレイヤーに必勝法が存在する。もし悪魔に必勝法があれば、有限の手数でゲームは終わる。もし悪魔に必勝法がなければ、天使は常に自分が負けないように手を選ぶことで無限にゲームを続けることができ、勝敗の定義からそれが天使の必勝法となる。より抽象的には、天使の勝つすべてのゲームプレイの集合は、すべてのゲームプレイの自然な位相空間に対して閉じている、つまりゲームは決定的である。当然ながら、無限に続けられるあらゆるゲームはプレイヤー2が必勝法を持たないときプレイヤー1は自らが負けないような手を選び続けることができるが、ゲームの勝敗の定義次第では単にゲームを無限に続けることがプレイヤー1の勝利になるとは限らない。したがって、決定的でないゲームが存在する可能性はある。 コンウェイはこの問題に対する回答に賞金を与えると宣言した（十分な力を持つ天使の必勝法に100ドル、天使の力によらず悪魔が勝つと示すことができれば1000ドル）。当初は、チェスボードを三次元に拡張した問題に対する進展が見られた。オリジナルの（二次元の）問題では、2006年後半に、独立した複数の証明によって天使の勝利が示された。Bowditch は4の力を持つ天使が勝つことを証明し、Máthé と Kloster は、力が2あれば十分なことを示した。 (ja)
- Il problema dell'angelo è un problema matematico della teoria dei giochi proposto da John Horton Conway. (it)
- O problema do Anjo é uma questão na Teoria dos Jogos proposta por John Conway. O jogo é comumente referido como o jogo dos Anjos e Diabos. É jogado por dois jogadores chamados o anjo e o diabo. Ele é jogado num tabuleiro de xadrez infinito (ou equivalentemente aos pontos de um reticulado 2D). O anjo tem poder (o número natural 1 ou maior). O tabuleiro de xadrez inicia-se vazio com o anjo na origem. A cada rodada, o anjo salta para um quadrado vazio diferente no máximo quadrados de distância, ou seja, um quadrado que poderia ser alcançado por no máximo movimentos do rei de xadrez. (A distância do quadrado inicial é no máximo na norma de infinidade). O demônio, na sua vez, pode adicionar um bloco a qualquer quadrado que não contenha um anjo. O anjo pode pular sob os quadrados obstruídos, mas não pode aterrissar neles. O demônio ganha se o anjo ficar incapaz de se mover. O anjo ganha se sobreviver indefinidamente. O problema do Anjo é: Pode um anjo com poder suficientemente grande ganhar? A resposta é desconhecida, e Conway ofereceu uma recompensa para a solução geral deste problema($100 para a estratégia de vencer do anjo com poder suficientemente grande para ganhar, e $1000 para a prova de que o demônio pode ganhar independentemente do poder do anjo). O progresso, entretanto, foi feito em dimensões elevadas, com algumas provas . Deve existir uma estratégia para que um dos jogadores ganhe. Se o diabo pode forçar uma vitória, então ele pode fazer isso num número finito de movimentos. Se o diabo não pode forçar uma vitória, então existe sempre uma ação que o anjo pode fazer para evitar perder e uma estratégia para ganhar para esse é sempre escolher esse movimento.Abstraindo mais, o "o conjunto do pay-off" (isto é, o conjunto de todos os jogos em que o anjo ganha) é um conjunto fechado (na topologia natural no conjunto de todos os jogos), e é sabido que tais jogos são determinísticos. (pt)
- Задача об ангеле и дьяволе — задача теории игр, предложенная Конвеем в 1982.. (ru)
- 天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题，在2006年已獲解答。 (zh)
|
| rdfs:comment
|
- Il problema dell'angelo è un problema matematico della teoria dei giochi proposto da John Horton Conway. (it)
- Задача об ангеле и дьяволе — задача теории игр, предложенная Конвеем в 1982.. (ru)
- 天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题，在2006年已獲解答。 (zh)
- The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. T (en)
- El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway El juego se suele conocer por el nombre Ángeles y Demonios. El juego tiene dos jugadores, llamados el ángel y el diablo. Se juega sobre una tablero de ajedrez infinito (o lo que es lo mismo, los puntos de una cuadrícula bidimensional). El ángel tiene poder k (un número natural mayor o igual que 1), el cual es fijado antes de que el juego comience. El tablero está inicialmente vacío, con el ángel en el origen. En cada turno, el ángel salta a otra casilla vacía, la cual podría ser alcanzada por un máximo de k movimientos correspondientes a los del rey en ajedrez; es decir, la distancia a partir de la casilla inicial no es mayor que k con la norma infinito). El diablo, en su turno, pued (es)
- Le problème de l'ange est un jeu mathématique conceptuel inventé par le mathématicien John H. Conway en 1982 dans le livre Winning Ways for your Mathematical Plays. Sur un échiquier de taille supposée infinie, un diable tente de piéger un ange. À chaque coup, le diable élimine l'une des cases du plateau, puis l'ange doit sauter à une case quelconque non éliminée, distante de N cases au maximum, N étant un entier positif fixé au préalable (dénommé « pouvoir » de l'ange). L'ange pouvant « voler », les cases intermédiaires entre sa case de départ et sa case d'arrivée peuvent avoir déjà été éliminées ou non. Seule la distance entre ces deux cases est limitée par le pouvoir de l'ange. (fr)
- エンジェル・プロブレム (angel problem) はジョン・ホートン・コンウェイによって提起された組合せゲーム理論の問題である。一般に天使と悪魔 (Angels and Devils) ゲームとも呼ばれている。ゲームは、天使と悪魔と呼ばれる二人のプレイヤーによって、無限の広さのチェスボード（正方格子）の上で行われる。ゲームの開始前に、天使は力k（kは正の整数）を持つことを決めておく。開始時点で盤上には天使がひとつの場所にいるだけで他は空である。天使と悪魔は交互に手順が回ってくる。天使は、自分が今いる地点からチェビシェフ距離で最大kの範囲内にある空いている地点へジャンプする。悪魔は、天使のいない任意の地点にひとつブロックを置く。天使はブロックを飛び越えることはできるが、ブロックの上に乗ることはできない。天使が動けなくなったら悪魔の勝ちとなり、無限に動き続けることができれば天使の勝ちである。 このとき、十分な力を持つ天使であれば悪魔に勝てるだろうか。 (ja)
- O problema do Anjo é uma questão na Teoria dos Jogos proposta por John Conway. O jogo é comumente referido como o jogo dos Anjos e Diabos. É jogado por dois jogadores chamados o anjo e o diabo. Ele é jogado num tabuleiro de xadrez infinito (ou equivalentemente aos pontos de um reticulado 2D). O anjo tem poder (o número natural 1 ou maior). O tabuleiro de xadrez inicia-se vazio com o anjo na origem. A cada rodada, o anjo salta para um quadrado vazio diferente no máximo quadrados de distância, ou seja, um quadrado que poderia ser alcançado por no máximo movimentos do rei de xadrez. (A distância do quadrado inicial é no máximo na norma de infinidade). O demônio, na sua vez, pode adicionar um bloco a qualquer quadrado que não contenha um anjo. O anjo pode pular sob os quadrados obstruídos, (pt)
|
