완전 정보 게임
게임의 정보가 참가자 모두에게 공개된 게임
ex) 바둑, 오목, 체스
누가 먼저 하는가에 따라서 승부는 이미 결정되어 있다
(양쪽 다 최선을 다할 때)
불완전 정보 게임에서는 최선을 다한다는 말을 할 수 없음
최선을 다한다 : 완전 정보 게임에서는 그게 뭔지 정확하게 정의가능
오늘은 완전정보 게임중에 NIM게임을 볼 거임
NIM 게임 : 한번 플레이 할 때마다 반드시 문제 사이즈가 줄어듬을 보장할 수 있음
바둑돌 가져가기1
바둑돌 k개가 있음, 두 사람이 번갈아가며 자신의 차례에 1개, 2개의 돌을 가져갈 수 있다. 자신의 차례에 동작을 할 수 없으면 그 사람이 진다.
이기는 방법이 있는 사람과 그 사람이 이기는 방법을 구하시오.
언제 이길 까? : 내가 처음한다고 치고, 몇 개를 받았을 때 이기는 상황인지 지는 상황인지 판단
그래서 내가 언제 이길까? : 내가 마지막 돌을 가져가면 이길거임
28개면 이길까 질까? -> 상대방이 아무리 똑똑해도 내가 이길 수 있는 방법이 있음(이게 최선을 다한다의 정의)
27개면... -> 내가 지는 상황(상대방이 똑똑할 때 이길 방법이 없다는 뜻)
여기서 진다는 거는 내가 뭘 해도 상대방이 이길 상황을 줄 수 있다는 것
내가 이긴다는 거는 내가 한가지만 해도 상대방이 무조건 지는 상황을 줄 수 있으면 됨
결론
3의 배수를 받으면 지는 상황임 -> 내가 뭘 해도 상대방이 이기는 걸 받음
3의 배수가 아닌게 이기는 거임
내가 3의 배수를 받으면 내가 뭘 해도 상대방이 3의배수가 아닌걸 주게 됨
반대로 아닌걸 받으면 상대방한테 항상 3의 배수를 줄 수 있다.
3의 배수를 받으면 -> 지는 것
전부 O면 X, X가 하나라도 있으면 O
바둑돌 가져가기2
바둑돌이 k개가 있는데 이번에는 번갈아가며 자신의 차례에 1개, 3개, 4개의 돌을 가져갈 수 있음
이런식으로 풀면 NIM게임을 풀 수 있다.(지금은 기본적인 버전)
돌 가져가기(SCPC본선 문제)
돌이 n개의 더미가 있다
(돌3개),(돌5개),(돌2개) .... 이런식으로
A가 먼저 하는데 이중에 한 덩어리를 가져감(돌 5개)
B가 A가 가져간 빈자리의 왼쪽 전체나 오른쪽 전체를 가져감
그리고 남은거 가지고 계속 반복
A가 제일 많이 받을 수 있는 돌은 몇개인가?
예제
3, 5, 1, 4, 7
만약 A가 5를 가져갔다고 치면 B는 오른쪽을 다 먹고 3을 주는게 최적일 거임
A가 3을 가져가면 3점이 최고
5를 가져가면 8점
1을 가져가면 B는 오른쪽을 날리고 A가 5점을 더 먹을 거임 -> 6점
4를 가져가면 10점 (B가 7가져가고 A가 5가져가고 B가 3가져가고 A가 1가져감)
이거 어떻게 풀까.....
O(n^2)정도에 풀어야함
O(n^3)은 우리가 아는 패턴
만약 4를 먼저 가져간다면 B는 오른쪽에서 A가 얻을 수 있는 점수, 왼쪽에서 A가 얻을 수 있는 점수 중에 큰 쪽을 버리고 작은 쪽을 줌
4를 가져갔을 때 A가 몇점을 먹게되는지 알려면
오른쪽과 왼쪽의 점수를 알아야함 -> 더 작은 것들의 점수를 알면 큰 것의 점수를 알 수 있음
계산해야하는 값 : n^2개(모든 길이가 다 저정도(n^2/2))
n개를 try를 해야하니깐
O(n^3)의 시간이 걸림
중요한 패턴이 있음
2 3 6 4
라는 걸로 A가 먹을 수 있는 제일 좋은 점수 있을 것이다.
그걸 x라고 하자
거기에 값이 하나 추가되었다.
2 3 6 4 4
여기서 먹을 수 있는 제일 좋은 점수를 y라고 하자
y가 더 작을 수 있나?
기분상 y가 더 작을 수는 없을 것 같음(옵션이 더 많아졌고, B가 가져가도 남는게 더 많을 수 있는 데....)
구체적으로 말하면 작을 수 없음
2 3 6 4에서 A가 6을 가져가는게 최선이라고 하자
4가 추가되었을 때
B가 왼쪽을 날렸는데(4추가 전) 지금도 왼쪽을 날리면 오른쪽에 늘어난 입력이 있음
B가 왼쪽을 날렸는데 이번엔 오른쪽을 날리면
A가 더 먹을 수 있게 됨
이렇게 대충 생각해보면 줄어들리가 없음
저 그림대로 해 놓은게 O(n^3)패턴인거임
저렇게 해서 O(n^2)까지 줄일 수 있다.
(어렵다.....)
코드도 굉장히 복잡하지만 O(n^2logn)으로 풀면 그나마 간결해진다고 한다. (교수님 피셜)
