Journal Archive

등식 맞추기 성냥개비 퍼즐 게임의 설계 목표는 그림 1과 같이 문자열로 주어진 초기 수식을 성냥개비 배치 저장 구조로 변환한 후, 주어진 개수 이내의 성냥개비를 옮겨 등식이 만족되는 경우가 있는지를 탐색하는 데 있다. 이때, 수식은 성냥개비 배치 저장 구조를 등식 문자열로 변환하여 계산하는 방법이 편리하다. 그림 2에 등식 맞추기 성냥개비 퍼즐 게임의 전체적인 깊이우선 재귀호출 알고리즘을 보였다.

Fig. 1. 
Conversion between internal structure of matchstick layout and equation string

Fig. 2. 
Rough algorithm for the matchstick equation puzzle game

성냥개비를 이용하여 숫자를 표현하는 방법은 그림 3의 7-세그먼트 형식과 동일하다. 그림 4에 7-세그먼트의 각 요소를 ‘0’ ~ ‘9’의 숫자와 ‘+’, ‘-’ 연산자의 모양에 따라 7-세그먼트의 A에서 G까지의 순서로 0~6번 비트에 대응시킨 각각의 비트 패턴 및 이들과 아스키 코드와의 변환 테이블을 위한 구현 코드를 보였다. 여기서 Seg_bit[]는 ‘0’~‘9’, ‘+’, ‘-’에 대한 7-세그먼트 비트 패턴을, Seg_map[]은 7-세그먼트 비트 패턴에 대한 ‘0’~‘9’, ‘+’ ,‘-’을 대응하는 테이블이다.

Fig. 3. 
7-segment for digit presentation of matchstick

Fig. 4. 
Implemented code for 7-segment bit [attern for digit and operator, and conversion table with ASCII code

성냥개비 등식 퍼즐 게임의 일반적인 배치는 7-세그먼트를 기반으로 그림 5와 같이 모델링할 수 있고, 이 모델에서 ‘=’을 위한 세그먼트는 실제로 배치할 필요가 없다. 그림 5에 나타난 약어들의 의미는 아래와 같고, 이를 구현한 코드는 그림 6에 보였다. 여기서 Seg_lay[]는 7-세그먼트로 표현되는 성냥개비의 전체 배치를 저장하는 내부 구조이다.

• ∘ NDGT : number of digits
• ∘ NSEG : number of 7-segment for matchstick layout
• ∘ OPSN : segment position of operator symbol
• ∘ EQSN : segment position of equal symbol

Fig. 5. 
Modeling for matchstick equation puzzle game layout

Fig. 6. 
Implemented code for model of fig. 5

초기 등식 문자열은 성냥개비 이동 과정을 추적하기 위해 내부의 7-세그먼트 배치로 변환되어야 한다. 또한, 성냥개비가 이동된 후 등식의 만족 여부를 판단하기 위해서는 7-세그먼트 배치의 내부 구조가 등식 문자열로 변환되어야 한다. 그림 7에 이들 상호간의 변환 프로시저를 보였는데, seg_get() 프로시저는 현재 숫자가 완성되지 않은 상태라면 flase(=0)를 리턴한다. 그림 9는 그림 5의 성냥개비 배치의 내부 저장 내용을 그림 8의 예와 같이 각각의 7-세그먼트를 다섯 줄로 나누어 콘솔 화면에 출력하는 프로시저이다.

Fig. 7. 
Procedure for conversion between equation string and 7-segment

Fig. 8. 
An example of console output for matchstick layout

Fig. 9. 
Procedure for outputting matchstick layout to console

성냥개비의 현재 배치 상태에 대한 등식을 체크하기 위해 내부 저장 상태를 “0+3=09” 형태의 등식 문자열로 변환한 후, ‘=’ 기호를 기준으로 분리한 양쪽 수식을 계산하여 그 결과를 비교한다. 이를 위한 프로시저 seg_cal(char *exp)의 구현 코드는 생략하도록 한다.

7-세그먼트 ss의 bs 구성 요소(비트)를 세그먼트 sd의 bd 구성 요소로 옮기기 위해서는 아래의 세 가지 절차가 필요하다.

• ∘ ss 세그먼트의 bs 구성 요소가 채워져 있는지 체크한다.
• ∘ sd 세그먼트의 bd 구성 요소가 비어있는지 체크한다.
• ∘ 위 두 가지 사항이 만족한다면 ss 세그먼트의 bs 구성 요소를 비우고, sd 세그먼트의 bd 구성 요소를 채운다.

‘±’의 연산자 세그먼트에 대해서는 특정 구성 요소가 아닌 현재 값을 기준으로 채움과 비움이 결정되어야 하는데, 현재 값이 ‘+’라면 더 이상 받을 수 없는 채움 상태이고, ‘-’이면 하나를 받아 ‘+’가 될 수 있는 비움 상태로 판단한다. 그림 10에 성냥개비의 이동을 처리하는 프로시저를 보였다.

Fig. 10. 
Procedure for movement process of matchstick

일반적인 게임 트리는 현재 선택 가능한 행동별로 이후에 이루어질 수 있는 가능한 모든 행동 조합들을 경우의 수로 분류하여 이번에 취할 최선의 선택을 제안하는 이잡기식 혹은 완전 알고리즘(exhaustive algorithm, brute-force algorithm)[16],[17] 형태이다. 이잡기식 알고리즘은 미래의 상태 변화가 고정되는 결정론적 게임 트리에서 가능하고, 그 구현 방법은 간단명료하지만 요구되는 메모리 용량이나 계산량이 한계를 넘으면 트리 전체를 전개할 수 없기 때문에 곤란하다. 따라서 대부분의 게임 트리는 주어진 일정 단계까지만 전개하고, 그 시점에서의 승리 가능성에 AI 기법등을 활용하는 평가 함수를 도입한다.

성냥개비 등식 퍼즐 게임에서는 옮기는 성냥개비 개수가 1~3개 정도로 제한되므로 게임 트리를 끝까지 전재할 필요가 없고, 각 단계에서의 평가는 등식의 성립 여부이므로 그림 1에 보였던 결정론적 게임 트리 유형의 적용을 고려할 수 있다. 다만, 성냥개비를 옮긴 후의 새 국면(배치)에서 이전의 국면으로 되돌아가거나 이미 탐색되었던 등식과 중복된 결과를 얻을 수 있다는 점이 다르기 때문에 이에 대한 대응책이 필요하다.

우선, 이전 국면으로 되돌아가는 상황은 다음과 같이 식별할 수 있다.

• ∘ 옮겨 놓은 성냥개비를 또 다른 곳으로 옮기려고 하는 경우
• ∘ 이미 한 번 옮겨서 비어있는 곳으로 옮기려고 하는 경우

이를 위한 방법은 새로운 국면으로 진입하는 과정 즉, 성냥개비의 이동 이력을 스택 구조로 관리하고, 옮기려는 성냥개비의 출발지나 도착지가 스택에 존재하는지를 체크함으로써 가능하다. 그림 11에 성냥개비 이동 과정 추적 및 체크를 위한 trc_*() 프로시저들을 보였다.

Fig. 11. 
Procedure for matchstick movement tracking

다음으로, 탐색 결과가 이미 탐색을 마친 등식과 중복되는 지는 아래와 같이 식별할 수 있다.

• ∘ 동일한 이동이지만 순서만 다른 경우
• 　이를테면 a→x, b→>y의 이동 결과는 b→y, a→x의 이동 결과와 동일하다.
• ∘ 이동은 다르지만 결과가 동일한 경우
• 　이를테면 a→x, b→>y의 이동 결과는 a→y, b→x의 이동 결과와 동일하다.

위 두 가지 모두를 체크하는 방법으로, 지금까지 발견된 이동 경로 각각에 대한 출발지점들의 집합 Sk, 도착지점들의 집합 D_k, 이번에 발견된 이동 경로의 출발지점 집합 S, 도착지점 집합 D를 각각 정의하고, “S_k ≡ S and D_k ≡ D ”인 k가 존재하는지를 체크하는 방안을 생각할 수 있다. 그런데, 출발지점 집합과 도착지점 집합이 동일하면 그 결과인 등식도 동일하므로 여기서는 발견된 등식들을 관리하여 비교하는 방법을 적용한다. 그림 12에 탐색 결과의 중복성을 체크하는 seg_new() 프로시저를 보였다.

Fig. 12. 
Procedure for checking redundancy of equation

앞에서 언급한 자료구조 및 프로시저들을 기반으로 그림 2의 알고리즘을 구현한 코드를 그림 13에 보였고, 그 개략적인 내용은 다음과 같다.

Fig. 13. 
Implemented code for algorithm of Fig. 1

• ∘ 성냥개비 하나를 옮길 때마다 등식 만족 여부를 체크하여 만족하는 경우 그 결과를 출력한다.
• 　- move(), seg_new()
• ∘ 변화된 새 국면으로 내려가 이전 국면에서와 동일한 과정으로 새로운 탐색을 진행한다.
• 　- game_DFS()
• ∘ 새로운 국면으로 내려왔을 때 국면의 깊이가 한계에 다다르면 리턴한다.
• ∘ 이동이 가능한 모든 조합(성냥개비가 놓인 곳의 위치와 비어있는 곳의 위치) 각각을 하나씩 특정한다.
• 　- ss: source segment number
• 　- sb: source bit number in the ss segment.
• 　- ds: destination segment number
• 　- db: destination bit number in the ds segment
• ∘ 특정된 이동 조합에 대하여 위 과정을 반복한다.