| dbo:abstract
|
- Der Satz von Sprague-Grundy ist ein Theorem aus der Kombinatorischen Spieltheorie. Roland Sprague und Patrick Michael Grundy entdeckten 1935 und 1939 unabhängig voneinander, dass sich die heute so genannten neutralen Spiele, bei denen der zuletzt ziehende Spieler gewinnt, so auffassen lassen, als wären sie Reihen des Nim-Spiels. (de)
- En la teoría de juegos combinatorios, el teorema de Sprague-Grundy establece que todo juego imparcial bajo la convención de juego normal es equivalente a un juego de un montón de Nim, o a una generalización infinita de Nim. Por tanto, puede representarse como un número natural, el tamaño del montón en su juego equivalente de Nim, como un número ordinal en la generalización infinita, o alternativamente como un nimber, el valor de ese juego de un montón en un sistema algebraico cuyo La operación de adición combina varios montones para formar un único montículo equivalente en nim. El valor Grundy o valor Nim de cualquier juego imparcial es el nimber único al que es equivalente el juego. En el caso de un juego cuyas posiciones están indexadas por números naturales (como el propio nim, que está indexado por el tamaño de su montón), la secuencia de nimbers para posiciones sucesivas del juego se denomina secuencia Nim del juego. El teorema de Sprague-Grundy y su demostración encapsulan los principales resultados de una teoría descubierta independientemente por R.P. Sprague (1935) y P.M. Grundy (1939). (es)
- Dans la théorie des jeux combinatoires, le théorème de Sprague-Grundy indique comment définir la stratégie gagnante d'un jeu impartial fini sans partie nulle en version normale (c'est-à-dire où le joueur qui ne peut plus jouer est le perdant), lorsque ce jeu est lui-même somme de deux ou plusieurs jeux impartiaux. Le théorème de Sprague-Grundy a été découvert indépendamment par Roland Sprague en 1935 et Patrick Grundy en 1939. Il généralise un résultat établi en 1901 par Charles Bouton, relatif au jeu de Nim classique ou jeu de Marienbad. La généralisation de ce théorème aux jeux partisans a donné naissance à la théorie des jeux combinatoires. (fr)
- In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim. The Grundy value or nim-value of any impartial game is the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the nim-sequence of the game. The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1936) and P. M. Grundy (1939). (en)
- スプレイグ・グランディの定理（英: Sprague–Grundy theorem）とは、 組合せゲーム理論において、通常のプレイ規約下におけるすべての公平ゲームはと等価であることを意味する定理である。このとき、公平ゲームにおけるグランディ値やニム値はゲームと等価なユニークな数として定義される。位置（もしくは位置の加数）に自然数（例えばニムのようなゲームにおいて考えられるヒープのサイズ）によって添字が付けられているゲームの場合、連続したヒープサイズに対するニム数の列はゲームのニム列と呼ばれる。 この理論は (1935) と (1939) により別々に発見された。 (ja)
- Twierdzenie Sprague’a-Grundy’ego – twierdzenie dotyczące gier, które są:
* bezstronne (impartial), czyli gracze mogą wykonywać dokładnie te same ruchy w danej sytuacji
* normalne (normal game), czyli przegrywa ten, kto nie może zrobić ruchu
* w każdej pozycji można wykonać skończoną liczbę ruchów
* każda rozgrywka ma skończoną długość Funkcja Sprague’a-Grundy’ego: jest określona rekurencyjnie F(p)=0 dla pozycji p, dla której nie można wykonać ruchu F(k)= mex(A) gdzie A, to zbiór wartości funkcji F dla pozycji, do których możemy dojść w jednym ruchu z pozycji k jeśli A nie jest pusty. Twierdzenie Sprague’a-Grundy’ego: Gracz ma strategię zwycięską wtedy i tylko wtedy, gdy wartość funkcji Sprague’a-Grundy’ego jest różna od 0. Wartość funkcji Sprague’a-Grundy’ego dla sumy gier (tzn. gra toczy się na kilku planszach, gracz w dowolnym ruchu wykonuje ruch na jednej planszy) wyraża się wzorem: gdzie suma nimliczb po prawej stronie równości oznacza operację xor na liczbach F(P1), F(P2), ...F(Pn) (pl)
- Функція Шпрага-Гранді широко використовується в теорії ігор для знаходження виграшної стратегії в комбінаційних іграх, наприклад, гра Нім. Дана функція визначається для ігор з двома гравцями, в яких програє той, який не має можливості зі своєї позиції зробити черговий крок.Теорема була незалежно сформульована й доведена Р. Шпрагом (1935) та П.М. Гранді (1939). (uk)
- Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход. В случае дискретных игр иногда называется нимбером. Теорема Шпрага-Гранди — это общий вывод из результатов, которые были независимо сформулированы и доказаны (1935) и (1939). Она состоит в том, что для любой беспристрастной игры, где выигрывает сделавший последний ход, для каждой позиции однозначно определено значение функции Шпрага-Гранди, которое и определяет выигрышную стратегию либо её отсутствие. (ru)
- 在组合博弈论中，斯普莱格–格隆第定理证明， 所有的一般胜利条件下的无偏博弈都能转换成尼姆数表达的博弈。一个无偏博弈的尼姆值定义为这个博弈的等价尼姆数。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20048 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der Satz von Sprague-Grundy ist ein Theorem aus der Kombinatorischen Spieltheorie. Roland Sprague und Patrick Michael Grundy entdeckten 1935 und 1939 unabhängig voneinander, dass sich die heute so genannten neutralen Spiele, bei denen der zuletzt ziehende Spieler gewinnt, so auffassen lassen, als wären sie Reihen des Nim-Spiels. (de)
- スプレイグ・グランディの定理（英: Sprague–Grundy theorem）とは、 組合せゲーム理論において、通常のプレイ規約下におけるすべての公平ゲームはと等価であることを意味する定理である。このとき、公平ゲームにおけるグランディ値やニム値はゲームと等価なユニークな数として定義される。位置（もしくは位置の加数）に自然数（例えばニムのようなゲームにおいて考えられるヒープのサイズ）によって添字が付けられているゲームの場合、連続したヒープサイズに対するニム数の列はゲームのニム列と呼ばれる。 この理論は (1935) と (1939) により別々に発見された。 (ja)
- Функція Шпрага-Гранді широко використовується в теорії ігор для знаходження виграшної стратегії в комбінаційних іграх, наприклад, гра Нім. Дана функція визначається для ігор з двома гравцями, в яких програє той, який не має можливості зі своєї позиції зробити черговий крок.Теорема була незалежно сформульована й доведена Р. Шпрагом (1935) та П.М. Гранді (1939). (uk)
- 在组合博弈论中，斯普莱格–格隆第定理证明， 所有的一般胜利条件下的无偏博弈都能转换成尼姆数表达的博弈。一个无偏博弈的尼姆值定义为这个博弈的等价尼姆数。 (zh)
- En la teoría de juegos combinatorios, el teorema de Sprague-Grundy establece que todo juego imparcial bajo la convención de juego normal es equivalente a un juego de un montón de Nim, o a una generalización infinita de Nim. Por tanto, puede representarse como un número natural, el tamaño del montón en su juego equivalente de Nim, como un número ordinal en la generalización infinita, o alternativamente como un nimber, el valor de ese juego de un montón en un sistema algebraico cuyo La operación de adición combina varios montones para formar un único montículo equivalente en nim. (es)
- Dans la théorie des jeux combinatoires, le théorème de Sprague-Grundy indique comment définir la stratégie gagnante d'un jeu impartial fini sans partie nulle en version normale (c'est-à-dire où le joueur qui ne peut plus jouer est le perdant), lorsque ce jeu est lui-même somme de deux ou plusieurs jeux impartiaux. Le théorème de Sprague-Grundy a été découvert indépendamment par Roland Sprague en 1935 et Patrick Grundy en 1939. Il généralise un résultat établi en 1901 par Charles Bouton, relatif au jeu de Nim classique ou jeu de Marienbad. (fr)
- In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim. (en)
- Twierdzenie Sprague’a-Grundy’ego – twierdzenie dotyczące gier, które są:
* bezstronne (impartial), czyli gracze mogą wykonywać dokładnie te same ruchy w danej sytuacji
* normalne (normal game), czyli przegrywa ten, kto nie może zrobić ruchu
* w każdej pozycji można wykonać skończoną liczbę ruchów
* każda rozgrywka ma skończoną długość Funkcja Sprague’a-Grundy’ego: jest określona rekurencyjnie F(p)=0 dla pozycji p, dla której nie można wykonać ruchu F(k)= mex(A) gdzie A, to zbiór wartości funkcji F dla pozycji, do których możemy dojść w jednym ruchu z pozycji k jeśli A nie jest pusty. (pl)
- Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход. В случае дискретных игр иногда называется нимбером. (ru)
|
| rdfs:label
|
- Satz von Sprague-Grundy (de)
- Teorema de Sprague-Grundy (es)
- Théorème de Sprague-Grundy (fr)
- スプレイグ・グランディの定理 (ja)
- Twierdzenie Sprague’a-Grundy’ego (pl)
- Sprague–Grundy theorem (en)
- Функция Шпрага — Гранди (ru)
- 斯普莱格–格隆第定理 (zh)
- Функція Шпрага-Гранді (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
