-
Notifications
You must be signed in to change notification settings - Fork 0
/
改良審局函數3
191 lines (176 loc) · 6.57 KB
/
改良審局函數3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../include/algorithm.h"
#include <climits>
#define DEPTH 3
using namespace std;
/******************************************************
* In your algorithm, you can just use the the funcitons
* listed by TA to get the board information.(functions
* 1. ~ 4. are listed in next block)
*
* The STL library functions is not allowed to use.
******************************************************/
/*************************************************************************
* 1. int board.get_orbs_num(int row_index, int col_index)
* 2. int board.get_capacity(int row_index, int col_index)
* 3. char board.get_cell_color(int row_index, int col_index)
* 4. void board.print_current_board(int row_index, int col_index, int round)
*
* 1. The function that return the number of orbs in cell(row, col)
* 2. The function that return the orb capacity of the cell(row, col)
* 3. The function that return the color for the cell(row, col)
* 4. The function that print out the current board statement
*************************************************************************/
//class virtual_cell{
//public:
// int orbs_num; // The number of the orbs on the cell
// int capacity; // The max number of the orbs of a cell
// char color; // The color of the cell, 'w'(No one has placed the orbs), 'r'(Red Player) and 'b'(Blue player)
// bool explode;
//};0
//class virtual_b{
//public:
// virtual_cell cells[5][6];
// virtual_b(Board src);
//};
//========================================
bool on_corner(int i,int j){
if(i==0 && j==0) return true;
if(i==0 && j==5) return true;
if(i==4 && j==0) return true;
if(i==4 && j==5) return true;
return false;
}
bool on_edge(int i,int j){
if(i==0 || i==4 ||j==0 || j==5) return true;
return false;
}
bool on_center(int i,int j){
return !on_edge(i,j);
}
int critical_neighbor(Board board,int i,int j){
int num=0;
if(i-1>=0 && j-1>=0) {
if(board.get_capacity(i-1,j-1)-board.get_orbs_num(i-1,j-1)==1) num++;
}
if(i>=0 && j-1>=0) {
if(board.get_capacity(i,j-1)-board.get_orbs_num(i,j-1)==1) num++;
}
if(i+1>=0 && j-1>=0) {
if(board.get_capacity(i+1,j-1)-board.get_orbs_num(i+1,j-1)==1) num++;
}
if(i-1>=0 && j>=0) {
if(board.get_capacity(i-1,j)-board.get_orbs_num(i-1,j)==1) num++;
}
if(i+1>=0 && j>=0) {
if(board.get_capacity(i+1,j)-board.get_orbs_num(i+1,j)==1) num++;
}
if(i-1>=0 && j+1>=0) {
if(board.get_capacity(i-1,j+1)-board.get_orbs_num(i-1,j+1)==1) num++;
}
if(i>=0 && j+1>=0) {
if(board.get_capacity(i,j+1)-board.get_orbs_num(i,j+1)==1) num++;
}
if(i+1>=0 && j+1>=0) {
if(board.get_capacity(i+1,j+1)-board.get_orbs_num(i+1,j+1)==1) num++;
}
return num;
}
int cell_val_compute(Board board ,int i,int j , int color){
int value = 8 - (board.get_capacity(i,j) - board.get_orbs_num(i,j));
if(value==7 && on_center(i,j)) value *= 2;
if(board.get_orbs_num(i,j)==0 && on_corner(i,j)) value = 10 ;
value+= 2*(critical_neighbor(board,i,j));
return value;
}
int tree_dev(int depth , Board b, int color , Player* player){
//cout<<"depth="<<depth<<endl;
int value;
if(depth%2) value = INT_MIN; // need to get MAX
else value = INT_MAX;
for(int i=0 ; i<5 ; i++){
for(int j=0 ; j<6 ; j++){
if(b.get_cell_color(i, j) == color || b.get_cell_color(i, j) == 'w') { // valid step
int tmp;
if(depth%2) tmp = cell_val_compute(b,i,j,color);
else tmp = -1*cell_val_compute(b,i,j,color);
Board new_b = b;
new_b.place_orb(i,j,player);
if(depth<=DEPTH) {
if(color=='r') {
Player* p_blue = new Player('b');
tmp += tree_dev(depth+1 ,new_b , 'b', p_blue);
delete p_blue;
}
else if(color=='b')
{
Player* p_red = new Player('r');
tmp += tree_dev(depth+1 ,new_b , 'r', p_red);
delete p_red;
}
}
//==============================
//cout<<"tmp="<<tmp<<" value="<<value<<endl;
if(depth%2) {
//cout<<"(tmp>value) is true? "<<(tmp>value)<<endl;
if(tmp>value) value = tmp ;
}
else{
//cout<<"(tmp<value) is true? "<<(tmp<value)<<endl;
if(tmp<value) value = tmp;
}
}
}
}
//cout<<value<<"\n\n\n";
return value;
}
void board_eval(Board board , int color , int value[][6] , Player* player){
for(int i=0 ; i<5 ; i++){
for(int j=0 ; j<6 ; j++){
if(board.get_cell_color(i, j) == color || board.get_cell_color(i, j) == 'w') {
value[i][j] = cell_val_compute(board , i , j, color);
if(color=='r') {
Player* next_player = new Player('b');
Board n_board = board;
n_board.place_orb(i,j,player);
int return_val = tree_dev( 2 ,n_board,'b',next_player);
value[i][j] += return_val;
//cout<<"return value = "<<return_val<<endl;
}
else {
Player* next_player = new Player('r');
Board n_board = board;
n_board.place_orb(i,j,player);
value[i][j] += tree_dev(2,n_board,'r',next_player);
}
}
else value[i][j]=-1;
//cout<<i<<","<<j<<" "<<value[i][j]<<"\n";
}
}
}
void algorithm_A(Board board, Player player, int index[]){
int row, col;
int color = player.get_color();
int value[5][6];
//==================================
Player *cur_player = new Player(color);
board_eval(board,color,value,cur_player);
delete cur_player;
int tmp=INT_MIN;
for(int i=0 ; i<5 ; i++){
for(int j=0 ; j<6 ; j++){
if(value[i][j]>tmp){
index[0]=i;
index[1]=j;
tmp = value[i][j];
}
//cout<<value[i][j]<<" ";
}
//cout<<endl;
}
//cout<<"I choose :"<<index[0]<<","<<index[1]<<"\n\n\n";
}