고모 쿠 (Gomoku) 보드 표현

Question

고모 쿠 게임을하고 있는데 보드 상태를 저장하는 효율적인 데이터 구조가 필요합니다. 2D 배열에 저장하려고 생각했지만 더 많은 것이 있습니다. 효율적인 방법. 감사합니다

Answer 1

당신이 주로 색인 조회를 수행 할 것이라고 생각하기 때문에, 배열은 거의 최선의 선택이 될 것입니다 - 낮은 상수 요소로 일정 시간에이 조회를 지원합니다. 공간 효율성의 측면에서

:

각 사각형 빈, 또는 두 선수에 의해 채워 될 수 있습니다. 따라서 최대 세 가지 가능성이 있습니다. 공간 효율성을 극대화하기 위해 전체 보드를 base-3 표현으로 저장할 수 있지만, 컴퓨터가 바이너리로 작동하기 때문에 주어진 사각형의 값을 결정하기 위해 전체 보드를 처리해야합니다 (따라서 간단히 인덱스 조회가 가능합니다). 보드의 크기에 비례 한 시간이 걸릴 것입니다. - 시간이 이라면 실제로은 문제가되지 않습니다. 대신 사각형 당 2 비트를 사용하는 것이 좋습니다. 이렇게하면 네 가지 가능성 중 하나를 나타낼 수 있습니다 (네 번째는 사용되지 않습니다).

많은 언어에는 비트 집합 구현이있어 비트 배열로 작업 할 수 있습니다. 위의 경우에 적합합니다.

2D 구조로 작업 할 때 일반적으로 약간의 메모리 오버 헤드가 있기 때문에 2D 비트가 아닌 비트 맵을 원할 수도 있습니다. 2D에서 1D 로의 변환은 간단합니다. x*height + y 또는 y*width + x을 사용하여 2D 색인을 1D로 변환 할 수 있습니다.

비록 내가 Gomoku 보드가 일반적으로 작아서, 부피가 큰 표현조차도 완벽하게 작동 할 것이라고 생각합니다. (일부 인공 지능 기술은 보드의 많은 복사본을 만들지 만, 만약 당신이 그렇게한다면, 최소한의 표현은 의미가있을 것입니다.)