[45호]은정-Go(인공지능 체스로봇)

2017 ICT 융합 프로젝트 공모전 입선작

은정-Go(인공지능 체스로봇)

글 | 단국대학교 김은정, 김건희, 곽영우

1. 심사평
칩센 얼핏 보기에 구성 방법이 쉬워 보이지만, 기본 회로부 하드웨어의 구성, 모터 및 전자석을 이용한 말의 이동 등을 고려하면 machanic 부분뿐만 아니라 일부 머신 러닝까지 고려가 된 복잡한 작품으로 판단됩니다. 나름대로 고민하여 구성했을 알고리즘을 문서로 표현하기 위해 어려운 부분은 충분히 이해하지만, 알고리즘에 대한 설명이 너무 단편적이고 부족해 보이는 것도 사실입니다. 하지만 다시 말하지만 기술적으로 많은 부분에 대해 충분한 고려를 하고, 이를 융합하고자 시도한 기술 구성적 난이도 부분은 충분히 잘 했다고 생각됩니다.

뉴티씨 체스 인공지능을 실제 눈으로 보이게 해서 꽤나 흥미로웠습니다. 이 기술을 이용하면, 알파고 같은 인공지능 체스 기사가 나올 수도 있을 것 같습니다. 파이팅입니다.

위드로봇 재미있는 아이디어로 완성도 있는 결과까지 잘 도달한 것 같습니다. 전시회에서 많은 인기를 끌 것 같습니다.

2. 작품 개요
세계가 주목하고 있는 제4차 산업혁명의 주요 의제 중 하나일 만큼 인공지능 로봇은 이슈가 되고 있습니다. 실제로도 인공지능을 이용한 자율 주행 자동차도 도로에 나오고, 인공지능 바둑 알고리즘 알파고와 사람의 대결도 많은 이슈를 받았습니다. 은정-고는 인공지능 체스 알고리즘을 이용한 체스 로봇입니다. 현재 알까기 로봇이나, 장기 로봇 등 여러 대국 게임 작품들을 살펴보면, MFC만을 사용하여 하드웨어적인 요소가 없거나 영상 처리 등을 이용하여 프레임이나 집게 손이 장기 말을 이동하는 방식이 대부분을 차지합니다.

은정-고는 거기에 보다 사람들의 흥미를 유발할 수 있게 업그레이드하여 프레임을 감췄습니다. 겉으로 보기에는 체스 판위에 웹캠도 없이, 프레임도 없이 체스 말만 올라와 있지만 Computer와 User의 대국이 시작되면 User가 말을 움직이면, 그에 따라 Computer의 말이 저절로 움직여 대응을 하기 시작합니다.

3. 작품 설명
3.1. 주요 동작 및 특징
은정-Go는 인공지능 알고리즘을 이용한 지능형 체스 로봇으로 대국 게임이라는 것이 꼭 컴퓨터 상의 소프트웨어만으로 동작 되는 것이 아닌, 하드웨어를 포함한, 즉 로봇과 소프트웨어를 접목시킴을 제시하고 있습니다.

대부분의 인공지능 알고리즘과 하드웨어를 접목시킨 대국 로봇을 보자면, 대부분 영상처리를 이용하여 말을 파악하고, 집게 팔 같은 외관상 보이는 프레임으로 말을 움직이는 형태를 갖추고 있습니다. 그러나 은정-Go는 웹캠이 필요한 영상처리 대신 마그네틱 센서와 자석을 이용하여 말의 위치를 파악했습니다. 또한 외관상 보이는 집게 팔 대신 전자석과 스텝 모터 제어를 통해 프레임을 체스판 밑으로 감췄습니다. 따라서 오락적인 요소를 더욱 높였습니다. 또한 몇 수 앞을 내다볼 수 있는 Min-Max Algorithm을 개선한 Alpha-Beta Algorithm을 사용하여 Computer의 말들에게 이점이 되는 node만 선택하여 효율적으로 탐색하는 알고리즘을 사용하였습니다. 추가적으로 평가 함수를 사용하여 보다 지능적인 판단을 하여 더욱 유리한 대국을 이끌 수 있게 하였습니다.

전체적인 과정은 다음과 같습니다. User가 말을 이동하였으면, 그 좌표 값을 CPU의 gpio 핀에 연결된 마그네틱 센서가 인식을 한 후 말의 위치를 파악합니다. 센서로 파악된 말의 위치를 판별한 후 유리한 대국인지 먼저 평가를 합니다. 그 후 몇 수 앞을 내다봐서 가장 유리한 node를 찾는 알고리즘을 돌린 후 Computer의 말이 움직여야할 좌표 값을 찾습니다. 좌표 값을 찾은 후 진동이 적고 저속에서 토크가 쎈 바이폴라 스텝 모터 2개를 사용하여 x축, y축으로 이동합니다. 이때 User의 말을 먹게 되는 경우 User의 말은 밖으로 먼저 나온 뒤 모터가 움직이게 됩니다.

3.1.1. H / W
Ⅰ. 센서부
센서는 자석의 성질을 이용한 magnetic reed switch를 사용하였습니다. reed switch는 접점 부분이 비활성 가스를 충전한 유리관 속에 봉인되어 있는 스위치로, 자성이 가해지면 양쪽의 reed에 N극과 S극이 유도되어 자기 흡인력에 의해 reed가 붙게 됩니다. 따라서 전류가 흐르게 되고 자계가 소거되면 reed의 탄성에 의해 접점이 복귀됩니다. 따라서 각각의 말에 자석을 부착한 후 그 자성에 의해 좌표 값을 알게 됩니다. 그림 3에서 볼 수 있듯이 자석이 reed switch 중앙에 위치할 경우는 OFF가 되고 그 외에는 ON이 되므로 ON의 범위를 더 높이기 위해 체스 칸의 사이드에 센서를 부착하였습니다.

8*8로 이루어진 나무판 위에 센서를 64개 부착한 뒤 가로 세로를 각각 한 줄에 이어 CPU의 GPIO pin에 연결하였습니다. 이 때 reed switch만 연결 할 경우 다른 GPIO out pin으로 역류하는 ghost activations이 발생하므로 그것을 막기 위해 다이오드 1N4148을 부착하였습니다. 또한 구조상으로 센서를 빨간색 원안에 놓으면 ON이 되기 때문에 체스 칸의 길이인 55mm와 reed switch의 길이인 12mm를 고려하여 OFF되지 않는 범위 내에 말이 존재하도록 자석은 6mm인 네오디움 자석을 부착하였습니다.

Ⅱ. 모터부
스텝 모터에는 크게 유니폴라 스텝 모터와 바이폴라 스텝 모터가 있습니다. 유니폴라 스텝 모터는 각각의 코일에 1개의 권선만 지나기 때문에 1방향 밖에 전류가 흐르지 않습니다. 바이폴라 스텝 모터는 각각의 코일에 2개의 권선이 지나기 때문에 방향성이 존재하게 됩니다. 유니폴라 스텝 모터는 회로가 간단하며 고속 회전시 토크가 높습니다. 반대로 바이폴라 스텝 모터는 회로가 복잡하나 저속 회전시 토크가 높습니다. 따라서 저속 구동시 토크가 높고, 진동이 덜한 바이폴라 스텝 모터를 사용하기로 하였습니다. 모터 드라이버는 L298N을 사용하여 제어를 하였고, 2상 4선식 42BYGH2673A-C 바이폴라 스텝 모터 두 개를 사용하여 각각 x축과 y축을 이동하였습니다. 스텝 모터의 제어는 1상 여자 방식, 2상 여자 방식, 1-2상 여자 방식이 있는데, 선택에 따라 입력 pulse와 step의 특성이 달라집니다. 1상은 출력토크가 낮다는 단점이 있었고, 2상은 1상에 비해 배의 전원 용량이 필요하나 토크가 높아 난조가 일어날 확률이 낮습니다. 따라서 1상과 2상을 반씩 합쳐놓은 부드러우면서 토크가 적당히 쎈 1-2상 방식을 사용했습니다.

Ⅲ. 하드웨어 설계
하드웨어를 체스 판 아래에 감추기 위해서 보통의 대국 로봇과 다르게 하드웨어 설계를 했습니다. 우선, 모터 제어에 정확도를 높이기 위해 톱니를 내었고, 그에 맞는 레일을 깔았습니다. 그 후 모터가 바닥과 수평이 되게끔 철봉으로 수평을 맞췄습니다. 모터에 철봉을 관통하는 지지대를 고정시킨 후 모터를 작동시키면 수평으로 나아가게 하였습니다. Solid Works로 작업한 사진 속 그림 10번은 모터가 움직이는 한 세트이고, 그 세트가 총 두 개가 존재합니다. 밑에 있는 y축 모터 위에는 x축 모터를 부착하였고, x축 모터 위에는 전자석을 장착하여 알고리즘을 돌리고 난 후 나온 좌표 값에 의해 밑에 자석이 붙어 있는 말이 움직이게 됩니다.

3.1.2. Algorithm
Ⅰ. 센서부
우선, 자석이 붙은 말의 위치를 reed switch 센서로 알아내야 합니다. 첫째로 switch-case 문을 사용하여 LOW0번부터 LOW7번까지 순서대로 ON 시킨 후 OFF 시키는 것을 반복하였습니다. LOW0가 ON이 되어 있을 때 COL0번부터 COL7번까지 탐색한 후 OFF 시키고, 다음에 LOW1이 ON이 되어 있을 때 또 COL0번부터 COL7번까지 탐색한 후 OFF 시키고 그 다음을 반복하였습니다. 자석이 체스 칸 위에 있을 경우 reed switch 센서의 접점이 물려 전류가 흐르게 되고, LOW는 0부터 7까지 ON, OFF를 반복하므로 COL의 GPIO pin에 신호가 오게 되면, x축의 좌표 값은 LOW의 GPIO pin, y축의 좌표 값은 COL의 GPIO pin임을 알 수 있습니다.

둘째로, 밑에 자석이 붙은 말이 움직임에 따라 0과 1로만 나타내는 것이 아니라 User가 말을 들어 올린 말이 User의 말인지 Computer의 말인지의 정보도 있어야 합니다. 또한 어떠한 말인지의 정보도 있어야 합니다. 우선 말이 들어 올린 경우를 구분하기 위해 position을 pre와 next로 나눴습니다. 말이 들어 올려진 경우는 위치 정보가 1이었다가 0이 됩니다. 또한 말이 내려진 경우는 위치 정보가 0이었다가 1이 됩니다. pre_position은 말이 움직이기 전 상태를 말합니다. 만약 pre_position이 1인 말의 next_position이 0이 될 경우 들어올려진 경우로 파악합니다. 또한 pre_position이 0인 말의 next_position이 1이 될 경우는 들어 올려진 말이 내려진 경우라고 파악합니다.

셋째로, 들어 올려진 말이 User의 말인지 Computer의 말인지 구분하기 위해 체스의 처음 정보, 즉 처음 세팅 값은 룰로써 정해져 있기 때문에 User은 -의 점수 Computer은 +의 점수로 구분하였습니다. 또한 말들마다 점수의 차이를 주어 말마다의 가치를 나눴습니다. 그 정보들을 User가 말을 들어 올릴 때 다른 변수에 저장을 해놓고 User가 말을 내려놓을 때 그 정보들을 입력 받는 알고리즘을 짰습니다. 이 때 말을 들어 올리는 행위는 User만 하는 행위이므로 만약 검은색 말, 즉 +의 점수가 들어 올려 졌을 경우는 User가 Computer의 말을 먹는 상황이라고 파악합니다.

Ⅱ. 모터부
우선, 스텝 모터의 기본 원리는 상을 순서대로 ON 시키면서 회전을 하는 것입니다. 사용한 모터는 2상 4선식 바이폴라 모터이므로 A, B, A’, B’의 순서로 GPIO pin에 연결하였고, CPU의 Timer Interrupt를 사용하여 차례대로 GPIO pin을 ON시켜 모터를 구동 하였습니다. Timer Interrupt 주기는 10로 설정하였고 모터의 속도와 가속도를 설정하기 위해 가속도 공식을 사용하여 수식을 세워 함수로 만들었습니다.

말을 움직이기 위해서는 x축의 모터가 -x방향과 +x방향 둘다 자유자재로 움직일 수 있어야 합니다. 이때 스텝 모터는, 구동을 하던 방향을 바꾸기 위해서는 ON 시켜주는 GPIO pin의 순서를 반대로 해주면 되므로, Timer Interrupt를 멈춘 뒤 순서를 반대로 해주었습니다. y축 모터도 마찬가지 이므로 모터를 움직이는 함수는 총 4개로 모터의 마지막 위치에서 가야할 위치에 따라 +x+y, -x+y, +x-y, -x-y 를 판별한 후 모터를 구동하였습니다.

Ⅲ. AI Algorithm
체스 알고리즘은 몇 수 앞을 내다볼 수 있는 Min-Max 알고리즘을 바탕으로 구현하였습니다. Min-Max 알고리즘이란 Computer가 유리한 값은 크고, User가 유리한 값은 작게 가치를 두어 노드를 뻗어나가는 알고리즘입니다.

즉, Max는 Computer, Min은 User입니다. 노드의 깊이를 3이라고 두면, 마지막 노드에서부터 위로 올라가면서 Max, Min을 판별하여 가장 가치 있는 노드를 선택합니다. 어미가 Min인 경우 뻗어나간 자식들 중 제일 작은 가치를 고릅니다.

이것은 User가 경우의 수 들 중 가장 User에게 유리한 경우를 선택한다고 가정한 선택입니다. 그리고 그 위에 올라가면 어미가 Max가 되는데, Max는 Computer가 둘 수 있는 가장 좋은 경우이기 때문에 똑같이 Max는 Computer가 둘 수 있는 수 중 가장 가치가 높은 노드를 선택할 것입니다. 이렇게 다른 경우의 수, 다른 노드까지 탐색을 하면 Computer가 선택할 수 있는 수 중 가장 가치 있는 노드가 나옵니다. 이것만으로 해서도 게임이 이루어질 수 있지만 깊이가 깊어질수록, 엄청난 노드의 수로 게임이 처질 수 있습니다. 따라서 Alpha-Beta 가지치기를 이용하여 Min-Max 알고리즘에서 탐색시간과 탐색 효율을 높여주는 알고리즘을 이용하였습니다. Alpha-Beta 가지치기란, 예를들면 Min에서는 가장 작은 가치를 선택하지만, Max에서는 가장 큰 가치를 선택하기 때문에 만약 Min의 가치가 300이면 다음 Max는 300보다 작은 200을 선택하지 않을 것이고, 또한 다른 자식노드의 자식노드가 200보다 작은 값이 나와도 Max로는 선택을 하지 않을것이 때문입니다. 따라서 효율이 떨어지는 가지는 Cut off되어 더 이상 탐색하지 않게 됩니다.

알고리즘 구현에 필요한 것들은 여러 가지가 있습니다. 알고리즘의 효율을 높여주는 Cut off함수(노드를 뻗어나가다가 가지 않아도 되는 경우에 가지를 쳐서 더 이상 뻗어 나가지 않도록 하는 함수)와 각 말들이 움직일 수 있는 경로를 만든 함수, 게임의 종료 여부를 결정하는 종단함수 등이 있습니다. 그러나 이 모든 것을 훌륭히 구현했다고 해도 지능 수준이 낮다면 게임이 이루어지지 않습니다. 따라서 이 문제를 해결하기 위해 정석 함수와 평가 함수에 대한 고찰이 이루어 졌습니다. 정석 함수란 정석적으로 기능을 부여하기 위한 함수이며 평가 함수에서는 우선적인 상대적 우열을 가린 후 동일한 가치를 가지는 국면들을 정석 함수를 이용하여 2차적 우열을 가리는 방식을 사용하여 지능적인 요소를 더욱 높였습니다.

우선, 알고리즘을 돌리기에 앞서 지금 대국이 Computer에게 유리한 대국인지를 평가 함수를 이용하여 판단합니다. 만약 User에게 먹힐 위험이 있는 말이 있는 경우의 가치를 더 크게 판단합니다. 그 다음 정석 함수를 이용하여 노드를 뻗어나가고, 그 가치를 밑에서부터 평가하면서 올라오게 됩니다. 또한 Computer의 말이 먹히더라도 만약 가치를 교환할만한 국면이면 그 노드에 가치를 더하는 함수도 추가하여 지능을 높였습니다.
다음은 예시입니다.

Computer의 각각 말이 갈 수 있는 좌표 값과 그 좌표 값에서 인공지능으로 갈 수 있는 모든 경우의 수를 우선 저장시킵니다. 그리고 Cut off 함수와 Alpha-Beta알고리즘을 적용시켜 가장 유리한 움직임을 저장시킵니다. 그리고 앞서 처음에 했던 평가 함수와 적용시킵니다.

다음은 평가 함수 내에서도 평가를 하는 경우입니다. 그림21의 초록색 화살표는 처음의 먹힐 가능성이 있는 Computer의 말이 먹을 수 있는, 또는 피할 수 있는 경우가 나타납니다. 파란색 화살표는 AI알고리즘을 통해 말이 이동한 경우 먹힐 가능성이 있는 것을 나타내었습니다.

말이 죽지 않는 경우를 더 큰 가치로 둔다면 (1,3)의 비숍이 (4,0)의 룩을 먹는 것이 가장 큰 가치이겠지만 만약 User의 말을 먹는 경우, User의 가치가 높은 말을 먹는 가치를 중점으로 둔다면 Computer의 비숍이 User의 나이트에게 먹힐 위험이 있더라도 User의 퀸을 먹을 것입니다. 저는 우선적으로 후자에 더 큰 비중을 두어 결과는 다음과 같습니다.

3.2. 전체 시스템 구성

3.3. 개발 환경(개발 언어, Tool, 사용 시스템 등)
저는 많은 개발툴 중에서 ti사의 tms320f2809pza를 제어하기 위해 source insight를 이용하였습니다. source insight는 언어로 개발 시 수천개에서 수만개의 소스코드를 포함하여 코드를 분석하고 디버깅 및 개발할때 이만한 툴이 없기 때문에 source insight를 사용하였습니다.
또한 teraterm이라는 프로그램을 이용하여 pc와 ti 사의 tms320f2809보드 간에 sci 통신을 하여 ti사의 보드에 접근할 수 있었습니다.
이로 인해 Printf를 이용하여 에러처리나 알고리즘 확인 및 디버깅을 할수 있었습니다.

4. 단계별 제작 과정
전자전기공학부 학부생으로써 자료구조 공부나 AI 공부를 하는 동안 하드웨어를 먼저 완성하였습니다.

5. 기타(회로도, 소스코드, 참고문헌 등)
5.1.1. 소스코드
Ⅰ. 센서
(1) reed switch로 말의 위치 알아낸 후 정보 저장
센서의 위치를 알아내는 소스

(2) 모터
motor의 속도, 가속도를 제어하기 위한 함수

(3) Algorithm

Min-Max 알고리즘을 기반으로 한 Alpha-Beta Algorithm

Ⅱ. 회로도