베를레캄프 스위칭 게임

베를캄프 스위칭 게임은 미국의 수학자 엘윈 베를캄프가 제안한 수학 게임이다.^[1]같은 게임을 독자적으로 발견한 데이비드 게일(David Gale)의 이름을 따서 게일-베를캄프(Gale-Berlekamp) 스위칭 게임이라고도 불렸으며,^[2] 비밸런싱 라이트 게임으로도 불렸다.^[3]그것은 두 개의 스위치 뱅크에 의해 제어되는 전구 시스템을 포함하는데, 한 게임 플레이어는 많은 전구를 켜려고 하고 다른 게임 플레이어는 가능한 많은 전구를 끄려고 한다.코딩 이론에서 커버 반지름의 개념을 증명하는 데 사용할 수 있다.

규칙.

게임을 위한 장비는 직사각형 ${\displaystyle \mathrm{모양}}$의 전구를 포함하는 방으로 구성되며, $치수$는$$${\displaystyle \times }$ b ${\$$displaystyle a}$과($와{\displaystyle }$) b {\displaystyle $a}$과(와) b ${\displaystyle b}$이다$.$ 방의 한쪽에 $있는{\displaystyle }$ ${\displaystyle b}$ ${\displaystyle ab}$ 스위치로$$ 각 전구를 개별적으로 제어한다.이들 스위치 중 하나를 뒤집으면 전구가 이전 상태에 따라 꺼짐에서 켜짐 또는 켜짐으로 변경된다.방의 다른 쪽에는 각 열 또는 전구 열마다 하나씩${\displaystyle }$+ ${\displaystyle b}$ ${\displaystyle a+b}$ $스위치$가 있는 다른 둑이 있다.이러한 스위치 중 하나가 플립될 때마다 제어하는 행 또는 열의 모든 전구는 이전 상태에 따라 꺼짐에서 켜짐 또는 켜짐으로 변경된다.스위치를 두 개 이상 플립할 때 스위치가 플립되는 순서는 결과에 영향을 미치지 않는다. 즉, 어떤 순서로 플립이 되든 플립 순서의 마지막에 동일한 전구가 켜진다.

그 게임은 두 판으로 나뉘어 진행된다.첫 번째 라운드에서 첫 번째 플레이어는 개별 조명을 제어하는 스위치를 사용하여 조명을 임의로 켜거나 끌 수 있다.두 번째 라운드에서 두 번째 플레이어는 행이나 빛의 열을 제어하는 스위치를 사용하여 첫 번째 플레이어가 설정한 빛의 패턴을 다른 패턴으로 변경한다(또는 가능한 경우, 변경되지 않은 상태로 둠).첫 번째 선수의 목표는 경기 종료 시 최대한 많은 조명이 남아 있고, 두 번째 선수의 목표는 가능한 한 적은 조명이 남아 있는 것이다.따라서 첫 번째 선수는 두 번째 선수가 많은 조명을 끌 수 없는 조명 패턴을 선택해야 한다.

역사

Berlekamp는 1966년부터 1971년까지 뉴저지 주 머레이 힐에 있는 벨 연구소에서 일했다.^[4]그곳에서 그는 ${\displaystyle \mathrm{수학부}}$ 공용실에서 10$$ ${\displaystyle \times }$ ${\displaystyle 10}$ $[\displaystyle 10\time 10}$케이스에 대한 이 게임의 물리적 인스턴스를 구성했다.^[1][2]David Gale 또한 1971년 이전에 독립적으로 이 게임을 발명했다.^[5]

관련 문제에 초기 연구의 컴퓨터 실험, 15×15{15\times 15\displaystyle}게임은 얼마나 잘 두번째 선수 누가 randomly,[6]고 J.W. 달과 레오 모저(1966년), 글리슨의 questio을 취급하는으로 살아가는 첫번째 선수를 상대로 할 수 있는 것을 물어보라고 해석할 수 있앤드류 M. 글리슨(1960년)에 의해 간행물 포함되어 있었다.nt첫 번째 플레이어의 거의 모든 선택에 대해 큰 게임 보드 크기의 한계에서 최적의 게임 값이 $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle 2n{}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$}}에 가깝다는 것을 기하학적으로 보여준다$.$^[7]

분석

수학적으로 첫 번째 플레이어의 움직임에 의해 점등된 조명을 $세트{\displaystyle }$ S ${\$${\displaystyle \mathrm{displaystyle}}$ $S}$로 설명할 수 있으며, 두 번째 플레이어의 최적 플레이로 달성할 수 있는 최소 개수의 조명을 숫자 f${\displaystyle }$( $S{\displaystyle }$) ${\displaystyle f(S)}$로 기술할 수 있다$.$ 첫 번째 플레이어의 최적 플레이는 $세트{\displaystyle }$ S$${\$displaystyty S}$를 선택하는 것이다.maximizes ${\displaystyle f(S)}$. Therefore, one can describe the largest number of lights that can be achieved by the best play for the first player as a number ${\textstyle R_{a,b}=\max _{S}f(S)}$. Beyond the question of how to play well in an individual game, a broader question that has been the 수학적 연구의 목적은 $일반적$으로 ${\displaystyle R_{}}$a , ${\displaystyle b_{}}${\$displaystyle R_{a,b$$\}$의 값을 $함수$로서 ${\$$displaystyle a}$ 및 $b$ ${\displaystyle b}$의 함수로서 특성화하여 그 동작을 결정하거나, {\$displaystyle$ a$}$ 및$$ $b{\displaystyle }${\$displaystyty$}의 많은 조합에 대한 값을 계산하는 것이다.$b}$ 가능한$$ 한.

정사각형 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ $n$$\times n}$ 배열의$$ 경우는 $n{\displaystyle 12}$ 12 ${\displaystyle$ n$\$$leq$ $12}$에 대해 해결되었다$.$ 또한, $R{\displaystyle {}_{,}}$ ${\displaystyle n_{}}$ ${\$에 대한 하한선은 $n{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 20}$ ${\displaystyleq 20}$에 대해 발견되었다$.$^[8][9][10]이 숫자는 다음과 같다.

$n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ n$\times$ n$}$에 대한 솔루션

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle R_{n,n}}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 82	≥ 96	≥ 106	≥ 120	≥ 132	≥ 148

점증적으로, 이 숫자는 n ${\displaystyle \frac{{}^{}}{\mathrm{}}}$ 2 -${\displaystyle \mathrm{\theta }}$ ${\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle {\tfrac{n^{2}}-\tea (n^{3/2})}$에 따라 증가한다$.$^[2][5][11]

계산 복잡성

어떤 선택을 뒤집어야 할지 기하급수적으로 많은 선택들이 있기 때문에, 컴퓨터적으로 제한된 플레이어들이 이 게임을 얼마나 잘 할 수 있는지에 대한 의문을 제기하는$$$큰{\displaystyle }$ n ${\displaystyle n}$에 대해 최적의 선택을 위한 철저한 검색은 불가능하다.

첫 번째 플레이어는 무작위로 플레이하여$$ 예상 게임 값을 ${\displaystyle \frac{{n\mathrm{}}^{}}{}}$ 2${\displaystyle }$- ${\displaystyle \frac{{}^{}}{\mathrm{}}}$ - ${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$/ 2$){\displaystyle {\tfrac{n^{2}}-O(n^{3/2})$로 만들 수 있다.Similarly, the second player can obtain a value whose expected distance from ${\displaystyle {\tfrac {n^{2}}{2}}}$ is ${\displaystyle \Omega (n^{3/2})}$ by playing randomly; this value might either be larger or smaller than ${\displaystyle {\tfrac {n^{2}}{2}}}$, but if it is lar두 번째 플레이어는 같은 양만큼 작은 값을 얻기 위해 모든 행 스위치를 돌릴 수 있다.^[2][5][11]두 번째 플레이어에 대한 이러한 무작위 전략은 동일한 솔루션 값 보증을 획득하는 다항 시간 알고리즘을 제공하여 조건부 확률 방법을 사용하여 무작위로 만들 수 있다.다른 derandomization은 복잡도 등급 NC에서 병렬 알고리즘을 제공한다.^[12]

첫 번째 선수가 어느 전구를 밝힐지 선택했을 때, 게임에서 두 번째 선수에게 최적의 선택지를 찾는 것은 NP-하드 문제다.^[13]하지만, n×n{\displaystyle n\times의 스녀}게임에, 어떤ε 을에 켜진 전구의(1+ε){\displaystyle(1+\varepsilon)}번 최소 가능한 한 많은 잎사귀을 두번째 선수에 대한 선택을 찾을 수 있는 다차 함수 시간 근사 계획;0{\displaystyle \varepsilon>0}, 시간에 O(n.은 2${\displaystyle )}$+ ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle O^{}}$( ${\displaystyle 1^{}}$ /${\displaystyle {\epsilon {}^{}}^{}}$ ${\displaystyle {{2\mathrm{}}^{}}^{}}$) ${\$^[14]

코딩 이론과의 연관성

Berlekamp 스위칭 게임은 코딩 이론에서 특정 이진 선형 코드의 커버 반경을 실증하는 것으로 사용될 수 있다.길이 $n{\displaystyle }$ ${\displaystyle n}$ 및 $치수$ d ${\displaystyle$ $d$$}$의 이진 선형 코드는 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$라는 두 개의 요소를 가진 유한한 필드 위에$$ n$${\$displaystyle n$} -차원$$ 벡터 공간 $F{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$의 $d{\displaystyle }$ ${\$densionalential$$ line subspace d$}$로 정의된다$$.${\displaystyle \mathb{F} _{2$서브스페이스의 요소를 코드워드라고 하며, 커버 반경은 ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ 수 $r{\displaystyle }$ ${\$$displaystyle \mathb{F} _{2}^{n}}$의 모든 지점이 암호문의$$ 해밍 거리 $r{\displaystyle }$ ${\displaystyle r}$ 내에 있도록$$ 한다$$.

Let ${\displaystyle n=ab}$ and ${\displaystyle d=a+b-1}$. For these parameter values, the vector space ${\displaystyle \mathbb {F} _{2}^{n}}$ describes all possible patterns of lit bulbs on the ${\displaystyle a\times b}$ array of lightbulbs, with a vector addition operation that c두 가지 패턴 중 정확히 하나의 패턴에 나타나는 전구에 불을 붙임으로써 두 가지 패턴을 옴비즈한다(전구 세트의 대칭 차이 연산).하나는 두 번째 플레이어가 완전히 끌 수 있는 모든 패턴 또는 완전히 꺼진 보드로 시작하여 두 번째 플레이어가 만들 수 있는 모든 패턴으로 구성된 선형 하위 공간을 정의할 수 있다.두 번째 플레이어는 두 번째 ${\displaystyle {\mathrm{스위치}}^{}}$ 뱅크 설정 방법에 ${\displaystyle {대해}^{}}$ 2 a${\displaystyle {}^{}}$+ b ${\$$displaystyle 2^{$$a+b}}$를 선택하지만, 이 하위 공간은 ${\displaystyle {두}^{}}$ 번째 플레이어의 스위치를 모두 뒤집으면 패턴 o에 영향을 미치지 않기 때문에 치수$a$${\displaystyle {}^{}}$+ ${\displaystyle b}$ - ${\displaystyle 1^{}}$$a+b-1}$를 $부여$한다$.$f 전구

그런 다음 ${\displaystyle R_{}}$ a${\displaystyle {}_{}}$, ${\displaystyle b_{}}$ ${\$이(가) 이 코드의 커버 반지름이다$$.첫 번째 플레이어가 선택한 전구 세트는 선형 아공간에서 최대한 멀리 떨어진$$ $F{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$의 포인트를 준다.두 번째 플레이어에 의해 상태가 변경되는 전구 세트는 최상의 플레이로 선형 아공간에서 가장 가까운 포인트를 제공한다.이러한 선택 후에도 계속 점등되는 전구 세트는 이 두 점 사이의 해밍 거리를 정의하는 번호를 가진 전구들이다.^[1]

참고 항목

• 여러 전구를 제어하는 스위치를 사용하여 전구를 끄는 것과 관련된 다른 퍼즐인 Lights Out(게임)

참조