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