오래된 체스 게임에 최첨단 현대 기술을 적용하면 어떻게됩니까? 컴퓨팅 파워의 잉여와 지루 괴짜 게임에 자신의 이상한 가정 실험을 수행 할 때 어떻게됩니까?
올해 자신을 톰 머피 7 세라고 부르는 펜실베니아 소프트웨어 엔지니어는 기계 학습과 신경망에서 불필요한 양의 중앙 처리 장치 사이클에 이르기까지 모든 것을 사용하여 우스꽝스럽게 나쁜 체스 플레이 알고리즘을 만들기로 결정했습니다.”
“재미에 대한 나의 생각입니다…”머피는 실험을 설명하는 유머러스 한 비디오에서 말합니다.
첫 번째 움직임
머피는 그것을 해낼 수있는 지력을 가지고 있습니다. 그는 2007 년에 컴퓨터 과학 박사 학위를 옹호했다고 말합니다. 같은 해인 카네기 멜론에서 학생들은 만우절에 매년 시그 보빅 회의를 개최하기 시작했습니다. “전산 이단 협회”가 후원 한 것은”해리 퀴즈 마스터 보빅”이라는 가상의 연구원에게 헌정 된 풍자적 인 특별 이익 집단이었고”인공 어리 석음”과 같은 주제에 대한 바보 같은 논문에 대한 호출을 포함합니다.”
지난 11 년 동안,머피는 구글의 고위 직원 소프트웨어 엔지니어(피츠버그 사무실)이었다. 그러나 올해 그는 만우절 회의에 다시 돌아하기로 결정-그리고 다시,자신의 일부 유머러스 한 연구를 기여했다.
머피는 자신의 과거 프리젠 테이션 중 일부는’실제’연구와 구별 할 수 있었다 말도 조사를 포함 자랑스럽게 자랑(예를 들어,슈퍼 마리오 브라더스의 첫 번째 수준은 사전 편찬 순서와 쉽게 시간 여행은’실제’학술 연구에서 약 20 인용이).
하지만 머피는 체스에 관심을 돌렸다.
게임 시작
머피의 초기 게임에서 인간 플레이어는 눈을 가리고 조각이 어디에 있는지 기억하도록 강요합니다. 그러나 컴퓨터에 해당하는 것은 무엇입니까? 조각이 어디에 있는지 말하고 있지만 어떤 조각이 있는지(또는 어떤 색인지)말하지 않습니다)…
물론,컴퓨터도 위치로 이어지는 움직임을 제공하지 않을 것입니다. 그것은 누구의 차례인지 알지 못할 것입니다. 예,컴퓨터의 왕이 체크에 있다는 가능성이있다-어느 시점에서 거의 모든 움직임은 안전에 왕을 리드 이동을 제외하고 불법입니다. 하지만 그 주위를 얻을,톰 가능한 이동의 목록을 생성 하는 프로그램을 만들어,우선 순위의 순서로 순위—첫 번째 법적 이동 선택 됩니다.
“나는 그것에 대해 재생 좋아,그것은 매우 좋지 않기 때문에,”머피는 비디오에서 말한다. “그러나 자연스러운 질문은 그것이 얼마나 좋지 않은가?”체스 재생 프로그램에 대해 그것을 테스트하는 것은 예,그것은 큰 규칙 성으로 잃는 것을 증명한다-에서와 같이,”매 시간.”
그런 다음 그는 다른 나쁜 체스 재생 알고리즘을 구축하기 위해 착수하여 상대적인 성능을 비교할 수있었습니다…
하나는 흰색 재생할 때 흰색 사각형에 조각을 배치하는 선호했다,그리고 검은 색 재생할 때 검은 색 사각형에. (상대방? 반대 색깔의 사각형에 그 조각을 배치 선호하는 알고리즘. 결국 둘 다 꽤 심하게 뛰었습니다. “그들은 선호를 가지고 있지만,정말 승리와 함께 할 필요가 없습니다.”사실,둘 다 무작위로 움직임을 선택하는 알고리즘보다 조금 더 나쁩니다.
당신이 지루 보드에 어떤 조각 모른 채 체스를 재생 내 프로그램을 평가하기 위해 바보의 대회에서 경쟁 30 이상한 체스 알고리즘에 대한 내 복잡한 42 분 비디오를 찾을 경우 예술을 이해하지 않기 때문에,그것은이다:https://t.co/DkaEBGrwAf
— 톰 7(@톰 7)7 월 15, 2019
그는”허들”과”스웜”이라는 두 가지 알고리즘도있었습니다.이 알고리즘에서는 한 명의 자동 플레이어가 조각을 자신의 왕과 가깝게 유지하는 동작을 검색하고 다른 플레이어는 상대방의 왕 근처에 조각을 배치하는 동작을 검색합니다. 이것은 때때로 허들의 왕이 전반적으로 자신의 폰을 따라 가도록 강요 당하게되며,적어도 몇 가지 경우에는 폰이 실수로 더 강력한 조각으로 승격되어 실수로 반대 왕을 체크했습니다.
그러나 더 자주,그것은 다른 방식으로 작동합니다. “당신은 상대를 공격 할 수있는 환경 설정이있는 경우,당신은 실수로 때때로 장군거야.”비디오에서 머피는 나쁜 체스 알고리즘 중,이 하나는 놀라 울 정도로 나쁘지 않은 것을 알 수있다. “‘떼’는 사실’무작위 이동’보다 훨씬 낫습니다.'”
또 하나의 성공적인 전략은 네 가지 특정 종류의 움직임(이 순서대로)을 우선시하는 알고리즘입니다.
그러나 다른 끔찍한 아이디어가있다—그 상대의 조각을 반영하거나 보드의 반대편에 그 조각을 모두 이동하고자하는 알고리즘처럼. 하나의 알고리즘은 단순히 알파벳 순서로 먼저 오는 중 이동을 선택합니다.
그리고 각각의 움직임은 가능한 움직임의 목록에서 선택되는 또 다른 알고리즘이있다—선택은 파이의 숫자에 의해 임의로 결정으로…
체스 랜드에서 생존
그러나 궁극적으로 그의 가장 정교한 알고리즘은 질문으로 시작: 게임의 끝을 통해 보드에 남아,그 동료 체스 조각의 모든 승리 신흥—어떤 단일 체스 조각은”생존”대부분 가능성이? 충실하게 답을 조사,머피는 무료/리브레 체스 사이트를 방문 지불 LiChess.org (지금은 하루에 백만 개 이상의 게임을 볼 수 있습니다). 또한 다운로드를위한 게임을 제공합니다—그래서 머피는 그 중 모든 506,000,416 다운로드.
그는 그의 방법론을 설명하는”체스랜드에서의 생존”이라는 논문에 결과를 요약했다. 머피는 2018 년 11 월까지 모든 완전한 게임을 다운로드했지만,이후 8 개월 만에 2 억 명이 추가로 출시되었습니다. 심지어 그의 11 월 어획량은 체스 게임의 무려 8 백 75 기가바이트을 표현,”그래서 이러한 처리 효율성과 병렬 처리에 대한 몇 가지주의를했다,”머피는 비디오에서 말한다.
“다행히,나는 코어와 진정으로 과도한 램의 단지 음란 번호와 컴퓨터가,그래서 당신은 뭔가를 사용 해.”
어,얼마나 음란? 이메일에서 그는 자신의”무상”홈 시스템에 대해 설명합니다. 몇 시간 동안 멀티 스레드 씨++프로그램을 실행하면 전체 데이터 세트를 통해 위기에 충분했다. “나는 사람들이 당신이 하나의 기계로 효율적으로 무엇을 할 수 있는지 과소 평가 생각!”
“관련된 작업은 매우 간단합니다: “
“나는 기본적으로 처음부터 모든 코드를 썼다,이 작업을 다른 사람의 코드를 얻는 것보다 더 재미 있기 때문에. :)”
머피의”생존 가능성”분석은 데이터의 정말 아름다운 시각화를 만들어 64 개의 사각형(게임이 끝날 때 그 사각형에있을 가능성을 나타내는 색상)의 모든 체스 조각에 대한 생존 확률을 보여줍니다.)
그리고 이것은 더 나쁜 체스 플레이 알고리즘으로 이어졌습니다. 첫째,단지 그들이 통계적으로 생존 할 가능성이있어 그 사각형으로 조각을 이동 하나가있다. 또는 단순히 그들이 게임의 끝에있을 가능성이 가장 높은 사각형에. 그리고 다른 알고리즘은 정반대입니다—조각을 생존(또는 결국)할 가능성이 가장 적은 사각형으로 이동합니다. 두 가지 알고리즘은 각 사각형의 조각에 대해 가장 높은 생존율(캡처 속도 대)을 갖는 정사각형을 계산하며,하나의 알고리즘은 생존을 선호하는 가장 높은 비율을 찾고”치명적”알고리즘은 가장 낮은 비율을 찾습니다.
“이상하게,그것은 이러한 전략의 최고의 승리 기회를 가지고.”
그리고 마지막으로,그는(그것의 가장 유망한 움직임을 재생하도록 강요있어 특별한 알고리즘을 포함하여)여러 수준에 건어 체스 엔진에’그들 모두를 비교하기로 결정했다. “결과를 보면 놀랍지 않게 이것이 전반적인 최악의 전략이며 거의 모든 사람들에게 패배를 안겨줍니다.”
그러나 톰의 원래”눈가리개”알고리즘을 기억하십니까? 그는 기계 학습을 수행 한 신경망으로 그것을 보강하기로 결정했습니다.이 네트워크는 리체스의 게임에서 사용할 수있는 수십억 개의 위치를 사용합니다.조직. 이제 각 위치에서 실제 조각을 100%정확도로 정확하게 예측할 수있었습니다…약 5 분의 1 시간. 그리고 그것이 틀린 경우에도 각 위치에 대해 평균 3.22 조각을 잘못 추측합니다.
그리고 이것은 훨씬 더 거친 계산을위한 점프 오프 포인트가됩니다. 어떤 시점에서,그는 자신의 데이터베이스에있는 모든 게임은 결국 21,553,382,902 독특한 위치를 통과 추론. 204 기가바이트와 함께 당신은 그들 모두를 저장할 수—다음 움직임과 함께-하지만 또 다른 흥미로운 통계가있다. 포지션의 무려 76%가 정확히 한 번 발생했습니다. “그래서 이것들은 많은 공간을 차지하며,나는 그들을 다시 볼 가능성이 거의 없기 때문에 놀기에 매우 유용하지 않습니다.”이 일회성 위치를 버리고,다른 모든 가능한 게임 위치는 메모리의 약 5 백메가바이트로 저장할 수 있습니다. 이 쉽게(그 자체가 고유 한 위치에 갇혀 찾을 일이 경우 임의의 이동에 교환하는 동안)가 발생하는 모든 위치에 대한 가장 인기있는 움직임을 재생하는 알고리즘으로 변환 할 수 있습니다.
그러나 그것을 때리는 쉬운 트릭이 하나 있습니다. “즉시 내가 이상한 움직임의 조금을 만들 때,그냥 무작위로 재생을 시작합니다. 그리고 그것은 매우 쉽게 이길 수 있습니다.”
최종 실험에는 건어 엔진의 다양한”희석”이 포함되며,선호하는 움직임은 무작위로 선택된 움직임으로 대체됩니다.”
“우리는 실제로 플레이어가 건어의 특정 희석에 직접 비교함으로써 지금 얼마나 좋은 평가할 수 있습니다…”
머피의 정교한 체스 플레이 알고리즘의 모든 충실하게 테스트 한 후,그는 하나의 거대한 테이블에 결과를 요약,그리고 의기 양양 그가 마침내 다른 이익을 추구 할 준비가 발표하여 자신의 비디오를 체결했다.
“이제 다음 프로젝트로 넘어갑니다.이 프로젝트는 이 개에게 체스를하는 법을 가르치는 것입니다.”
- 기계 학습이 인류를 우리가 이해하지 못하는 답변으로 인도 할 때 어떤 일이 발생합니까?
- 국수 만드는 로봇 소피를 만나다.
- 15 년 후,연구자들은 느낄 수있는 인공 팔을 공개합니다.