C++

Forum

 
Need an ideea for Chess

skater (15)
Hi everyone, i am looking for a way to generate the moves for each depth without them interfering with eachother, More explicitly i'm looking for a way to do GenerateMoves() from this algorithm http://ai-depot.com/articles/minimax-explained/2/

My first ideea was to create a list with all the moves but then i'll have to have a seperate list for each node,

my code so far: (can't paste it all so i'll just put the relevant functions for my problem)

the board is a 12x12 matrix with the first 2 and last 2 rows and columns marked as "bounds" to generate moves faster.

the function that checks if the move is legal
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
 
int ver_muta(int tur, int t[12][12], int x, int y, int x2, int y2) {

   if(tur==1)
      switch(t[x][y]) {
         case PION:
            if(x2==x+p[3] && y2==y+q[3] && t[x2][y2]<=-PION)
               return t[x2][y2];
            if(x2==x+p[4] && y2==y+q[4] && t[x2][y2]<=-PION)
               return t[x2][y2];
            if(t[x+p[8]][y+q[8]]!=0)
               break;
            if(x2==x+p[8] && y2==y+q[8])
               return 1;
            if(x==3) {
               if(t[x+p[8]][y+q[8]]!=0)
                     break;
               if(t[x+2*p[8]][y+2*q[8]]!=0)
                     break;
               if(x2==x+2*p[8] && y2==y+2*q[8])
                  return 1;
            }
               break;
         case NEBUN:
            for(int i=1;i<=4;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]<=-PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case TURA:
            for(int i=5;i<=8;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]<=-PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case REGINA:
            for(int i=1;i<=8;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]<=-PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case REGE:
            for(int i=1;i<=8;i++) {
               if(t[x2][y2]!=0) {
                  if(x2==x+p[i] && y2==y+q[i] && t[x2][y2]<=-PION)
                     return t[x2][y2];
                  else
                     continue;
               }
               else if(x2==x+p[i] && y2==y+q[i])
                  return 1;
            }
               break;
         case CAL:
            for(int i=9;i<=16;i++) {
               if(t[x2][y2]!=0) {
                  if(x2==x+p[i] && y2==y+q[i] && t[x2][y2]<=-PION)
                     return t[x2][y2];
                  else
                     continue;
               }
               else if(x2==x+p[i] && y2==y+q[i])
                  return 1;
            }
               break;
      }
   if(tur==-1)
      switch(t[x][y]) {
         case -PION:
            if(x2==x+p[1] && y2==y+q[1] && t[x2][y2]>=PION)
               return t[x2][y2];
            if(x2==x+p[2] && y2==y+q[2] && t[x2][y2]>=PION)
               return t[x2][y2];
            if(t[x+p[6]][y+q[6]]!=0)
               break;
            if(x2==x+p[6] && y2==y+q[6])
               return 1;
            if(x==8) {
               if(t[x+2*p[6]][y+2*q[6]]!=0)
                     break;
               if(x2==x+2*p[6] && y2==y+2*q[6])
                  return 1;
            }
               break;
         case -NEBUN:
            for(int i=1;i<=4;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]>=PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case -TURA:
            for(int i=5;i<=8;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]>=PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case -REGINA:
            for(int i=1;i<=8;i++)
               for(int j=1;j<=8;j++) {
                  if(t[x+j*p[i]][y+j*q[i]]!=0) {
                     if(x2==x+j*p[i] && y2==y+j*q[i] && t[x2][y2]>=PION)
                        return t[x2][y2];
                     else
                        break;
                  }
                  if(x2==x+j*p[i] && y2==y+j*q[i])
                     return 1;
               }
               break;
         case -REGE:
            for(int i=1;i<=8;i++) {
               if(t[x2][y2]!=0) {
                  if(x2==x+p[i] && y2==y+q[i] && t[x2][y2]>=PION)
                     return t[x2][y2];
                  else
                     continue;
               }
               else if(x2==x+p[i] && y2==y+q[i])
                  return 1;
            }
               break;
         case -CAL:
            for(int i=9;i<=16;i++) {
               if(t[x2][y2]!=0) {
                  if(x2==x+p[i] && y2==y+q[i] && t[x2][y2]>=PION)
                     return t[x2][y2];
                  else
                     continue;
               }
               else if(x2==x+p[i] && y2==y+q[i])
                  return 1;
            }
               break;
      }
   return 0;
}


would really appreciate a fast answer since i need to finish this till 25th :( any ideea is welcome ! thanks for taking the time to read this and maybe help me solve it :)
Galik (2254)
skater wrote:
My first ideea was to create a list with all the moves but then i'll have to have a seperate list for each node,


I would have thought for a chess game that each node would be a list forming a kind of permutation tree. But I am not familiar with any chess-solving algorithms.
skater (15)
I would have thought for a chess game that each node would be a list forming a kind of permutation tree. But I am not familiar with any chess-solving algorithms.



thats how i thaught about it aswell but as you can see from the algorithm.. the search goes depth first , and if i make it a list and check each node it will go width first.
Galik (2254)

Making a list will not result in checking width before depth. The algorithm is recursive. So while checking the top level 'width wise' it must plunge one step deeper FIRST before moving on to the next in its list.

And then while checking that 'one step deeper' game it does the same thing. It creates a list but before it traverses the list width-wise it has to plunge one more step deeper FIRST before moving on to the next in its list.

And so on until the deepest level has been reached before returning up to the previous deepest level to check its next node in the list width wise.

So it really does work depth first.
Last edited on
skater (15)
What i need is for the algorithm to go depth first all the way to the end state(checkmate) or till it reaches the max depth .. but i am guessing this is also doable ... i have been looking into the depth first algorithm looks suitable to tweaking it and turning it into min_max :D cheers for the help .. i'll post back if i manage to finish the algorithm , thanks for the help Galik :)
jsmith (5804)
I don't quite understand... for min-max, don't you want a breadth-first algorithm so
you can prune?
skater (15)
if i understand the algorithm correctly no, it must go depth first to actually have an evaluated end node in order to compare alfa and beta for pruning :)

(correct me if i'm wrong)
jsmith (5804)
I thought a typical chess implementation would generate every possible move to a depth
of, say, 3, then prune, then continue on with just the remaining nodes.
skater (15)
how i see things ...


in order to get a min evaluation or a max evaluation you need to go depth first to evaluate that particular branch and give it a value (else it will be + / - infinity till one of the nodes are evaluated)

http://www.cs.cornell.edu/Courses/cs312/2002sp/lectures/rec21.htm (check the alfa-beta pruning tree to see how it gets the values for alfa and beta :) )

Last edited on
skater (15)
UPDATE:


i've implemented a depth-first like algorithm .. that takes into account if the depth number is odd or even, so that it can decide if its a min or a max node ...
once it reaches the max depth it evaluates the board and gives the node a value but i'm short on ideeas on how to send the value trough the tree ( it must take into account if the node is min or max too each time it goes a depth back because min will choose the lowest value possible out of his childs and max the highest out of them .. ).

My question is: can i make some kind of pointer that points to all the child nodes of a particular node (the branching factor is around 40 ) ? if so can someone give me an example please

any other idea on how to approach this is welcome! cheers all.

PS : this is my node structure 
1
2
3
4
5
6
7
8
9
 
 struct lista
{
	int mat[12][12]; // game board
	int pozitie; // the nodes number
	int tata; // the father's number
	int adancime; // the depth of the node
        int evaluare; // the heuristic function
	struct lista *next; // pointer to the next node
}


PSS: i got a 2nd ideea, this would make me start from scratch but with a way better strategy.

if i create a pointer inside a recursive function such as 

1
2
3
4
5
6
 
int function() {
   struct name *aux;
   //make this point to a move list 
   and for each move in the list 
       return function()
}


will the pointer point to a different memory zone in all the recursions or to a different one each time ?
Last edited on
Topic archived. No new replies allowed.