*정* 스토어

*정*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

10개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

Gametree 3ply minimax 알고리즘을 적용한 hexapawn game, pruning 적용

..FILE:Assignment_2008720095_03.hwpHexapawn Game ProgramAssignment 03by Game Tree & pruningIntroductionOverall Description이번 과제는 게임트리를 이용하여 Hexapawn(3*3)을 구현하는 것으로, 게임은 Interactive Mode와 Batch Mode로 구성되어 있다.먼저 Interactive Mode는 사용자가 실시간 대화형으로 Computer와 1:1 게임을 벌이는 Mode이고, Batch Mode는 사용자가 File을 통하여 미리 pawn의 색상과, 좌표를 입력하고, 프로그램은 그 좌표를 통하여 게임을 진행하게 된다.Requirement1) 알고리즘과제에서 구현해야 할 알고리즘은 3-ply Game tree와 alpha-beta pruning이 사용해야 한다.2) 게임 형식3*3 의 Board와 같은 틀에서 게임이 진행되며, User는 White or Black을 선택하여 게임을 진행하며 White가 먼저 pawn을 이동하게 된다.명령어(File의 command)를 통하여 pawn을 이동하게 되고, 올바르지 않은 pawn을 선택하여 움직이려고 할 경우, 입력을 다시 해야 한다.3) 게임 규칙pawn의 이동 경로는 전진, 좌, 우만 존재하며, 상대방의 pawn을 죽이며 이동할 수 있는 경우는 좌 대각선상과 우 대각선상으로만 움직여 상대방의 pawn을 잡을 수 있다.또한 이동 경로에는 상대방의 말이 없어야 하며, 좌 대각선상과 우 대각선상으로 움직일 때는 상대방의 말이 없으면 움직일 수 없다.또한 자신의 말이 아닌 것은 움직 일 수 없으며, 범위 외의 좌표로도 움직일 수 없다.4) 승리 조건한쪽의 pawn이 상대방의 시작점 좌표까지 이동하였을 경우(자신의 말이 상대방의 끝까지 이동하였을 경우)자신의 말이 모두 움직일 수 없을 경우자신의 말이 Board 판에 존재 하지 않을 경우Sample input/outputBatch ModeBatch Mode의 간단한 실나, 사용자에 의해 직접 호출되며, Max와는 반대되는 개념으로 Max가 최선의 경우의 수를 생각한다면 Min의 경우 최악의 경우를 생각하게 된다. 즉 상대방이 제일 잘 할 경우를 가정하여 생각하게 된다.예를 들어 Computer가 White pawn이라고 가정할 경우, 프로그램은 Max->Min->Max함수를 재귀적으로 호출하게 되는데, 이 때 처음 Max에서는 White(Computer)의 최선의 경우, 다음 Min에서는 Black(User)의 최선의 경우, 즉 컴퓨터의 입장에서 보았을 때, 최악의 경우를 생각하고, 다음 Max 함수에서는 이러한 Min함수가 호출 된 후, 최악의 state에서 가장 최선이 될 수 있는 pawn의 움직임을 판단하여 evaluation의 값을 반환하게 된다.또 이때, pruning 알고리즘을 이용하여, 불필요한 경우의 수는 생각하지 않게 되므로 해당 프로그램의 연산 속도를 높일 수 있다.Terminal_test & Evaluation해당 state에서 게임이 종료될 수 있는 3가지 경우를 판단하여 이때의 evaluation을 반환하게 되는데, 게임이 종료된다면 100, -100을 반환하게 되고, 그렇지 않을 경우 해당 state의 evaluation을 반환하게 된다.Evaluation 함수는 현재 state를 이용하여 state_evaluation의 값을 반환하게 된다.Manager ClassInteractive_Mode / Batch_Mode 는 해당 Mode를 선택하여 게임을 진행하게 하는 함수이다.Move_Com_pawn해당 함수는 Computer가 pawn을 움직이게 하는 함수로, game tree의 Max함수 혹은 Min함수를 호출한다.Move_File_pawn해당 함수는 Batch_Mode일 때 파일을 읽어 들여 pawn을 움직이게 하는 함수이다.Move_User_pawn해당 함수는 유저의 입력에 따라 pawn을 움직이게 하는 함수이다.search_pawn & movable다음 함수들은 user의 pawn을 움직일 파보다 작거나 같을 경우 return B를 하며 가지치기를 하게 된다.이는 Beta와 Alpha값을 비교하였을 때, 더 이상 계산을 할 필요가 없기 때문에, 그 이후의 시나리오에 대해서는 생략하는 것을 뜻한다. 이는 최선의 상태만을 찾기 위한 Minimax 알고리즘의 특성에 해당하므로 해당 과제의 구현에서는 Minimax 알고리즘과 alpha beta pruning을 통하여 해당 게임을 구현하였다.4. Algorithm specificationFlow Chart구현한 프로그램의 flow chart로 게임이 시작되면 Mode를 선택하게 된다.Interactive Mode일 경우, User는 pawn의 색상을 선택하게 되고, Computer와 1:1 game을 진행하게 된다. 게임 진행에 관해서는 function description에서 설명하였기 때문에, 자세한 내용은 생략한다.계속해서 사용자에게 움직이려는 pawn의 위치와 움직이게 될 위치를 입력받게 되고, 게임이 끝났는지를 pawn이 움직일 때마다 확인하고 만약 evaluation의 값에 따라 게임이 종료된다면, 게임 결과를 출력하고 프로그램을 종료시킨다.비슷하게 Batch Mode에서는 User에게 직접 color와 pawn을 입력 받는 것이 아니라, file에서 입력 받게 되며, 입력 받은 정보를 통해 pawn의 color와 위치 정보를 계속해서 전달 받으며 방법은 Interactive Mode와 비슷한 방식으로 게임을 진행하게 된다.PseudocodeMax_functiont_value = Terminal_teat(current_state);e_value = Evaluation(current_state);if(t_value 100 or 100)return t_value;if(current_node->level == 3)return e_value;for(i = 0; i= beta)return beta;}}}return alpha;}Max함수의 pseudo code로 먼저 Max함수의 도입부에서는, Termlpha){alpha = temp;if(pNew->get_level() == 1){pCur = pNew;}}}if(c_state[i+1][j] == '0' && i < 2) //front{GTN* pNew = new GTN(); //create new chile nodepNew->set_state(*c_state); //save current node statememcpy(next_state, pNew->get_state(), 3*3); //copy statenext_state[i][j] = '0'; //move pawnnext_state[i+1][j] = com_color;pNew->set_state(*next_state); //copy state by moved pawn statepNew->set_level(pc_Root->get_level() + 1); //level uppNew->set_op_Com(1);temp = Min_Value(pNew, alpha, beta); //call min functionif(temp > alpha){alpha = temp;if(pNew->get_level() == 1){pCur = pNew;}}}if(c_state[i][j-1] == '0' && j > 0) //left{GTN* pNew = new GTN(); //create new chile nodepNew->set_state(*c_state); //save current node statememcpy(next_state, pNew->get_state(), 3*3); //copy statenext_state[i][j] = '0'; //move pawnnext_state[i][j-1] = com_color;pNew->set_state(*next_state); //copy state by moved pawn statepNew->set_level(pc_Root->get_level() + 1); //level uppNew->set_op_Com(1);temp = Min_Valet_state(), 3*3); //copy statenext_state[i][j] = '0'; //move pawnnext_state[i-1][j-1] = com_color;pNew->set_state(*next_state); //copy state by moved pawn statepNew->set_level(pc_Root->get_level() + 1); //level uppNew->set_op_Com(0);temp = Max_Value(pNew, alpha, beta); //call min functionif(beta > temp){beta = temp;if(pNew->get_level() == 1){pCur = pNew;}}}if(c_state[i-1][j+1] == user_color && i > 0 && j set_state(*c_state); //save current node statememcpy(next_state, pNew->get_state(), 3*3); //copy statenext_state[i][j] = '0'; //move pawnnext_state[i-1][j+1] = com_color;pNew->set_state(*next_state); //copy state by moved pawn statepNew->set_level(pc_Root->get_level() + 1); //level uppNew->set_op_Com(0);temp = Max_Value(pNew, alpha, beta); //call min functionif(beta > temp){beta = temp;if(pNew->get_level() == 1){pCur = pNew;}}}if(c_state[i-1][j] == '0' && i > 0) //front{GTN* pNew = new GTN(); //create new chile nodepNew->set_state(*c_state); //save current node statememcpy(next_state, ; i

프로그램소스| 2012.11.11| 10페이지| 3,500원| 조회(299)

MAX, min, game tree, minimax, MinMax알고리즘, 게임트..

미리보기

닫기