보드 게임 "Go"NP가 완성 되었습니까?

많은 체스 AI가 주변에 있으며, 분명히 일부는 세계 최고의 선수를 이기기에 충분합니다.보드 게임 "Go"NP가 완성 되었습니까?

보드 게임 Go에 대한 성공적인 인공 지능을 작성하려는 많은 시도가 있었지만 지금까지는 평균 아마추어 수준을 넘어선 아무것도 상상하지 못했다고 들었습니다.

Go에서 주어진 시간에 최적의 이동을 수학적으로 계산하는 작업이 NP 완전 문제입니까?

2009-11-12 sharkin

Dunno 왜 당신은 downvoted있어. 이것은 합법적 인 질문입니다. +1 – mpen

현재 몬테카를로 (Monte Carlo)와 비슷한 알고리즘이 프론티어를 평균 아마추어 수준으로 밀어 넣었습니다. 찾아야 할 이름으로는 제니스 (Zenith), 많은 얼굴 (Faces of Go), 푸 에고 (Fuego), 릴라 (Leela) 등이 있습니다. – Svante

체스 앤 고는 모두 EXPTIME complete입니다. IIRC, Go는 가능한 움직임이 더 많기 때문에 체스보다 복잡성 등급이 더 높다고 생각합니다. 위키 백과는 이동의 복잡성에 대해 good article을 가지고 있습니다.

출처

2009-11-12 23:28:18 rmeador

+12

두 결과 모두 일반화 된 게임 버전에 대한 것이라고 말할 수 있습니다. 일정한 크기의 보드를 가진 게임은 항상 일정한 시간 내에 해결 될 수 있습니다. (비록 상수가 너무 커서 지금은 물론 지금까지도 처리 할 수 없습니다.) – ShreevatsaR

전문가가 "체스가 EXPTIME 완료되었습니다"라고 말하면 이해의 관점에서 볼 때 ShreevatsaR의 요지는 매우 중요합니다. – PeterAllenWebb

이동이 P에 불과하더라도 그것은 여전히 n 공백의 수와 m 일부 (대형) 고정 수입니다 O(n^m) 같은 끔찍한 일이 될 수 있습니다. P에 있다고해도 계산하기에 합리적이지 않습니다.

출처

2009-11-13 04:52:17 BCS

체스 또는 고 AI는 이동을 결정하기 전에 모든 가능성을 완전히 평가하지 않습니다.

체스 인공 지능은 검색 공간을 좁히고 보드의 주어진 위치가 어떻게 좋은지 정량화하기 위해 다양한 경험적 방법을 사용합니다. 이것은 가능한 보드 위치 14-15 개를 앞당겨 평가하고 좋은 위치로가는 경로를 선택하여 재귀 적으로 수행 할 수 있습니다.

보드 위치가 정량화되는 방법에 약간의 '마법'이 있습니다. 최상위 단계에서 AI는 단순히 이동 A> 이동 B로 이동하여 A를 움직일 수 있습니다. 그러나 조각 수는 제한되어 있으므로 그들은 모두 양적 가치를 지니고있어 '충분히 좋은'알고리즘을 구현할 수 있습니다.

그러나 프로그램에서 Go에서 두 가지 보드 위치를 평가하고 A> B 계산을하는 것이 훨씬 더 어려워졌습니다. 그 중요한 부분이 없으면 AI의 나머지 부분을 만들기가 조금 힘듭니다.

출처

2009-11-28 05:28:53

보드 게임 "Go"NP가 완성 되었습니까?

답변

관련 문제