← Back to branch summary

~kubuntu-members/bovo/4.11

« back to all changes in this revision

Viewing changes to ai/aron/aiboard.cc

  • Committer: Parker Coates
  • Date: 2009-03-23 20:28:30 UTC
  • Revision ID: git-v1:93422748408ab8bba79291ee65ad0a4b5e64118a
Added a new stronger and more human-like AI. The new AI is the default, 
but the old AI is still present and accessable through a KConfig entry.

Patch provided by Pelladi Gabor.
CC: pelladigabor@gmail.com

svn path=/trunk/KDE/kdegames/bovo/; revision=943426

Show diffs side-by-side

added added

removed removed

Lines of Context:
ai/aron/aiboard.cc
 
1
/*******************************************************************
 
2
*
 
3
* This file is part of the KDE project "Bovo"
 
4
*
 
5
* Bovo is free software; you can redistribute it and/or modify
 
6
* it under the terms of the GNU General Public License as published by
 
7
* the Free Software Foundation; either version 2, or (at your option)
 
8
* any later version.
 
9
*
 
10
* Bovo is distributed in the hope that it will be useful,
 
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
* GNU General Public License for more details.
 
14
*
 
15
* You should have received a copy of the GNU General Public License
 
16
* along with Bovo; see the file COPYING.  If not, write to
 
17
* the Free Software Foundation, 51 Franklin Street, Fifth Floor,
 
18
* Boston, MA 02110-1301, USA.
 
19
*
 
20
********************************************************************/
 
21
 
 
22
/**
 
23
 * @file AiBoard implementation
 
24
 */
 
25
 
 
26
#include "aiboard.h"
 
27
 
 
28
#include <time.h>
 
29
 
 
30
#include <vector>
 
31
#include <iostream>
 
32
#include <stdlib.h>
 
33
#include <algorithm>
 
34
 
 
35
#include "aisquare.h"
 
36
#include "coord.h"
 
37
#include "dimension.h"
 
38
#include "move.h"
 
39
 
 
40
using namespace bovo;
 
41
using namespace std;
 
42
 
 
43
namespace ai {
 
44
 
 
45
AiBoard::AiBoard(const usi width, const usi height,
 
46
                 KGameDifficulty::standardLevel skill, Player player)
 
47
  : m_cleanBoard(true), m_player(player), m_skill(skill) {
 
48
    m_dimension = new Dimension(width, height);
 
49
    setup();
 
50
}
 
51
 
 
52
AiBoard::AiBoard(const Dimension& dimension,
 
53
                 KGameDifficulty::standardLevel skill, Player player) 
 
54
  : m_cleanBoard(true), m_player(player), m_skill(skill) {
 
55
    m_dimension = new Dimension(dimension.width(), dimension.height());
 
56
    setup();
 
57
}
 
58
 
 
59
AiBoard::~AiBoard() {
 
60
    for (int x = 0; x < m_dimension->width(); ++x) {
 
61
        delete[] m_board[x];
 
62
    }
 
63
    delete[] m_board;
 
64
    delete m_dimension;
 
65
}
 
66
 
 
67
bool AiBoard::empty(const Coord& c) const throw(outOfBounds) {
 
68
    if (!m_dimension->ok(c)) {
 
69
        throw outOfBounds();
 
70
    }
 
71
    return m_board[c.x()][c.y()].empty();
 
72
}
 
73
 
 
74
bool AiBoard::empty(const usi x, const usi y) const throw(outOfBounds) {
 
75
    return empty(Coord(x, y));
 
76
}
 
77
 
 
78
usi AiBoard::height() const {
 
79
    return m_dimension->height();
 
80
}
 
81
 
 
82
Coord AiBoard::move() {
 
83
    if (m_cleanBoard) {
 
84
        srand(static_cast<int>(time(0)));
 
85
        usi randX = rand()%(m_dimension->width()/3) + m_dimension->width()/3;
 
86
        usi randY = rand()%(m_dimension->height()/3) + m_dimension->height()/3;
 
87
        return Coord(randX, randY);
 
88
    }
 
89
    for (usi x = 0; x < m_dimension->width(); ++x) {
 
90
        for (usi y = 0; y < m_dimension->height(); ++y) {
 
91
            if (m_board[x][y].status()) {
 
92
                Coord c(x, y);
 
93
                setPoints(c, value(c, m_player));
 
94
                addPoints(c, value(c, m_player == X ? O : X));
 
95
            }
 
96
        }
 
97
    }
 
98
    Coord out = evaluate();
 
99
    return out;
 
100
}
 
101
 
 
102
Coord* AiBoard::moves() {
 
103
#ifdef __GNUC__
 
104
#warning Implement - Coord* AiBoard::moves(const Coord& c)
 
105
#endif
 
106
    return new Coord();
 
107
}
 
108
 
 
109
Player AiBoard::player(const Coord& c) const throw(outOfBounds) {
 
110
    if (!m_dimension->ok(c)) {
 
111
        throw outOfBounds();
 
112
    }
 
113
    return m_board[c.x()][c.y()].player();
 
114
}
 
115
 
 
116
Player AiBoard::player(const usi x, const usi y) const throw(outOfBounds) {
 
117
    return player(Coord(x, y));
 
118
}
 
119
 
 
120
bool AiBoard::setPlayer(const Move& move)
 
121
  throw(busy, gameover, notValidPlayer) {
 
122
    m_cleanBoard = false;
 
123
    zero(move.coord());
 
124
    m_board[move.coord().x()][move.coord().y()].setPlayer(move.player());
 
125
    if (win(move.coord())) {
 
126
        m_gameover = true;
 
127
        return true;
 
128
    }
 
129
    return false;
 
130
}
 
131
 
 
132
void AiBoard::setSkill(KGameDifficulty::standardLevel skill) {
 
133
    m_skill = skill;
 
134
}
 
135
 
 
136
usi AiBoard::width() const {
 
137
    return m_dimension->width();
 
138
}
 
139
 
 
140
/* secret helper functions */
 
141
 
 
142
Coord next(const Coord& c, usi dir) {
 
143
    usi LEFT = 1;
 
144
    usi UP = 2;
 
145
    usi RIGHT = 4;
 
146
    usi DOWN = 8;
 
147
    Coord tmp = c;
 
148
    if (dir & LEFT) {
 
149
        tmp = tmp.left();
 
150
    } else if (dir & RIGHT) {
 
151
        tmp = tmp.right();
 
152
    }
 
153
    if (dir & UP) {
 
154
        tmp = tmp.up();
 
155
    } else if (dir & DOWN) {
 
156
        tmp = tmp.down(); 
 
157
    }
 
158
    return tmp;
 
159
}
 
160
 
 
161
bool cmp(const pair<uli, Coord> a, const pair<uli, Coord> b) {
 
162
    return a.first > b.first;
 
163
}
 
164
 
 
165
/* Private methods */
 
166
 
 
167
Coord AiBoard::evaluate() const {
 
168
    std::vector<std::pair<uli, Coord> > v, v2, v3;
 
169
    for (int x = 0; x < m_dimension->width(); ++x) {
 
170
        for (int y = 0; y < m_dimension->height(); ++y) {
 
171
            v.push_back(make_pair(points(Coord(x, y)), Coord(x, y)));
 
172
        }
 
173
    }
 
174
    sort(v.begin(), v.end(), cmp);
 
175
    uli max = v.begin()->first;
 
176
    for (vector<pair<uli, Coord> >::const_iterator it = v.begin(); 
 
177
      it != v.end(); ++it) {
 
178
        bool doBreak = false;
 
179
        switch (m_skill) {
 
180
            case KGameDifficulty::Impossible: // @TODO: Implement Impossible
 
181
            case KGameDifficulty::VeryHard: //@TODO: Implement Very Hard
 
182
            case KGameDifficulty::Hard:
 
183
                if (it->first == max) {
 
184
                    v2.push_back(*it);
 
185
                } else {
 
186
                    doBreak = true;
 
187
                }
 
188
                break;
 
189
            case KGameDifficulty::Medium:
 
190
                if (it->first * 1.2 >= max) {
 
191
                    v2.push_back(*it);
 
192
                } else {
 
193
                    random_shuffle(v2.begin(), v2.end());
 
194
                    return v2.begin()->second;
 
195
                }
 
196
                break;
 
197
            case KGameDifficulty::Easy:
 
198
                if (it->first * 2 >= max) {
 
199
                    v2.push_back(*it);
 
200
                } else {
 
201
                    random_shuffle(v2.begin(), v2.end());
 
202
                    return v2.begin()->second;
 
203
                }
 
204
                break;
 
205
            case KGameDifficulty::VeryEasy:
 
206
                if (it->first * 4 >= max) {
 
207
                    v2.push_back(*it);
 
208
                } else {
 
209
                    random_shuffle(v2.begin(), v2.end());
 
210
                    return v2.begin()->second;
 
211
                }
 
212
                break;
 
213
            case KGameDifficulty::RidiculouslyEasy:
 
214
            default: // in case the gui sets the level to an illegal value
 
215
                if (it->first * 7 >= max) {
 
216
                    v2.push_back(*it);
 
217
                } else {
 
218
                    random_shuffle(v2.begin(), v2.end());
 
219
                    return v2.begin()->second;
 
220
                }
 
221
                break;
 
222
        }
 
223
        if (doBreak) { 
 
224
            break;
 
225
        }
 
226
    }
 
227
    if (v2.size() == 0) {
 
228
        throw gameover();
 
229
    } else if (v2.size() == 1) {
 
230
        return v2.begin()->second;
 
231
    }
 
232
    for (vector<pair<uli, Coord> >::const_iterator it = v2.begin(); 
 
233
      it != v2.end(); ++it) {
 
234
        v3.push_back(make_pair(value2(it->second), it->second));
 
235
    }
 
236
    sort(v3.begin(), v3.end(), cmp);
 
237
    if (v3.size() > 1) {
 
238
        random_shuffle(v3.begin(), v3.end());
 
239
    }
 
240
    return v3.begin()->second;
 
241
}
 
242
 
 
243
uli AiBoard::points(const Coord& c) const throw(outOfBounds) {
 
244
    if (!m_dimension->ok(c)) {
 
245
        throw outOfBounds();
 
246
    }
 
247
    return m_board[c.x()][c.y()].points();
 
248
}
 
249
    
 
250
void AiBoard::addPoints(const Coord& c, uli points) throw(outOfBounds) {
 
251
    if (!m_dimension->ok(c)) {
 
252
        throw outOfBounds();
 
253
    }
 
254
    m_board[c.x()][c.y()].setPoints(m_board[c.x()][c.y()].points() + points);
 
255
}
 
256
 
 
257
void AiBoard::setPoints(const Coord& c, uli points) throw(outOfBounds) {
 
258
    if (!m_dimension->ok(c)) {
 
259
        throw outOfBounds();
 
260
    }
 
261
    m_board[c.x()][c.y()].setPoints(points);
 
262
    m_board[c.x()][c.y()].setStatus(false);
 
263
}
 
264
    
 
265
void AiBoard::setup() {
 
266
    m_gameover = false;
 
267
    m_board = new AiSquare*[m_dimension->width()];
 
268
    for (int x = 0; x < m_dimension->width(); ++x) {
 
269
        m_board[x] = new AiSquare[m_dimension->height()];
 
270
    }
 
271
}
 
272
 
 
273
uli AiBoard::value(const Coord& c, const usi pl) const {
 
274
    if (!empty(c)) {
 
275
        return 0;
 
276
    }
 
277
    usi oppositePlayer = (pl==1?2:1);
 
278
    usi tp;
 
279
    usi empty;
 
280
    usi await;
 
281
    usi leftsideEmpty;
 
282
    uli tmpPoint = 1;
 
283
    uli point = 0;
 
284
    bool enemy = false;
 
285
    for (int dir = 0; dir < 4; ++dir) {
 
286
        for (int i = 1; i <= 5; ++i) {
 
287
            tp = 0;
 
288
            enemy = false;
 
289
            empty = 0;
 
290
            await = 0;
 
291
            leftsideEmpty = 0;
 
292
            for (int diff = 5-i; diff > 0-i; --diff) {
 
293
                Coord tmp = c;
 
294
                switch (dir) {
 
295
                    case 0:
 
296
                        tmp = Coord(c.x()-diff, c.y());
 
297
                        break;
 
298
                    case 1:
 
299
                        tmp = Coord(c.x(),      c.y()-diff);
 
300
                        break;
 
301
                    case 2:
 
302
                        tmp = Coord(c.x()-diff, c.y()-diff);
 
303
                        break;
 
304
                    case 3:
 
305
                        tmp = Coord(c.x()+diff, c.y()-diff);
 
306
                        break;
 
307
                }
 
308
                if (m_dimension->ok(tmp)) {
 
309
                    if (player(tmp) == pl) {
 
310
                        empty += await;
 
311
                        await = 0;
 
312
                        ++tp;
 
313
                    } else if (player(tmp) == oppositePlayer) {
 
314
                        enemy = true;
 
315
                        tp = 0;
 
316
                    } else {
 
317
                        if (tp > 0) {
 
318
                            ++await;
 
319
                        } else {
 
320
                            ++leftsideEmpty;
 
321
                        }
 
322
                    }
 
323
                } else {
 
324
                    enemy = true;
 
325
                    tp = 0;
 
326
                }
 
327
                if (enemy) {
 
328
                    break;
 
329
                }
 
330
            }
 
331
            tmpPoint = 1;
 
332
            switch (tp) {
 
333
                case 4:
 
334
                    tmpPoint *= (m_skill == KGameDifficulty::RidiculouslyEasy ? 7 : 231);
 
335
                case 3:
 
336
                    tmpPoint *= (m_skill == KGameDifficulty::VeryEasy ? 21 : 
 
337
                        (m_skill == KGameDifficulty::RidiculouslyEasy ? 12 : 231));
 
338
                case 2:
 
339
                    tmpPoint *= (m_skill == KGameDifficulty::VeryEasy ? 21 : 231 );
 
340
                    break;
 
341
                case 1:
 
342
                    tmpPoint *= m_skill == KGameDifficulty::RidiculouslyEasy ? 3 : 1;
 
343
                    break;
 
344
                case 0:
 
345
                    tmpPoint = 0;
 
346
            }
 
347
            if (pl == m_player && m_skill != KGameDifficulty::RidiculouslyEasy 
 
348
                               && m_skill != KGameDifficulty::VeryEasy) {
 
349
                tmpPoint *= 21;
 
350
            }
 
351
            if (empty < 2 && await > 0 && leftsideEmpty > 0) {
 
352
                tmpPoint *= 8;
 
353
            }
 
354
            point += tmpPoint;
 
355
        }
 
356
    }
 
357
    return point;
 
358
}
 
359
 
 
360
uli AiBoard::value2(const Coord& c) const {
 
361
    uli p = 0;
 
362
    usi lp = 0;
 
363
    usi q = 1;
 
364
    Coord tmp(c.x(), c.y());
 
365
    bool test = true;
 
366
    for (usi u = 1; u < 3; ++u) {
 
367
        for (usi i = 0; i < 4; ++i) {
 
368
            while (test) {
 
369
                switch (i) {
 
370
                    case 0:
 
371
                        tmp = Coord(c.x()-q, c.y());
 
372
                        break;
 
373
                    case 1:
 
374
                        tmp = Coord(c.x(),   c.y()-q);
 
375
                        break;
 
376
                    case 2:
 
377
                        tmp = Coord(c.x()-q, c.y()-q);
 
378
                        break;
 
379
                    case 3:
 
380
                        tmp = Coord(c.x()+q, c.y()-q);
 
381
                        break;
 
382
                }
 
383
                test = m_dimension->ok(tmp);
 
384
                if (test) {
 
385
                    test = player(tmp) == u;
 
386
                }
 
387
                if (test) {
 
388
                    ++lp;
 
389
                }
 
390
                ++q;
 
391
            }
 
392
            test = true;
 
393
            q = 1;
 
394
            while (test) {
 
395
                switch (i) {
 
396
                    case 0:
 
397
                        tmp = Coord(c.x()+q, c.y());
 
398
                        break;
 
399
                    case 1:
 
400
                        tmp = Coord(c.x(),   c.y()+q);
 
401
                        break;
 
402
                    case 2:
 
403
                        tmp = Coord(c.x()+q, c.y()+q);
 
404
                        break;
 
405
                    case 3:
 
406
                        tmp = Coord(c.x()-q, c.y()+q);
 
407
                        break;
 
408
                }
 
409
                test = m_dimension->ok(tmp);
 
410
                if (test) {
 
411
                    test = player(tmp) == u;
 
412
                }
 
413
                if (test) {
 
414
                    ++lp;
 
415
                }
 
416
                ++q;
 
417
            }
 
418
            switch (lp) {
 
419
                case 0:
 
420
                case 1:
 
421
                    p += lp;
 
422
                    break;
 
423
                case 2:
 
424
                    p += (9*lp);
 
425
                    break;
 
426
                case 3:
 
427
                    p += (8*9*lp+1);
 
428
                    break;
 
429
                default:
 
430
                    p += 1000;
 
431
                    break;
 
432
            }
 
433
            test = true;
 
434
            q = 1;
 
435
        }
 
436
    }
 
437
    return p;
 
438
}
 
439
 
 
440
bool AiBoard::win(const Coord& c) const {
 
441
    usi LEFT = 1;
 
442
    usi UP = 2;
 
443
    usi RIGHT = 4;
 
444
    usi DOWN = 8;
 
445
    usi DIR[8] = {
 
446
          LEFT,
 
447
          RIGHT,
 
448
          UP,
 
449
          DOWN,
 
450
          LEFT | UP,
 
451
          RIGHT | DOWN,
 
452
          LEFT|DOWN,
 
453
          RIGHT|UP
 
454
    };
 
455
    usi p = player(c);
 
456
    for (int i = 0; i < 4; ++i) {
 
457
        usi count = 1;
 
458
        Coord tmp = next(c, DIR[2*i]);
 
459
        while (m_dimension->ok(tmp) && player(tmp) == p) {
 
460
            ++count;
 
461
            tmp = next(tmp, DIR[2*i]);
 
462
        }
 
463
        tmp = next(c, DIR[2*i+1]);
 
464
        while (m_dimension->ok(tmp) && player(tmp) == p) {
 
465
            ++count;
 
466
            tmp = next(tmp, DIR[2*i+1]);
 
467
        }
 
468
        if (count >= 5) {
 
469
            return true;
 
470
        }
 
471
    }
 
472
    return false;
 
473
}
 
474
 
 
475
void AiBoard::zero(const Coord& c) {
 
476
    usi minX = c.x()-5 < 0 ? 0 : c.x()-5;
 
477
    usi maxX = c.x()+5 > m_dimension->width()-1 ? m_dimension->width()-1 : c.x()+5;
 
478
    usi minY = c.y()-5 < 0 ? 0 : c.y()-5;
 
479
    usi maxY = c.y()+5 > m_dimension->height()-1 ? m_dimension->height()-1 : c.y()+5;
 
480
    for (int x = minX; x <= maxX; ++x) {
 
481
        for (int y = minY; y <= maxY; ++y) {
 
482
            m_board[x][y].setStatus(true);
 
483
        }
 
484
    }
 
485
}
 
486
    
 
487
} /* namespace ai */