최근 DeepMind의 AI 에이전트 DeepNash는 Stratego에서 인간 전문 플레이어를 물리치고 Top 3에 진입하는 데 성공했습니다.
12월 1일, 사이언스지에 논문이 공식 게재되었습니다.
논문 주소: http://www.science.org/doi/10.1126/science.add4679
오늘날 게임 플레이 AI는 완전히 새로운 무대.
과거에는 많은 과학자들이 AI 훈련을 위해 체스와 바둑을 사용했지만 이번에 DeepMind는 체스와 바둑보다 더 복잡하고 포커보다 영리한 고전 보드 게임인 Stratego를 사용했습니다.
그리고 DeepNash라는 AI 에이전트는 스스로와 대결하면서 처음부터 Stratego를 배웠습니다.
이제 DeepNash는 세계 최대 온라인 Stratego 플랫폼인 Gravon의 인간 전문가 중 역사상 상위 3위 안에 들었습니다.
DeepNash는 이론적으로 게임 이론과 모델 프리 심층 강화 학습을 기반으로 하는 새로운 플레이 방식을 채택했습니다.
이 이름은 미국의 유명한 수학자 존 내쉬(John Nash)를 기리기 위해 붙여진 이름이기도 함을 알 수 있습니다.
그가 제안한 내쉬 균형, 비협조적 게임 균형이라고도 알려진 것은 게임 이론에서 매우 중요한 부분입니다.
보드 게임은 통제된 환경에서 인간과 기계가 어떻게 전략을 수립하고 실행하는지 연구할 수 있게 해주기 때문에 역사적으로 AI의 진행 상황을 측정하는 표준이었습니다.
그리고 이 스트라테고의 비밀은 무엇인가요?
체스와 바둑의 차이점은 Stratego가 불완전한 정보 게임이라는 것입니다. 플레이어는 상대방의 말의 정체를 직접 관찰할 수 없습니다.
이러한 복잡성으로 인해 AI 기반 Stratego 시스템은 종종 아마추어 수준에 있으며, 아무리 열심히 작동해도 "전문가" 수준에 도달하는 것이 불가능합니다.
과거 다양한 AI가 게임에서 대승을 거두고 인간을 완전히 압도할 수 있었던 것도 '게임트리 검색'이라는 AI 기술 때문이었습니다.
"게임 트리 검색"은 완전한 정보로 모든 종류의 게임을 죽일 수 있지만, Stratego와 같은 게임에는 확장성이 충분하지 않기 때문에 약간 무력합니다.
이 시점에서 DeepNash는 게임 트리 검색을 완전히 파괴했습니다.
사실 DeepNash는 게임 자체를 훨씬 뛰어넘는 Stratego의 가치를 마스터했습니다.
현실 세계는 종종 매우 복잡하고 정보가 제한되어 있습니다. 진정한 고급 AI 시스템은 Stratego와 같은 환경에 직면합니다.
DeepNash는 AI가 어떻게 결과의 균형을 성공적으로 맞추고 불확실한 상황에서 복잡한 문제를 해결할 수 있는지를 성공적으로 보여주었습니다.
Stratego 게임 방법
Stratego는 턴제 깃발 탈취 게임입니다. 게임에서 플레이어는 허세를 부리고, 우회전술을 사용하고, 정보를 수집하고, 능숙하게 작전을 수행해야 합니다.
제로섬 게임이므로 한 플레이어의 이득은 상대방의 손실과 동일합니다.
우리의 군사 체스와 비슷하게 들립니다.
Stratego와 군용 체스의 차이점은 체스 말 수가 더 많고, 군 계급이 더 많으며, 체스판 디자인이 더 간단하고, 철도, 캠프 및 심판이 없다는 것입니다.
양쪽이 대형을 세울 때 모든 체스 말은 똑바로 세워져 상대방이 볼 수 없어야 합니다.
포메이션이 완료되면 빨간색 부분이 먼저 이동한 후 차례대로 한 조각씩 이동합니다.
체스 기물 중 군기 및 지뢰는 이동할 수 없습니다. 정찰병은 가로 및 세로로 어떤 칸도 이동할 수 없지만, 다른 체스 기물은 가로 또는 세로로 한 칸만 이동할 수 있습니다.
양쪽의 체스 말이 같은 그리드에 있을 때 함께 드러나고 크기에 따라 판단됩니다. 이긴 체스 말은 뒤로 향하게 원래 위치로 돌아가고 패한 체스 말은 제거됩니다.
Stratego의 승리 방법은 중국 군사 체스와 유사합니다. 상대방의 군대 깃발을 점령하거나 움직이는 체스 말을 모두 파괴하여 승리를 거둘 수 있습니다.
Stratego가 AI에 그토록 어려운 이유는 무엇입니까? 그 이유 중 하나는 그것이 불완전한 정보의 게임이라는 것입니다.
Stratego의 두 플레이어는 시작 포메이션에 40개의 조각을 배치할 때 서로 숨겨져 있습니다.
플레이어는 동일한 지식에 접근할 수 없기 때문에 결정을 내릴 때 가능한 모든 결과의 균형을 맞춰야 합니다.
Stratego 체스 말의 종류와 순위
왼쪽: 체스 말의 순위. 게임에서는 군사 순위가 더 높은 조각이 승리합니다. 단, 스파이의 공격을 받은 10(원수)은 예외입니다. 단, 광부가 포획한 경우를 제외하면 폭탄은 항상 승리합니다.
중간: 가능한 시작 포메이션입니다. 깃발은 뒤쪽에 안전하게 보관해야 하며, 측면에는 폭탄이 있어 보호를 제공합니다. 두 개의 연한 파란색 영역은 "호수"이므로 절대 들어가서는 안 됩니다.
오른쪽: 게임이 진행 중인데, 블루팀의 스파이가 레드팀의 원수를 사로잡은 모습이 보입니다.
이 게임은 AlphaZero를 당황하게 했습니다
Stratego에서는 정보가 숨겨져 있습니다.
다른 플레이어를 만날 때만 상대방 조각의 정체가 드러납니다.
체스와 바둑의 차이점은 두 플레이어 모두 각 체스 말의 위치와 정체를 정확히 알고 있기 때문에 "완벽한 정보 게임"이라는 것입니다.
DeepMind의 AlphaZero는 항상 완벽한 정보 게임에서 좋은 성능을 발휘했지만 Stratego에서는 난처했습니다.
체스에서는 AlphaZero가 4시간 만에 Stockfish를 이겼고, 장기에서는 AlphaZero가 2시간 만에 Elmo를 이겼고, 바둑에서는 AlphaZero가 AlphaGo를 이겼고, 이세돌은 30시간 만에 승리했습니다.
Stratego는 Texas Hold와 더 유사합니다. 인간과 같은 능력이 필요합니다. 인간은 불완전한 정보를 가지고 결정을 내려야 하고 허세를 부릴 필요가 있습니다.
미국 작가 Jack London은 다음과 같이 지적한 적이 있습니다. "살면서 항상 좋은 카드를 갖고 있는 것은 아니지만 때로는 나쁜 패를 가지고도 잘 플레이할 수 있습니다."
실제로 많은 AI도 매우 능숙합니다. 그러나 그들이 Stratego를 만났을 때 그들은 혼란스러워했습니다. 이 게임의 과정은 너무 깁니다!
이기려면 플레이어가 수백 번 움직여야 합니다. 따라서 게임에서의 추론은 수많은 연속적인 행동을 기반으로 해야 하며, 이 과정에서 각 행동이 최종 결과에 미치는 영향을 명확하게 파악하기는 어렵습니다.
Chess, Poker, Go 및 Strateg의 크기 차이
또한 Chess, Go 및 Poker에 비해 가능한 게임 상태("게임 트리 복잡성")의 수가 차트를 벗어났으며 훨씬 더 어렵습니다. 해결하다.
이것이 Stratego가 매우 흥미로운 이유입니다. 이는 AI 커뮤니티에서 수십 년에 걸친 도전을 대표합니다.
Stratego: AI가 정복할 수 있는 고지
수년에 걸쳐 Stratego 게임에서 인공 지능을 돋보이게 만드는 방법은 AI 연구자들의 초점이 되었습니다.
이 게임에서 인간 플레이어를 물리치는 데에는 두 가지 주요 어려움이 있습니다.
우선, 이 게임의 게임 트리에는 10개의 535번째 전원 상태가 있습니다. 즉, 게임에는 10개의 535번째 전원 상태가 가능합니다. 대조적으로, Go에서는 가능한 레이아웃의 10의 360승만 있습니다.
둘째, Stratego에서 인공지능은 10의 66승 이상에 대해 상대의 배치 전략을 추론해야 하는 반면 포커에는 가능한 카드 쌍이 천 개만 있습니다.
따라서 Stratego의 복잡한 레이아웃을 깨는 것은 쉽지 않습니다. 인간 Stratego 플레이어를 물리치는 방법은 AI 연구자들이 직면한 전례 없는 과제입니다.
DeepNash가 다른 AI를 완전히 능가하는 이유는 게임 이론과 모델 프리 심층 강화 학습을 결합한 새로운 방법을 채택했기 때문입니다.
"모델리스"는 DeepNash가 게임에서 상대방의 상태를 명시적으로 시뮬레이션하려고 시도하지 않음을 의미합니다.
특히 게임 초반에는 DeepNash가 상대방의 말에 대해 거의 알지 못하는 경우, 이 모델링은 완료가 가능하더라도 유효하지 않을 확률이 높습니다.
또한 Stratego의 게임 트리는 너무 복잡하기 때문에 DeepNash는 게임을 할 때 다른 AI가 사용하는 몬테카를로 트리 검색을 채택할 수 없습니다. 후자는 덜 복잡한 보드 게임과 포커에서 AI가 획기적인 성과를 거두는 열쇠입니다.
양 당사자가 교대로 행동하는 완전한 정보 게임에서는 균형 전략이 역할을 할 수 있지만 불완전한 정보 게임에서는 충분하지 않음을 알 수 있습니다.
DeepNash는 새로운 게임 이론 알고리즘 아이디어인 정규화된 Nash 동적 프로그래밍(Regularized Nash Dynamic, R-NaD)을 채택합니다.
이 모델 프리 강화 학습 알고리즘은 DeepNash의 핵심입니다.
DeepNash를 안내하고 학습 행동이 Nash 균형 방향으로 발전하도록 합니다.
DeepNash는 R-NaD와 심층 신경망 아키텍처를 결합하여 Nash 평형으로 수렴합니다.
보상 변환, 동적 계획(동적) 및 업데이트 반복(udate)의 세 단계가 포함됩니다.
연구팀은 알고리즘이 원래 게임의 내쉬 균형에 수렴했음을 증명하기 위해 일련의 고정점이 생성될 때까지 이 세 단계를 반복적으로 적용했습니다.
가장 강력한 Stratego 로봇(컴퓨터 전략 월드 챔피언십의 여러 우승자 포함)과 대결할 때 DeepNash는 97%의 승률을 가지며 종종 100%의 승률을 달성합니다.
Gravon 게임 플랫폼에서 DeepNash는 최고의 인간 플레이어를 상대로 84%의 승률을 달성하여 역사상 상위 3위 안에 들었습니다.
물론, 게임 내에서 제한 없이 게임 이론을 통해 내쉬 균형에 도달할 수는 없습니다. 이런 방식으로는 플레이어의 승률을 보장할 수 없기 때문입니다.
균형 전략은 정보가 완전한 게임에서만 완전히 적용 가능합니다. 정보가 불완전한 게임에서는 예기치 않게 승리하려면 다른 전략이 필요합니다.
초기 부대 구성에서 DeepNash는 특별한 게임플레이를 채택했습니다. 익스플로잇을 어렵게 만들기 위해 DeepNash는 예측할 수 없는 전략을 개발했습니다.
이는 상대가 후속 경기에서 자신의 패턴을 발견하지 못하도록 초기 배치가 충분히 유연해야 함을 의미합니다.
게임 단계에서 DeepNash는 악용되는 것을 방지하기 위해 겉보기에 동일해 보이는 작업 간에 가능한 한 많은 무작위화를 시도합니다.
이 과정에서 정보를 숨기는 것은 매우 중요합니다.
정보를 숨기고 상대를 혼란스럽게 만드세요
실제 시나리오에서 사람들은 승리를 위해 허세와 같은 다른 수단도 사용할 것입니다.
"게임 이론의 아버지" von Neumann은 다음과 같이 설명했습니다. "실제 생활은 '허세', '작은 속임수', '내가 어떻게 할 것인지 추측'으로 가득 차 있습니다." Zhexuan의 "빨간 눈과 파란 눈의 자살 문제": 나도 알아, 그가 알고 있다는 걸 알아, 그가 알고 있다는 걸 알아...
이 점에서 DeepNash는 그다지 관대하지 않습니다.
액티브 블러핑은 자신의 체스 말이 높은 수준인 것처럼 가장하여 상대를 위협하는 것입니다. 쉽게 말하면 '허세 부리기'다.
이 예에서 DeepNash는 우리에게 좋은 교훈을 가르쳐주었습니다.
인간 플레이어(빨간색 측면)와 대결할 때 DeepNash(파란색 측면)는 게임 초반에 7(메이저)과 8(대령)을 희생했습니다. 조각 비용은 다음과 같습니다. 상대방의 10(원수), 9(일반), 8 1개, 7 2개를 식별합니다.
이 시점에서 DeepNash(파란색 측면)는 상대의 가장 강력한 조각을 많이 발견하는 동시에 자신의 핵심 조각을 숨겼습니다.
언뜻 보기에 DeepNash는 분명히 불리한 위치에 있는 것 같습니다. 7과 8이 아웃되었지만 인간 상대는 7위 이상의 모든 조각을 유지합니다.
그러나 마지막에는 DeepNash가 웃었습니다. 상대의 고위 경영진에 대해 감지한 믿을 만한 정보를 바탕으로 승리 확률을 70%로 추정했습니다.
결국 승리했습니다.
허세의 "기술"
포커에서 좋은 플레이어는 우리가 약할 때에도 상대방을 위협하기 위해 심리전을 펼칠 것입니다.
DeepNash도 이 허세 전략, 즉 네거티브 허세를 배웠습니다.
이것은 우리가 흔히 "돼지인 척하고 호랑이를 잡아먹는다"라고 부르는 것입니다. 높은 수준의 체스 말을 낮은 수준의 체스 말로 위장하고 상대가 속을 때까지 기다린 다음 단숨에 승리하는 것입니다.
아래 예에서 DeepNash는 2(매우 약하게 스카우트)를 사용하여 자신의 정체를 드러낸 상대의 8을 추적합니다.
인간 상대는 이를 통해 추적자가 10일 가능성이 높다고 판단하고 이를 스파이의 매복 서클로 유인하려고 합니다.
결국 DeepNash는 작은 체스말 2로 상대의 핵심 체스말 스파이를 파괴하는데 성공했습니다.
인간 플레이어(빨간색 면)는 자신의 8을 쫓는 알 수 없는 조각이 DeepNash의 10임에 틀림없다고 확신합니다(이때 DeepNash는 이미 유일한 9를 잃었기 때문입니다
다음은 DeepNash와 (익명) 간의 비교입니다. 인간 전문가) 게임 1, 게임 2, 게임 3, 게임 4의 완전한 게임 비디오를 클릭하면 더 많은 놀라움을 얻을 수 있습니다. (비디오 주소는 참고 자료에 나와 있습니다.)
DeepNash의 게임 레벨입니다. 인공적인 Stratego 플레이어가 인간 플레이어를 상대로 승리하는 데 필요한 수준에 근접했다는 소식을 들어본 적이 없습니다.
하지만 직접 상대한 후 Gravon에서 상위 3위 안에 들 것이라고 예상합니다. 인간 세계 선수권 대회에 참가하는 것이 허용되면 잘 될 것입니다
—— 논문 공동 저자, 전 Stratego 세계 챔피언 Vincent de Boer
볼 수 있습니다, 이 소설 R-NaD DeepMind의 방법은 완벽하거나 불완전한 정보를 가진 다른 2인용 제로섬 게임에 직접 적용할 수 있습니다.
R-NaD는 2인용 게임 설정을 넘어 대규모 현실 문제를 해결할 수 있는 잠재력을 가지고 있습니다
In 또한 R-NaD는 다른 목표를 가진 다른 분야에서도 AI의 새로운 응용을 열어줄 것으로 예상됩니다.
예를 들어, 사람들이 다른 사람의 의도나 환경 정보를 알지 못하는 교통 관리의 규모 최적화에서 R-NaD는
인간 세계는 본질적으로 예측할 수 없습니다.
이제 사람들은 불확실성에도 불구하고 강력한 AI 시스템을 만들어 인류의 미래에 대한 희망을 갖게 되었습니다.
http://www.science.org/doi/10.1126/science.add4679
https://www.nature.com/articles/d41586-022-04246-7
https :/ /www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information
https://youtu.be/HaUdWoSMjSY
https://youtu.be/L-9ZXmyNKgs
https://youtu.be/EOalLpAfDSs
https://youtu.be/MhNoYl_g8mo
위 내용은 DeepMind가 과학으로 돌아왔습니다! AI '월 브레이커'는 인간 주인을 물리치기 위해 속임수를 쓴다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
