Compiling program

Hello!


Here is my program, does not compile:

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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

#include <iostream>
#include <bitset>
#include <cstdlib>

using std::cin;
using std::cout;
using std::ostream;
using std::endl;
using std::bitset;

const size_t N = 3;
typedef bitset <N*N> board;


const board wins[] = {
    board(0b111000000), board(0b000111000), board(0b000000111),	// rows
    board(0b100100100), board(0b010010010), board(0b001001001),	// cols
    board(0b100010001), board(0b001010100)	// diagonals
};

board noughts;			// bit board for first player
board crosses;			// bit board for second player


const char NOUGHT = 'O';
const char CROSS = 'X';

void al_move();
board combined();
ostream & print_board(ostream & stm = cout, board b = combined());

// This indicates the current player. Computer plays noughts.
bool curr_move_noughts = true;

board
combined()
{
    return noughts | crosses;
}				// combined bit board for both players

bool
valid(size_t row, size_t col)
{
    return row < N && col < N;
}

size_t
pos(size_t row, size_t col)
{
    return row * N + col;
}				// map row, col to bit position

bool
occupied(size_t row, size_t col)
{
    return valid(row, col) && combined()[pos(row, col)];
}

bool
free(size_t row, size_t col)
{
    return valid(row, col) && !occupied(row, col);
}

size_t last_move_row = -1, last_move_col = -1 ;

void make_move( size_t row, size_t col, board & b )
{
    if (free(row, col))
    {
	b[pos(row, col)] = true;
        last_move_row = row ;
        last_move_col = col ;
    } 
}

void unMake( board & b )
{
    if (valid(last_move_row, last_move_col))// if valid last_move_row, last_move_col
    {
    int row= -1;
    int col= -1;
    b[pos(row, col)] = true;
    last_move_row = -1 ;
    last_move_col = -1 ; 
    }
}

void
make_move(size_t row, size_t col)
{
    if (curr_move_noughts)
	make_move(row, col, noughts);
    else
	make_move(row, col, crosses);
}

bool
is_win(board b)
{
    for (int i = 0; i < sizeof(wins) / sizeof(wins[0]); ++i) {
	if ((wins[i] & b) == wins[i])
	    return true;
    }
    return false;
}

bool
is_win()
{
    return is_win(curr_move_noughts ? noughts : crosses);
}

// is the board full?
bool is_full(board b)
{
    static board fullboard(0b111111111);
    return b == fullboard;
}

bool is_full()
{
    return is_full(curr_move_noughts ? noughts : crosses);
}

int evaluate(board b)

{ 

 if (is_win (board b))             // cross

 {return -1;}

 else if (is_win)

 {return 1; }

 else if (is_full()) {return 0;}

}


void
play()
{

    int row = -1;		// For player input
    int col = -1;

    for (int turns = 0; turns < 9; ++turns) {
	curr_move_noughts = !curr_move_noughts;

	if (curr_move_noughts) {
	    al_move(); 		// computer plays noughts
	} else {
	    cout << "Choose a move..." << endl;
	    cout << "Enter row and col : ";
	    cin >> row >> col;
	    // dmh - note that valid rows/col are 0-2, not 1-3. If you
	    // want the user to enter 1-3 then decrement the value
	    // they enter right after they enter it
	    if (!valid(row,col)) {
		cout << "Illegal move!  Try again...\n" << endl;
	    } else {
		make_move(row, col);
	    }
	}
	print_board();
	if (is_win()) {
	    cout << "Player " << (curr_move_noughts ? NOUGHT : CROSS) << " has won!" << endl; exit(0);
	} else if (is_full()) {
	    cout << "Game ended in a tie!" << endl;
	}
    }
}



ostream & print_board(ostream & stm, board b)
{
    stm << "------\n";
    for (std::size_t i = 0; i < N; ++i) {
	for (std::size_t j = 0; j < N; ++j) {
	    const size_t
		k = pos(i, j);
	    if (b[k])
		stm << (noughts[k] ? NOUGHT : CROSS) << ' ';
	    else
		stm << ". ";
	}
	stm << '\n';
    }
    return stm << "------\n";
}


void
al_move()			
{
int Search(int depth)
{
  int best_Score = -2;
  int best_Square = -2;
  if(depth == 0) return Evaluate(); // at branch end, use evaluation heuristic on position
  for (int turns = 0; turns < 9; ++turns) {                 // loop over turns
    while (occupied(x,y));
    make_move(x, y);              
    score = -Search(depth-1);       // recursion (flip sign because we change POV)
    unMake()
    if(score > bestScore) {         // score accounting: remember best (from side-to-move POV)
      best_Score = score;
      best_Square = square;
    }
  }
  return  best_Square; 
  return  best_Score;

 }
 
}


int
main()
{
    play();
    return 0;
}



Hopefully you have some ideas, see you later :D
Like the compiler reports:

Line 131: You shouldn't give a type name (here board) as part of the actual parameter list of a function call.

Line 135: You missed the empty parameter list of is_win().

Line 140: You missed a return statement in case of no condition meets.

Line 202: You tried defining a function inside another function. C/C++ is no Pascal/Ada/...
So far, everything fixed, though there came up some other errors that I don`t understand

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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

#include <iostream>
#include <bitset>
#include <cstdlib>

using std::cin;
using std::cout;
using std::ostream;
using std::endl;
using std::bitset;

const size_t N = 3;
typedef bitset <N*N> board;


const board wins[] = {
    board(0b111000000), board(0b000111000), board(0b000000111),	// rows
    board(0b100100100), board(0b010010010), board(0b001001001),	// cols
    board(0b100010001), board(0b001010100)	// diagonals
};

board noughts;			// bit board for first player
board crosses;			// bit board for second player


const char NOUGHT = 'O';
const char CROSS = 'X';

void al_move();
board combined();
ostream & print_board(ostream & stm = cout, board b = combined());

// This indicates the current player. Computer plays noughts.
bool curr_move_noughts = true;

board
combined()
{
    return noughts | crosses;
}				// combined bit board for both players

bool
valid(size_t row, size_t col)
{
    return row < N && col < N;
}

size_t
pos(size_t row, size_t col)
{
    return row * N + col;
}				// map row, col to bit position

bool
occupied(size_t row, size_t col)
{
    return valid(row, col) && combined()[pos(row, col)];
}

bool
free(size_t row, size_t col)
{
    return valid(row, col) && !occupied(row, col);
}

size_t last_move_row = -1, last_move_col = -1 ;

void make_move( size_t row, size_t col, board & b )
{
    if (free(row, col))
    {
	b[pos(row, col)] = true;
        last_move_row = row ;
        last_move_col = col ;
    } 
}

void unMake( board & b )
{
    if (valid(last_move_row, last_move_col))// if valid last_move_row, last_move_col
    {
    int row= -1;
    int col= -1;
    b[pos(row, col)] = true;
    last_move_row = -1 ;
    last_move_col = -1 ; 
    }
}

void
make_move(size_t row, size_t col)
{
    if (curr_move_noughts)
	make_move(row, col, noughts);
    else
	make_move(row, col, crosses);
}

bool
is_win(board b)
{
    for (int i = 0; i < sizeof(wins) / sizeof(wins[0]); ++i) {
	if ((wins[i] & b) == wins[i])
	    return true;
    }
    return false;
}

bool
is_win()
{
    return is_win(curr_move_noughts ? noughts : crosses);
}

// is the board full?
bool is_full(board b)
{
    static board fullboard(0b111111111);
    return b == fullboard;
}

bool is_full()
{
    return is_full(curr_move_noughts ? noughts : crosses);
}

int Evaluate(board b)

{ 

 if (is_win (b))             

 {return -1;}

 else if (is_win ())

 {return 1; }

 else if (is_full()) {return 0;}
 
 else {}                                // ?

}


void
play()
{

    int row = -1;		// For player input
    int col = -1;

    for (int turns = 0; turns < 9; ++turns) {
	curr_move_noughts = !curr_move_noughts;

	if (curr_move_noughts) {
	    int Search(int depth); 		// computer plays noughts
	} else {
	    cout << "Choose a move..." << endl;
	    cout << "Enter row and col : ";
	    cin >> row >> col;
	    // dmh - note that valid rows/col are 0-2, not 1-3. If you
	    // want the user to enter 1-3 then decrement the value
	    // they enter right after they enter it
	    if (!valid(row,col)) {
		cout << "Illegal move!  Try again...\n" << endl;
	    } else {
		make_move(row, col);
	    }
	}
	print_board();
	if (is_win()) {
	    cout << "Player " << (curr_move_noughts ? NOUGHT : CROSS) << " has won!" << endl; exit(0);
	} else if (is_full()) {
	    cout << "Game ended in a tie!" << endl;
	}
    }
}



ostream & print_board(ostream & stm, board b)
{
    stm << "------\n";
    for (std::size_t i = 0; i < N; ++i) {
	for (std::size_t j = 0; j < N; ++j) {
	    const size_t
		k = pos(i, j);
	    if (b[k])
		stm << (noughts[k] ? NOUGHT : CROSS) << ' ';
	    else
		stm << ". ";
	}
	stm << '\n';
    }
    return stm << "------\n";
}


			

int Search(int depth)
{
  int bestScore;	
  int square;
  int score;
  int x,y;
  int best_Score = -2;
  int best_Square = -2;
  if(depth == 0) return Evaluate(); // at branch end, use evaluation heuristic on position
  for (int turns = 0; turns < 9; ++turns) {                 // loop over turns
    while (occupied(x,y));
    make_move(x, y);              
    score = -Search(depth-1);       // recursion (flip sign because we change POV)
    unMake();
    if(score > bestScore) {         // score accounting: remember best (from side-to-move POV)
      best_Score = score;
      best_Square = square;
    }
  }
  return  best_Square; 
  return  best_Score;

 }
 



int
main()
{
    play();
    return 0;
}



I`m not sure of line 210, what should I give to Evaluate() argument type?
Last edited on
That's your specification of Evaluate:

int Evaluate(board b)

So give it an board.
I still get the following error:

main.cpp:209:40: error: expected primary-expression before ')' token

if(depth == 0) return Evaluate(board ); // at branch end, use evaluation heuristic on position
Your function definitions says: My name is Evaluate and you may apply me to exactly one value of type board. Such a value may be taken from a constant, a variable of type board or it may be returned from a function call which returns any value of type board.

See f.e. your own code line 91, where you find a function definition namely
int Search(int depth)
which expect exactly one value of type int. In line 214 you're calling it as
score = -Search(depth-1);
where (depth - 1) is the only one actual parameter and which is of type int. Take this as an example.

PS: Line 157 has a similar error. May there are other lines like this. Have a look at cplusplus.com Tutorial for detailed information about how calling a function.
I think that the mistake is to leave board out of int Search parameter list.. Here is some changes that I did:

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

int Search(int depth, board b)
{
  int bestScore;	
  int square;
  int score;
  int x,y;
  int best_Score = -2;
  int best_Square = -2;
  if(depth == 0) return Evaluate(board); // at branch end, use evaluation heuristic on position
  for (int turns = 0; turns < 9; ++turns) {                 // loop over turns
    while (occupied(x,y));
    make_move(x, y);              
    score = -Search(depth-1, board);       // recursion (flip sign because we change POV)
    unMake();
    if(score > bestScore) {         // score accounting: remember best (from side-to-move POV)
      best_Score = score;
      best_Square = square;
    }
  }
  return  best_Square; 
  return  best_Score;

 }
Here is some changes that I did an now it compiles... almost.


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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

#include <iostream>
#include <bitset>
#include <cstdlib>

using std::cin;
using std::cout;
using std::ostream;
using std::endl;
using std::bitset;

const size_t N = 3;
typedef bitset <N*N> board;


const board wins[] = {
    board(0b111000000), board(0b000111000), board(0b000000111),    // rows
    board(0b100100100), board(0b010010010), board(0b001001001),	// cols
    board(0b100010001), board(0b001010100)	// diagonals
};

board noughts;			// bit board for first player
board crosses;			// bit board for second player


const char NOUGHT = 'O';
const char CROSS = 'X';

void al_move();
board combined();
ostream & print_board(ostream & stm = cout, board b = combined());

// This indicates the current player. Computer plays noughts.
bool curr_move_noughts = true;

board
combined()
{
    return noughts | crosses;
}				// combined bit board for both players

bool
valid(size_t row, size_t col)
{
    return row < N && col < N;
}

size_t
pos(size_t row, size_t col)
{
    return row * N + col;
}				// map row, col to bit position

bool
occupied(size_t row, size_t col)
{
    return valid(row, col) && combined()[pos(row, col)];
}

bool
free(size_t row, size_t col)
{
    return valid(row, col) && !occupied(row, col);
}

size_t last_move_row = -1, last_move_col = -1 ;

void make_move( size_t row, size_t col, board & b )
{
    if (free(row, col))
    {
	b[pos(row, col)] = true;
        last_move_row = row ;
        last_move_col = col ;
    } 
}

void unMake( board & b )
{
    if (valid(last_move_row, last_move_col))// if valid last_move_row, last_move_col
    {
    int row= -1;
    int col= -1;
    b[pos(row, col)] = true;
    last_move_row = -1 ;
    last_move_col = -1 ; 
    }
}

void
make_move(size_t row, size_t col)
{
    if (curr_move_noughts)
	make_move(row, col, noughts);
    else
	make_move(row, col, crosses);
}

bool
is_win(board b)
{
    for (int i = 0; i < sizeof(wins) / sizeof(wins[0]); ++i) {
	if ((wins[i] & b) == wins[i])
	    return true;
    }
    return false;
}

bool
is_win()
{
    return is_win(curr_move_noughts ? noughts : crosses);
}

// is the board full?
bool is_full(board b)
{
    static board fullboard(0b111111111);
    return b == fullboard;
}

bool is_full()
{
    return is_full(curr_move_noughts ? noughts : crosses);
}

int Evaluate()

{ 
    
 board b = b;

 if (is_win (b))             

 {return -1;}

 else if (is_win ())

 {return 1; }

 else if (is_full()) {return 0;}
 
 else {}                                // ?

}


void
play()
{

    int row = -1;		// For player input
    int col = -1;

    for (int turns = 0; turns < 9; ++turns) {
	curr_move_noughts = !curr_move_noughts;

	if (curr_move_noughts) {
	    int Search(int depth); 		// computer plays noughts
	} else {
	    cout << "Choose a move..." << endl;
	    cout << "Enter row and col : ";
	    cin >> row >> col;
	    // dmh - note that valid rows/col are 0-2, not 1-3. If you
	    // want the user to enter 1-3 then decrement the value
	    // they enter right after they enter it
	    if (!valid(row,col)) {
		cout << "Illegal move!  Try again...\n" << endl;
	    } else {
		make_move(row, col);
	    }
	}
	print_board();
	if (is_win()) {
	    cout << "Player " << (curr_move_noughts ? NOUGHT : CROSS) << " has won!" << endl; exit(0);
	} else if (is_full()) {
	    cout << "Game ended in a tie!" << endl;
	}
    }
}



ostream & print_board(ostream & stm, board b)
{
    stm << "------\n";
    for (std::size_t i = 0; i < N; ++i) {
	for (std::size_t j = 0; j < N; ++j) {
	    const size_t
		k = pos(i, j);
	    if (b[k])
		stm << (noughts[k] ? NOUGHT : CROSS) << ' ';
	    else
		stm << ". ";
	}
	stm << '\n';
    }
    return stm << "------\n";
}


			

int Search(int depth)
{
  int bestScore;	
  int square;
  int score;
  int x,y;
  int best_Score = -2;
  int best_Square = -2;
  if(depth == 0) return Evaluate(); // at branch end, use evaluation heuristic on position
  for (int turns = 0; turns < 9; ++turns) {                 // loop over turns
    while (occupied(x,y));
    make_move(x, y);              
    score = -Search(depth-1);       // recursion (flip sign because we change POV)
    unMake(board);
    if(score > bestScore) {         // score accounting: remember best (from side-to-move POV)
      best_Score = score;
      best_Square = square;
    }
  }
  return  best_Square; 
  return  best_Score;

 }
 



int
main()
{
    play();
    return 0;
}





I think that it is better to give the functions Evaluate() and Unmake() empty parameter list

because it is overly complicated calling them otherwise.

I don`t like Unmake(board) though.

What changes would I need to make to the function void unMake( board & b ) to give it

zero arguments?
If unMake() should be applied to exactly one board (even no temporary one), then you might declare this board as a global variable which may be accessed by unMake().

You really should pay attention even to your compilers warnings!
I changed it but look how this program compiles:

Choose a move...
Enter row and col : 0 2
------
. . X
. . .
. . .
------
------
. . X
. . .
. . .
------
Choose a move...
Enter row and col : 3 0
Illegal move! Try again...

------
. . X
. . .
. . .
------
------
. . X
. . .
. . .
------
Choose a move...
Enter row and col : 1 1
------
. . X
. X .
. . .
------
------
. . X
. X .
. . .
------
Choose a move...
Enter row and col :


That`s so strange! The computer doesn`t play at all.
Where did you declare variable depth and where do you modify its value other than in line 216? If nowhere else depth would never be decremented.
I know that the Negamax is not correct, but I don`t understand the depth issue anyway.



I would start with my evaluation function, because I don`t know if it is correct.


Here is some ideas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20


  int Evaluate()

{ 
    
  if (is_win (noughts))          

 {score--}

 else if (is_win (crosses))   

 {score++ }

 else  {score+=0;}

 
}                            

                            





And for the Negamax:

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

int Search(int depth)
{
  
  
  int score;
  int x,y;
  int bestScore = -2;
  bool bestMove = false;
  if(depth == 0) return Evaluate(); 
  for (int turns = 0; turns < 9; ++turns) {                 // loop over turns
    while (occupied(x,y));
    make_move(x, y);              
    score = -Search(depth-1);       // recursion 
    unMake();
    if(score > bestScore) {         
      bestScore = score;
      bestMove = (x,y);
    }
  }
  return  bestScore; 
  return  bestMove;

 }
 




But I really don`t know how to do this, because I have no experience.

Last edited on
Where did you declare variable depth and where do you modify its value other than in line 216? If nowhere else depth would never be decremented.
And as a consequence line 11ff of Search() would never be executed. (Line 22 will never be executed. Your compiler should have reported a warning).
That was actually not my question though. I think it is important what I should do and in what order.

I think I need to

1) write the heuristic function

2) then move to the search algorithm.

For part 1, I`m not sure what to do, maybe use a binary search tree.

Here is some pseudocode

1
2
3
4
5
6
7
8
9

function Find-recursive(key, node):  // call initially with node = root
    if node = Null or node.key = key then
        return node
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        return Find-recursive(key, node.right)


How to adapt that in practise, who knows.
My previous reply should explain:
That`s so strange! The computer doesn`t play at all.
I didn't analyze the semantics of your program. What kind of game do you implement? Would you please describe it a little bit?

Usually when implementing a 2 players game you'll apply the heuristic on leafs of a search tree. This tree starts at a given board as its root node. Next level contains all boards resulting from all possible moves of the next player (f.e. computer). Now you've to add as 2. level nodes to each 1. level node boards resulting from possible user moves. And so on.
Your tree may be complete f.e. at a given depth of 3. Now you may apply your heuristics on its leafs.
The game is Tictactoe. Player 0 is computer, and player X is the player. I first compiled it so that the computer makes random moves and it worked fine.

When making the search tree, I might as well use lists to implement it.

The idea of a list is this:

1
2
3
4
5
6
7
8
9
10
11

struct Link {

string value;
Link* prev;
Link* succ;
Link(const string& v, Link* p = nullptr, Link*s = nullptr)
      : value{v}, prev{p}, succ{s} {}

};


That is, given a link, we can go to its successor using the succ pointer and to its predecessor using the prev pointer. Null pointer indicates that a Link doesn`t have a successor or a predecessor


That way, the search tree could be made in computer`s memory.

I will have to put some time to it, to implement it for the tictactoe.
I think you'll need lists and a tree. Each tree node may consists of a list:

      +-+-+-+
      |x|o| |
      +-+-+-+
  0   | |x| |
      +-+-+-+
      | | |o|
      +-+-+-+
         |
         +------------------------------------------+---------+---------+---------+
         |                                          |         |         |         |
      +-+-+-+                                    +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+
      |x|o|x|                                    |x|o| |   |x|o| |   |x|o| |   |x|o| |
      +-+-+-+                                    +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+
  1   | |x| |                                    |x|x| |   | |x|x|   | |x| |   | |x| |
      +-+-+-+                                    +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+
      | | |o|                                    | | |o|   | | |o|   |x| |o|   | |x|o|
      +-+-+-+                                    +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+
         |                                          |         |         |         |
         +                                          +         +- ...    +-...     +-...
         |                                          |
      +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+      +-+-+-+   +-+-+-+
      |x|o|x|   |x|o|x|   |x|o|x|   |x|o|x|      |x|o|o|   |x|o| |
      +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+      +-+-+-+   +-+-+-+
  2   |o|x| | - | |x|o| - | |x| | - | |x| |      |x|x| | - |x|x|o| - ...
      +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+      +-+-+-+   +-+-+-+
      | | |o|   | | |o|   |o| |o|   | |o|o|      | | |o|   | | |o|
      +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+      +-+-+-+   +-+-+-+
         |         |         |         |            |         |
         +-...     +-...     +-...     +-...        +...      +...


The tree starts with a given board as its root node. Its immediately following children reflect all possible moves of a given player (here x at level 1). Level 2 in turn consists of lists of boards reflecting all possible moves of the other player (here o) as answer to player x moves. And so on.

EDIT: Fixed syntax error.
Last edited on
I think I need to build the negamax tree. It can have any number of children depending on the game situation.


First, I would start like this:

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

struct node
{

   Node * children;
   int childcount;
   double value;
};


Node * CreateTree( Board b, int depth)
{

Node * node = new Node();
node.childCount = board.GeAvailableMoveCount();
    node.value      = board.GetValue;
    if (depth > 0 && node.childCount > 0)
    {

      insert( Node*children)

{ 

....

}




I need to study data structures more, now this seems way beyond my current skill level.

Also, I haven`t had much time lately. No sources were published yet.
The above version is incomplete though. It`s not what it should be. I somehow need to loop over all possible moves and later decide which move is best.

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

Node * CreateTree(Board board, int depth)
{
    Node * node = new Node();
    node.childCount = board.GeAvailableMoveCount();
    node.value      = board.GetValue;
    if (depth > 0 && node.childCount > 0)
    {
        node.children = new Node * [node.childCount];
        for (int i = 0; i != node.childCount; ++i)
            node.children[i] = CreateTree(board.Move(i), depth - 1);
    }
    else
    {
        node.children = NULL;
    }
    return node;
}

void DeleteTree(Node * tree)
{
    for (int i = 0; i != tree.childCount; ++i)
        DeleteTree(tree.children[i]);
    delete [] tree.children; // deleting NULL is OK
    delete tree;
}



There is some thoughts how to make the above "pattern" visible. It needs some grinding though.
Last edited on
Topic archived. No new replies allowed.