Rev 1805 | Rev 3924 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1805 | yogev_ezra | 1 | // |
2 | // KReversi.java |
||
3 | // The Othello Game, based on the algorithm of Muffy Barkocy |
||
4 | // (muffy@fish.com). |
||
5 | // |
||
6 | // The strategy is very very simple. The best move for the computer |
||
7 | // is the move that flip more pieces (preferring boards line and |
||
8 | // corners) and give less pieces to move to the opponent. |
||
9 | // |
||
10 | // Author: Alex "Kazuma" Garbagnati (kazuma@energy.it) |
||
11 | // Date: 20 Jan 96 |
||
12 | // L.R.: 26 Jan 96 |
||
13 | // Note: |
||
14 | // |
||
15 | |||
16 | |||
17 | |||
18 | #include |
||
19 | #include |
||
20 | #include |
||
21 | #include |
||
22 | #include |
||
23 | #include |
||
24 | |||
25 | typedef unsigned int u32; |
||
26 | |||
27 | int YSHIFT= 33; |
||
28 | |||
29 | int ENGLISH = 0; // |
||
30 | int ITALIAN = 1; // Languages |
||
31 | int EXTERNAL = 2; // |
||
32 | |||
33 | #define BLACK 0x000000; // |
||
34 | #define BLACK_S 0x333333; // |
||
35 | #define WHITE 0xffffff; // Colors |
||
36 | #define WHITE_S 0xaaaaaa; // |
||
37 | |||
38 | |||
39 | int NOMOVE = 0; // |
||
40 | int REALMOVE = 1; // Type of move |
||
41 | int PSEUDOMOVE = 2; // |
||
42 | |||
43 | int Empty = 0; // |
||
44 | int User = 1; // Board's owners |
||
45 | int Computer = 2; // |
||
46 | |||
47 | #define true 1 |
||
48 | #define false 0 |
||
49 | |||
50 | int UserMove = true; |
||
51 | int GameOver = false; |
||
52 | int CopyWinOn = false; |
||
53 | int StillInitiated = false; // This solve a little |
||
54 | // problem on reinit. |
||
55 | |||
56 | int TheBoard[8][8]; // Board |
||
57 | int Score[8][8]; |
||
58 | int OpponentScore[8][8]; |
||
59 | |||
60 | |||
61 | |||
62 | // |
||
63 | // DrawBoard |
||
64 | // (paint the Othello Board, a 8X8 green square table) |
||
65 | // |
||
66 | // Input: graphic (Graphics) |
||
67 | // Output: none |
||
68 | // Notes: |
||
69 | // |
||
70 | void DrawBoard() { |
||
71 | int i; |
||
72 | for(i=0;i<=8;i++) |
||
73 | { |
||
74 | __asm__ __volatile__("int $0x40"::"a"(38),"b"(320),"c"(YSHIFT+(YSHIFT+(40*i))*65536+40*i),"d"(0x555555)); |
||
75 | __menuet__line((40*i),YSHIFT,(40*i),353,0x555555); // horizontal |
||
76 | |||
77 | } |
||
78 | |||
79 | } |
||
80 | // End of DrawBoard |
||
81 | |||
82 | |||
83 | // |
||
84 | // DrawPiece |
||
85 | // (paint a piece, black or white, I'm using an 8x8 array, so |
||
86 | // from the input values for rows and cols must be |
||
87 | // subtracted 1) |
||
88 | // |
||
89 | // Input: who (int), |
||
90 | // column (int), |
||
91 | // row (int) |
||
92 | // Output: none |
||
93 | // Notes: |
||
94 | // |
||
95 | void DrawPiece(int Who, int Col, int Row) { |
||
96 | int pCol = (40*(Col-1)+1); |
||
97 | int pRow = YSHIFT+(40*(Row-1)+1); |
||
98 | u32 pColor,pShadow; |
||
99 | |||
100 | if (Who == User) { |
||
101 | pColor = BLACK; |
||
102 | pShadow = BLACK_S; |
||
103 | } else { |
||
104 | pColor = WHITE; |
||
105 | pShadow = WHITE_S; |
||
106 | } |
||
107 | TheBoard[Col-1][Row-1] = Who; |
||
108 | |||
109 | __menuet__bar(pCol+9,pRow+9,19,19,pColor); |
||
110 | } |
||
111 | // End of DrawPiece |
||
112 | |||
113 | |||
114 | // |
||
115 | // MsgWhoMove |
||
116 | // (paint the message informing who's move) |
||
117 | // |
||
118 | // Input: is user ? (int) |
||
119 | // Output: none |
||
120 | // Notes: |
||
121 | // |
||
122 | void MsgWhoMove(int UM) { |
||
123 | } |
||
124 | // End of MsgWhoMove |
||
125 | |||
126 | |||
127 | // |
||
128 | // FlipRow |
||
129 | // (calculate number of pieces are flipped by a move |
||
130 | // and return it. Eventually do the complete or pseudo |
||
131 | // move) |
||
132 | // |
||
133 | // Input: who (int) |
||
134 | // which board (int[][]) |
||
135 | // position col, row (int) |
||
136 | // direction col, row (int) |
||
137 | // make move ? (int) |
||
138 | // |
||
139 | int FlipRow(int Who, int WhichBoard[8][8] , int C, int R, |
||
140 | int CInc, int RInc, int MakeMove) { |
||
141 | int NewCol; |
||
142 | int NewRow; |
||
143 | int Opponent = User + Computer - Who; |
||
144 | int CNT = 0; |
||
145 | |||
146 | NewCol = C - 1; |
||
147 | NewRow = R - 1; |
||
148 | while (true) { |
||
149 | if (((NewCol+CInc) < 0) || ((NewCol+CInc) > 7) || |
||
150 | ((NewRow+RInc) < 0) || ((NewRow+RInc) > 7)) { |
||
151 | return 0; |
||
152 | } |
||
153 | if (WhichBoard[NewCol+CInc][NewRow+RInc] == Opponent) { |
||
154 | CNT++; |
||
155 | NewCol += CInc; |
||
156 | NewRow += RInc; |
||
157 | } else if (WhichBoard[NewCol+CInc][NewRow+RInc] == Empty) { |
||
158 | return 0; |
||
159 | } else { |
||
160 | break; |
||
161 | } |
||
162 | } |
||
163 | if (MakeMove != NOMOVE) { |
||
164 | C--; |
||
165 | R--; |
||
166 | int v; |
||
167 | for(v=0; v<=CNT; v++) { |
||
168 | if (MakeMove == REALMOVE) { |
||
169 | DrawPiece(Who, C+1, R+1); |
||
170 | } else { |
||
171 | WhichBoard[C][R] = Who; |
||
172 | } |
||
173 | C += CInc; |
||
174 | R += RInc; |
||
175 | } |
||
176 | } |
||
177 | return CNT; |
||
178 | } |
||
179 | // End of FlipRow |
||
180 | |||
181 | |||
182 | // |
||
183 | // IsLegalMove |
||
184 | // (verify that the move is legal) |
||
185 | // |
||
186 | // Input: who (int) |
||
187 | // board (int[][]) |
||
188 | // position col, row (int) |
||
189 | // Output: is legal ? (int) |
||
190 | // Notes: |
||
191 | // |
||
192 | int IsLegalMove(int Who, int WhichBoard[8][8] , int C, int R) { |
||
193 | if (WhichBoard[C-1][R-1] != Empty) { |
||
194 | return false; |
||
195 | } |
||
196 | int CInc,RInc; |
||
197 | for (CInc=-1; CInc<2; CInc++) { |
||
198 | for (RInc=-1; RInc<2; RInc++) { |
||
199 | if (FlipRow(Who, WhichBoard, C, R, CInc, RInc, NOMOVE) > 0) { |
||
200 | return true; |
||
201 | } |
||
202 | } |
||
203 | } |
||
204 | return false; |
||
205 | } |
||
206 | // End of IsLegalMove |
||
207 | |||
208 | |||
209 | // |
||
210 | // MakeMove |
||
211 | // (make the move) |
||
212 | // |
||
213 | // Input: who (int) |
||
214 | // position col, row (int) |
||
215 | // Output: false=EndGame, true=next player (int) |
||
216 | // Notes: |
||
217 | // |
||
218 | int MakeMove(int Who, int C, int R) { |
||
219 | int CInc,RInc; |
||
220 | for (CInc=-1; CInc<2; CInc++) { |
||
221 | for (RInc=-1; RInc<2; RInc++) { |
||
222 | FlipRow(Who, TheBoard, C, R, CInc, RInc, REALMOVE); |
||
223 | } |
||
224 | } |
||
225 | if (IsBoardComplete() || |
||
226 | ((!ThereAreMoves(Computer, TheBoard)) && (!ThereAreMoves(User, TheBoard)))) { |
||
227 | return false; |
||
228 | } |
||
229 | int Opponent = (User + Computer) - Who; |
||
230 | if (ThereAreMoves(Opponent, TheBoard)) { |
||
231 | UserMove = !UserMove; |
||
232 | } |
||
233 | return true; |
||
234 | } |
||
235 | // End of MakeMove |
||
236 | |||
237 | |||
238 | // |
||
239 | // EndGame |
||
240 | // (shows the winning message) |
||
241 | // |
||
242 | // Input: none |
||
243 | // Output: none |
||
244 | // Notes: |
||
245 | // |
||
246 | void EndGame() { |
||
247 | int CompPieces = 0; |
||
248 | int UserPieces = 0; |
||
249 | char *WinMsg_W = "Computer Won"; |
||
250 | char *WinMsg_L = "User Won"; |
||
251 | char *WinMsg_T = "???"; |
||
252 | char *TheMsg; |
||
253 | |||
254 | int StrWidth; |
||
255 | |||
256 | int c,r; |
||
257 | for (c=0; c<8; c++) { |
||
258 | for (r=0; r<8; r++) { |
||
259 | if (TheBoard[c][r] == Computer) { |
||
260 | CompPieces++; |
||
261 | } else { |
||
262 | UserPieces++; |
||
263 | } |
||
264 | } |
||
265 | } |
||
266 | if (CompPieces > UserPieces) { |
||
267 | TheMsg = WinMsg_W; |
||
268 | } else if (UserPieces > CompPieces) { |
||
269 | TheMsg = WinMsg_L; |
||
270 | } else { |
||
271 | TheMsg = WinMsg_T; |
||
272 | } |
||
273 | |||
274 | __menuet__write_text(100,8,0xff0000,TheMsg,strlen(TheMsg)); |
||
275 | |||
276 | } |
||
277 | // End of EndGame |
||
278 | |||
279 | |||
280 | // |
||
281 | // IsBoardComplete |
||
282 | // (checks if the board is complete) |
||
283 | // |
||
284 | // Input: none |
||
285 | // Output: the board is complete ? (int) |
||
286 | // Notes: |
||
287 | // |
||
288 | int IsBoardComplete() { |
||
289 | int i,j; |
||
290 | for (i=0; i<8; i++) { |
||
291 | for (j=0; j<8; j++) { |
||
292 | if (TheBoard[i][j] == Empty) { |
||
293 | return false; |
||
294 | } |
||
295 | } |
||
296 | } |
||
297 | return true; |
||
298 | } |
||
299 | // End of IsBoardComplete |
||
300 | |||
301 | |||
302 | // |
||
303 | // ThereAreMoves |
||
304 | // (checks if there are more valid moves for the |
||
305 | // player) |
||
306 | // |
||
307 | // Input: player (int) |
||
308 | // board (int[][]) |
||
309 | // Output: there are moves ? (int) |
||
310 | // Notes: |
||
311 | // |
||
312 | int ThereAreMoves(int Who, int WhichBoard[8][8] ) { |
||
313 | int i,j; |
||
314 | for (i=1; i<=8; i++) { |
||
315 | for (j=1; j<=8; j++) { |
||
316 | if (IsLegalMove(Who, WhichBoard, i, j)) { |
||
317 | return true; |
||
318 | } |
||
319 | } |
||
320 | } |
||
321 | return false; |
||
322 | } |
||
323 | // End of ThereAreMoves |
||
324 | |||
325 | |||
326 | // |
||
327 | // CalcOpponentScore |
||
328 | // (calculate the totalScore of opponent after |
||
329 | // a move) |
||
330 | // |
||
331 | // Input: position x, y (int) |
||
332 | // Output: score (int) |
||
333 | // Notes: |
||
334 | // |
||
335 | int CalcOpponentScore(int CP, int RP) { |
||
336 | int OpScore = 0; |
||
337 | int tempBoard[8][8]; // = new int[8][8]; |
||
338 | int c,r; |
||
339 | for (c=0; c<8; c++) { |
||
340 | for (r=0; r<8; r++) { |
||
341 | tempBoard[c][r] = TheBoard[c][r]; |
||
342 | } |
||
343 | } |
||
344 | int CInc,RInc; |
||
345 | for (CInc=-1; CInc<2; CInc++) { |
||
346 | for (RInc=-1; RInc<2; RInc++) { |
||
347 | FlipRow(Computer, tempBoard, CP+1, RP+1, CInc, RInc, PSEUDOMOVE); |
||
348 | } |
||
349 | } |
||
350 | if (ThereAreMoves(User, tempBoard)) { |
||
351 | int C,R; |
||
352 | for (C=0; C<8; C++) { |
||
353 | for (R=0; R<8; R++) { |
||
354 | OpScore += RankMove(User, tempBoard, C, R); |
||
355 | } |
||
356 | } |
||
357 | } |
||
358 | return OpScore; |
||
359 | } |
||
360 | // End of CalcOpponentScore() |
||
361 | |||
362 | |||
363 | // |
||
364 | // RankMoves |
||
365 | // (rank all moves for the computer) |
||
366 | // |
||
367 | // Input: none |
||
368 | // Output: none |
||
369 | // Notes: |
||
370 | // |
||
371 | void RankMoves() { |
||
372 | int C,R; |
||
373 | for (C=0; C<8; C++) { |
||
374 | for (R=0; R<8; R++) { |
||
375 | Score[C][R] = RankMove(Computer, TheBoard, C, R); |
||
376 | if (Score[C][R] != 0) { |
||
377 | OpponentScore[C][R] = CalcOpponentScore(C, R); |
||
378 | } else { |
||
379 | OpponentScore[C][R] = 0; |
||
380 | } |
||
381 | } |
||
382 | } |
||
383 | } |
||
384 | // End of RankMoves |
||
385 | |||
386 | |||
387 | // |
||
388 | // RankMove |
||
389 | // (rank a move for a player on a board) |
||
390 | // |
||
391 | // Input: who moves (int) |
||
392 | // on which board (int[][]) |
||
393 | // position col, row (int) |
||
394 | // Output: flipped pieces (int) |
||
395 | // Notes: best are corner, then border lines, |
||
396 | // worst are line near to border lines |
||
397 | // |
||
398 | int RankMove(int Who, int WhichBoard[8][8], int Col, int Row) { |
||
399 | int CNT = 0; |
||
400 | int MV = 0; |
||
401 | |||
402 | if (WhichBoard[Col][Row] != Empty) { |
||
403 | return 0; |
||
404 | } |
||
405 | int CInc,RInc; |
||
406 | for (CInc=-1; CInc<2; CInc++) { |
||
407 | for (RInc=-1; RInc<2; RInc++) { |
||
408 | MV = FlipRow(Who, WhichBoard, Col+1, Row+1, CInc, RInc, NOMOVE); |
||
409 | CNT += MV; |
||
410 | } |
||
411 | } |
||
412 | if (CNT > 0) { |
||
413 | if (((Col == 0) || (Col == 7)) || |
||
414 | ((Row == 0) || (Row == 7))) { |
||
415 | CNT = 63; |
||
416 | } |
||
417 | if (((Col == 0) || (Col == 7)) && |
||
418 | ((Row == 0) || (Row == 7))) { |
||
419 | CNT = 64; |
||
420 | } |
||
421 | if ((((Col == 0) || (Col == 7)) && (Row == 1) || (Row == 6)) && |
||
422 | (((Col == 1) || (Col == 6)) && (Row == 0) || (Row == 7)) && |
||
423 | (((Col == 1) || (Col == 6)) && (Row == 1) || (Row == 6))) { |
||
424 | CNT = 1; |
||
425 | } |
||
426 | } |
||
427 | return CNT; |
||
428 | } |
||
429 | // End of RankMove |
||
430 | |||
431 | |||
432 | // |
||
433 | // BestMove |
||
434 | // (calculate and execute the best move) |
||
435 | // |
||
436 | // Input: none |
||
437 | // Output: value, col & row (int[3]) |
||
438 | // Notes: |
||
439 | // |
||
440 | void BestMove (int retval[3]) { |
||
441 | |||
442 | retval[0] = -998; // move value; |
||
443 | retval[1] = 0; // column |
||
444 | retval[2] = 0; // row |
||
445 | |||
446 | RankMoves(); |
||
447 | int C,R; |
||
448 | for (C=0; C<8; C++) { |
||
449 | for (R=0; R<8; R++) { |
||
450 | if ((Score[C][R] == 0) && (OpponentScore[C][R] == 0)) { |
||
451 | Score[C][R] = -999; |
||
452 | } else if (Score[C][R] != 64) { |
||
453 | Score[C][R] = Score[C][R] - OpponentScore[C][R]; |
||
454 | } |
||
455 | } |
||
456 | } |
||
457 | for (C=0; C<8; C++) { |
||
458 | for (R=0; R<8; R++) { |
||
459 | if (Score[C][R] > retval[0]) { |
||
460 | retval[1] = C; |
||
461 | retval[2] = R; |
||
462 | retval[0] = Score[C][R]; |
||
463 | } |
||
464 | } |
||
465 | } |
||
466 | retval[1]++; |
||
467 | retval[2]++; |
||
468 | // return retval; |
||
469 | } |
||
470 | // End of BestMove |
||
471 | |||
472 | |||
473 | |||
474 | |||
475 | // |
||
476 | // paint |
||
477 | // |
||
478 | void paint() { |
||
479 | // MsgWhoMove(UserMove); |
||
480 | if (!CopyWinOn) { |
||
481 | int i,j; |
||
482 | for (i=0; i<8; i++) { |
||
483 | for (j=0; j<8; j++) { |
||
484 | if (TheBoard[i][j] != Empty) { |
||
485 | DrawPiece(TheBoard[i][j], i+1, j+1); |
||
486 | } |
||
487 | } |
||
488 | } |
||
489 | // } else { |
||
490 | // ShowAbout(); |
||
491 | } |
||
492 | } |
||
493 | // End of paint |
||
494 | |||
495 | |||
496 | // |
||
497 | // init |
||
498 | // |
||
499 | void init() { |
||
500 | // This is the right size of the applet 321x387 |
||
501 | // resize(321,387); |
||
502 | // I set twice the language. That's because if anybody |
||
503 | // forget a string in an external language file, are |
||
504 | // used english strings. |
||
505 | if (!StillInitiated) { |
||
506 | StillInitiated = true; |
||
507 | } |
||
508 | int i,j; |
||
509 | for (i=0; i<8; i++) { |
||
510 | for (j=0; j<8; j++) { |
||
511 | TheBoard[i][j] = 0; |
||
512 | } |
||
513 | } |
||
514 | TheBoard[3][3] = User; |
||
515 | TheBoard[3][4] = Computer; |
||
516 | TheBoard[4][3] = Computer; |
||
517 | TheBoard[4][4] = User; |
||
518 | UserMove = true; |
||
519 | // MsgWhoMove(true); |
||
520 | // repaint(); |
||
521 | } |
||
522 | // End of init |
||
523 | |||
524 | |||
525 | |||
526 | |||
527 | |||
528 | void paint_win(void) |
||
529 | { |
||
530 | __menuet__window_redraw(1); |
||
531 | __menuet__define_window(100,100,330,400,0x33777777,0,"Reversi"); |
||
2064 | dunkaist | 532 | __menuet__make_button(4,4,40,20,3,0xe0e0e0); |
1805 | yogev_ezra | 533 | __menuet__write_text(8,8,0x333333,"New",3); |
534 | __menuet__window_redraw(2); |
||
535 | } |
||
536 | |||
2064 | dunkaist | 537 | void main(void) |
1805 | yogev_ezra | 538 | { |
539 | int i; |
||
540 | u32 mouse_coord; |
||
541 | u32 mouse_butn; |
||
542 | int X,Y; |
||
543 | |||
544 | int TheCol, TheRow; |
||
545 | int BMove[3]; |
||
546 | int BX, BY; |
||
547 | int retval = false; |
||
548 | |||
549 | |||
550 | __menuet__set_bitfield_for_wanted_events(EVENT_REDRAW + EVENT_KEY + EVENT_BUTTON + EVENT_MOUSE_CHANGE); |
||
551 | paint_win(); |
||
552 | DrawBoard(); |
||
553 | init(); |
||
554 | paint(); |
||
555 | |||
556 | for(;;) |
||
557 | { |
||
558 | i=__menuet__wait_for_event(); |
||
559 | switch(i) |
||
560 | { |
||
561 | case 1: |
||
562 | paint_win(); |
||
563 | DrawBoard(); |
||
564 | paint(); |
||
565 | continue; |
||
566 | case 2: |
||
567 | __menuet__getkey(); |
||
568 | continue; |
||
569 | case 3: |
||
570 | if(__menuet__get_button_id()==1) { |
||
571 | __menuet__sys_exit();} |
||
572 | else |
||
573 | paint_win(); |
||
574 | init(); |
||
575 | DrawBoard(); |
||
576 | paint(); |
||
577 | continue; |
||
578 | case 4: |
||
579 | continue; |
||
580 | case 5: |
||
581 | continue; |
||
582 | case 6: |
||
583 | __asm__ __volatile__("int $0x40":"=a"(mouse_butn):"0"(37),"b"(2)); |
||
584 | __asm__ __volatile__("int $0x40":"=a"(mouse_coord):"0"(37),"b"(1)); |
||
585 | X = mouse_coord >> 16; |
||
586 | Y = mouse_coord & 0xffff; |
||
587 | |||
588 | // Process a normal click in the board |
||
589 | BX = X; |
||
590 | BY = Y - YSHIFT; |
||
591 | |||
592 | |||
593 | if ((BY >= 0) && (BY <= 321) && |
||
594 | (mouse_butn !=0) && (UserMove)) { |
||
595 | TheCol = (int)((BX/40)+1); |
||
596 | TheRow = (int)((BY/40)+1); |
||
597 | |||
598 | if (IsLegalMove(User, TheBoard, TheCol, TheRow)) { |
||
599 | retval = MakeMove(User, TheCol, TheRow); |
||
600 | while (retval && (!UserMove)) { |
||
601 | //MsgWhoMove(UserMove); |
||
602 | BestMove(BMove); |
||
603 | |||
604 | retval = MakeMove(Computer, BMove[1], BMove[2]); |
||
605 | //MsgWhoMove(UserMove); |
||
606 | } |
||
607 | if (!retval) { |
||
608 | EndGame(); |
||
609 | } |
||
610 | } |
||
611 | paint(); |
||
612 | } |
||
613 | continue; |
||
614 | |||
615 | |||
616 | } |
||
617 | } |
||
618 | }=>8;>8;>8;>8;>8;>8;>8;>8;>2;>2;>8;>8;>8;>8;>2;>2;>8;>8;>=8;>=8;>8;>8;>8;>8;>2;>2;>2;>2;>=CNT;>>>=8;i++)> |
||
619 |