2023년 인공지능 구현과제

gainterritory

목표 : 면적이 아닌 3각형 갯수를 최대한 많이 만드는 게임 제약사항 : 1분 이내에 결과를 도출하도록 할 것, 민맥스 트리를 이용해서 구현할 것

필요라이브러리

pip install tk pip install shapely

초반 전략 - 민맥스트리를 사용하지 않음

1. 초반에는 랜덤을 선을 잇지만 두가지 조건을 만족해야한다.
   1. 선분은 어느 선과도 연결되지 않는다. 다만 기울기가 같을 경우 허용
   2. 상대방이 다른 선과 연결된 선을 만들면 삼각형을 만들 수 있으므로 바로 삼각형을 만들것
2. 1.1 조건을 만족하는 선분이 없을 시 민맥스 체제로 변경하거나 다른 룰을 적용
3. 민맥스의 경우 멀티프로세싱을 사용할 예정이며 풀 방식을 활용할 예정

선공후공 판단방법

1. 7x7 공간에서 점이 최대 20개 까지 주어진다.
2. 점의 데이터를 입력해서 기계한테 받아오도록하는 알고리즘이 필요하다.
3. 학습방식으로 구현할 경우
   1. 점을 배열하는 모든 경우의 수를 배치하고 이를 랜덤으로 수행해서 승리한 경우가 선공인지 후공인지 기억한다.
   2. 이를 학습자료를 사용해서 점을 배치를 보고 판단하는 알고리즘을 사용
   3. 이부분은 파이토치로 적당한 모델 선택 -> XGBoost 로 선택

xgboost lightgbm 참고한 자료

1. https://mjrecord.tistory.com/18

민맥스 알고리즘

1. 병렬화를 진행하는만큼 가지치기를 수행을 하지 못함 -> 병렬화의 효율이 떨어짐을 의미
2. 멀티스레드로 할경우 같은 변수에 접근하기때문에 GIL로 성능하락
3. 멀티프로세스로 할경우 통신문제 발생

테스트 코드

1. 각 단계에서 반환한 자료형이 올바른지 확인해야한다.
2. 튜플과 리스트를 명확히 구분해야한다.
3. 각 노드들을 오름차순으로 정렬되어야한다.
4. x 보다는 y 좌표가 우선된다.
5. 반환하는 결과값이 올바른지 확인해야한다.
   1. 각 케이스별로 3가지를 만들고 이에 대해서 블랙박스 테스트를 진행한다.
   2. 가지치기가 제대로 일어나는지 확인이 필요하다.
   3. 트리의 min max 값을 일치여부를 확인해야한다.