게임 트리를 만들 때 어떤 모듈을 사용해야합니까?

Question

저는 Python 코딩 클래스 용 프로젝트를 작성 중이며 질문이 있습니다. 나는 Reversi 엔진을 쓰고 있는데,이 엔진은 게임에서 몇 가지 움직임을 보일 것이고 그 다음에 그것이 최선이라고 생각하는 움직임을 고를 것이다. 필자는 Python이이 언어에 이상적인 언어가 아니라는 것을 이해하지만 (다른 언어만큼 빠르지 않기 때문에) 최소한 기능적이지만 조금 느린 코드를 작성하는 것이 가능하다고 생각합니다.

즉, 저는 게임 보드 (매트릭스라고 생각하십시오)와 정수를 보유 할 게임 트리라는 두 개의 테이블을 만들려고합니다. 나는 메모리 효율이 높고 빠른 것을 사용하여 항목을 추가, 삭제 및 읽는 것을 원합니다.

지금 사용하고있는 보드는별로 효율적이지 않습니다. 나는 누군가가 (모듈을 사용하는 방법에 대한 지침과 함께) 어떤 모듈을 제안했는지 물어보고 싶었다. (예 : array, numpy; 나는 다음 중 하나를 사용하는 방법을 모른다.) :

self.board = [[0, 0, 0, 0, 0, 0, 0, 0,], 
       [0, 0, 0, 0, 0, 0, 0, 0,], 
       [0, 0, 0, 0, 0, 0, 0, 0,], 
       [0, 0, 0, 1, 2, 0, 0, 0,], 
       [0, 0, 0, 2, 1, 0, 0, 0,], 
       [0, 0, 0, 0, 0, 0, 0, 0,] 
       [0, 0, 0, 0, 0, 0, 0, 0,], 
       [0, 0, 0, 0, 0, 0, 0, 0,]] 

게임 트리의 경우 목록의 목록이 얼마나 가벼운 지에 따라 아이디어가 있습니다. 나는 표준 파이썬으로 작성된 함께 일하고 있어요 아이디어는 유사하다 : 각 %는 위의 보드 중 하나 (:하지 굽이마다 정확히 세 가지 옵션을 가지고 있으며, 이상적인 이상입니다) 것

tree_zero = % 

tree_one = [%, %, %] 

tree_two = [[%, %, %], [%, %, %], [%, %, %]] 

tree_thre = [[[%, %, %], [%, %, %], [%, %, %]], 
      [[%, %, %], [%, %, %], [%, %, %]], 
      [[%, %, %], [%, %, %], [%, %, %]]], 

tree_four = [[[[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]]], 

      [[[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]]], 

      [[[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]], 
       [[%, %, %], [%, %, %], [%, %, %]]]] 

. 하지만 이것은 느리고 무거운 물건으로 파이썬이 메모리를 효율적으로 사용하기 어렵습니다 (특히 4가보다 깊다면).

누구든지 이와 같은 프로그램을 사용해 본 적이 있거나 수입 할 효율적인 모듈 아이디어가 있다면 알려주십시오!

게임 트리의 예를 들면 wikipedia page과 특히 페이지의 첫 번째 그림을 생각해보십시오.

EDIT : 이상적으로, 앞으로 네 가지 움직임을 바라는 것이 이상적입니다. 이것은 처음 네 레벨이 어떻게 보이는지 보여주는 예입니다. 또한 사용하기 위해 주변에 떠 다니는 주어진 나무의 사본이 여러 개있을 것입니다. 속도는 이와 같이 기하 급수적으로 커지는 것에 중요합니다.

Answer 1

제 의견으로는 파이썬은 이런 종류의 작업에 완벽하게 어울립니다! 즉, 나는 파이썬을 사용하는 보드 게임을 위해 AI를하는 데 엄청나게 재미 있고 생산적인 시간을 보냈습니다.

첫 번째 권장 사항은 Bit Boards입니다. 여기 응용 프로그램 예제는 체스를위한 것이지만 개념은 Reversi에 완벽하게 전달할 수 있습니다. 세트 크기 보드에서 조각의 존재를 나타 내기 위해 0과 1을 사용하면 메모리 공간이 적을뿐만 아니라 계산 속도가 빨라진다는 장점이 있습니다 (비트 연산은 평등보다 빠릅니다).

또한 재귀를 구현하기 위해 모델을 다시 디자인해야합니다 (점수 매기기 기능으로 촉진). 이러한 구현은 단일 함수를 작성하여 1,2,3,4 이동에 대한 로직을 예상하고 하드 코딩하지 않고 무한 이동 깊이를 확장하거나 (또는 ​​오히려 디자인에 의해 제한되며 리소스에 의해서만 제한됨) . 이 효과에 대한 잘 설계된 기능은 양측 (플레이어)에 대해 작동하며, 임계 값 (사용자가 선택한 기준, 계산 된 위치/실시간 소비 한 값으로 정지)에 맞는 최상의 옵션을 선택하기 위해 중단 될 수 있습니다.

참고로 여기에 board game called Thud에 대한 github이 있습니다. 프로그램과 거의 동일한 요구 사항으로 만들었습니다. 여기서 저는 17x17 보드, 세 가지 다른 조각 및 두 가지 전략으로 작업했습니다. 우리 모두 볼 수있는 것은 Reversi의 규칙보다 훨씬 복잡합니다.

아, 좋은 재귀 모델도 멀티 스레딩을 수용합니다!