experimental/hex/hex_12.cpp - Issue 10928195: First round of dead file removal

Side by Side Diff: experimental/hex/hex_12.cpp

Issue 10928195: First round of dead file removal (Closed) Base URL: https://github.com/samclegg/nativeclient-sdk.git@master

Patch Set: Created 8 years, 3 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch

OLD	NEW
	(Empty)
1 // Hex Maniac v1.2

2 // Copyright Cameron Browne

3 // 5/10/2000

4 //

5 // Point-pairing algorithm with blind row.

6 //

7 // Feel free to experiment with and develop this code, but please

8 // acknowledge its contribution to any derived work.

9 //

10 // Compiles with the Microsoft C/C++ compiler (12.00.8168) and linker

11 // (6.00.8168) but should be portable. Use the following options:

12 // cl -GX hex_12.cpp

13 //

14 // Guaranteed bug free. Any errors must have been introduced by

15 // subsequent developers :)

16

17 #include <iostream>

18

19 using std::cout;

20 using std::cin;

21 using std::endl;

22

23

24 //////////////////////////////////////////////////////////////////////////////

25

26 const int MIN_N = 3; // Smallest board size

27 const int MAX_N = 26; // Largest board size (limit of alphanumeric notatio n)

28

29 static enum State // board point or move state

30 {

31 EMPTY = 0, // empty board position

32 VERT = 1, // computer player (vertical = j)

33 HORZ = 2, // human player (horizontal = i)

34 NUM_STATES

35 };

36

37 static char* StateNames[NUM_STATES] =

38 {

39 "Empty",

40 "Vertical",

41 "Horizontal",

42 };

43

44 struct Coord

45 {

46 Coord(int i_=-1, int j_=-1) : i(i_), j(j_) {}

47

48 int i;

49 int j;

50 };

51

52 // Hexagonal neighbours of X:

53 // >-<

54 // >-< 0 >-< \| 5 \| 0

55 // < 5 >-< 1 > ---+---+---

56 // >-< X >-< == 4 \| X \| 1

57 // < 4 >-< 2 > ---+---+---

58 // >-< 3 >-< 3 \| 2 \|

59 // >-<

60 static const Coord nbor[6] =

61 {

62 Coord(1,-1), Coord(1,0), Coord(0,1),

63 Coord(-1,1), Coord(-1,0), Coord(0,-1)

64 };

65

66 // Blind row defense templates

67 //

68 // Key:

69 // h = existing HORZ piece

70 // v = existing VERT piece

71 // . = empty position

72 // x = existing piece (VERT or HORZ)

73 // - = don't care

74 // H = last HORZ move

75 // V = VERT's best reply

76 // r = reentrant block on furthest connected piece (or adjacent if none)

77 //

78 // Note: more general situations should go last.

79 //

80 const int NUM_DEFENSE_TEMPLATES = 25;

81 static const char* HEX_DefenseTemplate[NUM_DEFENSE_TEMPLATES][2] =

82 {

83 { "H V - -", "- - - -" }, // acute blind corner

84 { "- - . H", "- - V -" }, // obtuse blind corner

85 { "- V H v", "- - - -" },

86 { "- v H V", "- - - -" },

87 { "- V H .", "h . . h" },

88 { "- . H V", "h . . h" },

89 { "v h H -", "V . h -" },

90 { "- H h v", "h . V -" },

91 { "- V H -", "h . h -" },

92 { "- - H V", "- h . h" },

93 { "- V H -", "- v - -" },

94 { "- H V -", "- v - -" },

95 { "- V H -", "- - h -" },

96 { "- H V -", "h - - -" },

97 { ". H h -", "V - - -" },

98 { "- h H .", "- - V -" },

99 { "- V H -", "h . - -" },

100 { "- H V -", "- . h -" },

101 { "- h H h", "- v V v" },

102 { "- h H h", "v V v -" },

103 { "- h H v", "- v V -" },

104 { "- v H h", "- V v -" },

105 { "- H r -", "h - - -" },

106 { "- r H -", "- - h -" },

107 { "- . H .", "- V . -" }, // reentrant block below (general case)

108 };

109

110

111 ///////////////////////////////////////////////////////////////////////////////

112

113 class HEX_Game

114 {

115 public:

116 HEX_Game(int n_=11) : N(n_), SwapOption(true) {}

117 ~HEX_Game() {}

118

119 bool Play(void);

120 private:

121 bool DoMove(State who);

122 bool GetUserMove(Coord& move) const;

123 bool GameWon(State who);

124 bool GameWon(State who, Coord const& from);

125 void RandomEmptyPosition(Coord& posn) const;

126 void ShowBoard(void) const;

127 bool IsValid(Coord const& posn) const;

128

129 void BestOpening(Coord& move) const;

130 bool GoodSwap(Coord const& move) const;

131 bool BestComputerMove(Coord& move) const;

132 bool DefendBlindRow(Coord& move) const;

133 void SpareMove(Coord& move) const;

134

135 private:

136 State Board[MAX_N][MAX_N]; // the board

137 int N; // current board size NxN

138 int NumMoves; // number of moves played

139 Coord Last; // opponent's last move

140 bool SwapOption; // whether the swap option is enabled

141 bool HasSwapped; // whether a player has swapped already

142 State WhoStarted; // who played first

143 bool Visit[MAX_N][MAX_N]; // for rough working

144 };

145

146

147 ///////////////////////////////////////////////////////////////////////////////

148

149 // Alternates moves between players until the game is won

150 //

151 // Returns: whether user choose to continue playing

152 //

153 bool HEX_Game::Play(void)

154 {

155 memset(Board, 0, sizeof(Board));

156 NumMoves = 0;

157 HasSwapped = false;

158

159 // Determine who starts

160 cout << "\nDo you want to start? [y/n/q]: ";

161 char ch('n');

162 cin >> ch;

163

164 if (tolower(ch) == 'q')

165 exit(1);

166

167 WhoStarted = (tolower(ch) == 'y') ? HORZ : VERT;

168

169 if (WhoStarted == HORZ)

170 ShowBoard();

171

172 // Play a game

173 State who(WhoStarted);

174 while (!DoMove(who))

175 who = State((NumMoves + WhoStarted + 1) % 2 + 1);

176

177 cout << "\nGame won by " << StateNames[who] << "!" << endl;

178 cout << "\nPlay again on " << N << 'x' << N << "? [y/n]: ";

179 cin >> ch;

180

181 return (tolower(ch) == 'y');

182 }

183

184 // Determines and plays a move for the specfied player

185 //

186 // Returns: whether this move wins the game

187 //

188 bool HEX_Game::DoMove(State who)

189 {

190 Coord move;

191 bool did_swap = (who==HORZ) ? GetUserMove(move) : BestComputerMove(move) ;

192 if (did_swap)

193 {

194 // 'who' chose to swap

195 State opp = (who == VERT) ? HORZ : VERT;

196 Board[Last.j][Last.i] = EMPTY; // undo opening move

197 Board[Last.i][Last.j] = who; // redo its reflection

198 ShowBoard();

199 cout << endl << "Swap! " << StateNames[who][0] << " takes ";

200 cout << char('A' + Last.j) << 1 + Last.i << "." << endl;

201

202 WhoStarted = who;

203 HasSwapped = true;

204 }

205 else

206 {

207 // Make the move

208 Board[move.j][move.i] = who;

209 NumMoves++;

210 Last = move;

211

212 // Show the result

213 ShowBoard();

214 cout << endl << StateNames[who][0] << " plays at ";

215 cout << char('A' + move.i) << 1 + move.j << "." << endl;

216 }

217

218 return GameWon(who);

219 }

220

221 // Reads user's move from the keyboard (HORZ)

222 //

223 // Returns: whether user chose to swap

224 //

225 bool HEX_Game::GetUserMove(Coord& move) const

226 {

227 char str[4];

228 if (SwapOption && !HasSwapped && NumMoves==1)

229 {

230 char ch('y');

231 cout << endl << "Swap opening move? ";

232 if (GoodSwap(Last))

233 cout << "(I would) [y/n/q]: ";

234 else

235 cout << "(I wouldn't) [y/n/q]: ";

236 cin >> ch;

237

238 if (tolower(ch) == 'q')

239 exit(2);

240

241 if (tolower(ch) == 'y')

242 return true; // Swap

243 }

244

245 do {

246 cout << endl << "Enter move [eg f6/q]: ";

247 cin >> str;

248

249 if (str[0] == 'q')

250 exit(3);

251

252 move.i = tolower(str[0]) - 'a';

253 move.j = atoi(&str[1]) - 1;

254 } while (!IsValid(move) \|\| Board[move.j][move.i]);

255

256 return false;

257 }

258

259 // Returns: whether the game has been won by the specified player

260 //

261 bool HEX_Game::GameWon(State who)

262 {

263 memset(Visit, 0, sizeof(Visit));

264 if (who == VERT)

265 {

266 for (int i = 0; i < N; i++)

267 if (Board[0][i]==VERT && !Visit[0][i] && GameWon(VERT, C oord(i,0)))

268 return true;

269 }

270 else

271 {

272 for (int j = 0; j < N; j++)

273 if (Board[j][0]==HORZ && !Visit[j][0] && GameWon(HORZ, C oord(0,j)))

274 return true;

275 }

276 return false;

277 }

278

279 // Recursively examines neighbours of potential winning chains

280 //

281 // Returns: whether the game has been won by the specified player

282 //

283 bool HEX_Game::GameWon(State who, Coord const& from)

284 {

285 if (who==HORZ && from.i==N-1 \|\| who==VERT && from.j==N-1)

286 return true;

287

288 Visit[from.j][from.i] = true; // this coord has been visited

289

290 for (int n = 0; n < 6; n++)

291 {

292 // Check neighbours for continuation of chain

293 Coord to(from.i + nbor[n].i, from.j + nbor[n].j);

294 if

295 (

296 IsValid(to) && Board[to.j][to.i]==who

297 &&

298 !Visit[to.j][to.i] && GameWon(who, to)

299 )

300 return true;

301 }

302 return false;

303 }

304

305 // Draws board in ASCII text format

306 //

307 void HEX_Game::ShowBoard(void) const

308 {

309 // Show alphabetical (HORZ) labels

310 cout << endl << " ";

311 for (int i = 0; i < N; i++)

312 cout << char('A' + i) << ' ';

313 cout << endl;

314

315 for (int j = 0; j < N; j++)

316 {

317 // Show numeric (VERT) labels

318 for (int s = 0; s < j; s++)

319 cout << ' ';

320 if (j < 9)

321 cout << ' ';

322 cout << j + 1;

323

324 // Show state of each board position along this row

325 for (int i = 0; i < N; i++)

326 if (Board[j][i] == VERT)

327 cout << " V";

328 else if (Board[j][i] == HORZ)

329 cout << " H";

330 else

331 cout << " .";

332 cout << endl;

333 }

334 }

335

336 // Returns: whether posn is within the bounds of the board

337 //

338 bool

339 HEX_Game::IsValid(Coord const& posn) const

340 {

341 return (posn.i >= 0 && posn.i < N && posn.j >= 0 && posn.j < N);

342 }

343

344

345 ///////////////////////////////////////////////////////////////////////////////

346 // Strategic operations

347

348 // Determines computer's best opening move (VERT)

349 //

350 void HEX_Game::BestOpening(Coord& move) const

351 {

352 move = Coord(N - 1, 0); // obtuse corner in blind row

353 }

354

355 // Returns: whether this opening move is worth swapping

356 //

357 bool

358 HEX_Game::GoodSwap(Coord const& move) const

359 {

360 return (move.i == N - move.j - 1); // swap along short diag onal

361 }

362

363 // Determines best move for computer (VERT)

364 //

365 // Returns: true on swap, else false

366 //

367 bool

368 HEX_Game::BestComputerMove(Coord& move) const

369 {

370 if (NumMoves == 0)

371 {

372 BestOpening(move); // opening move

373 }

374 else if (NumMoves == 1 && SwapOption && !HasSwapped && GoodSwap(Last))

375 {

376 return true; // swap opponent 's opening move

377 }

378 else if (Last.j == 0)

379 {

380 DefendBlindRow(move); // defend the blind row

381 }

382 else

383 {

384 if (Last.i < N - Last.j) // determine dual point on left

385 move = Coord(N - Last.j, N - Last.i - 1);

386 else // deter mine dual point on right

387 move = Coord(N - Last.j - 1, N - Last.i);

388 }

389

390 if (!IsValid(move) \|\| Board[move.j][move.i])

391 SpareMove(move); // spare move - do some damage!

392

393 return false;

394 }

395

396 // Determines best move along the blind row (row 0)

397 //

398 // Returns:

399 // Whether appropriate defending move was found.

400 //

401 bool HEX_Game::DefendBlindRow(Coord& move) const

402 {

403 move = Coord(-1, -1); // should already be initialised but mak e sure

404

405 for (int d = 0; d < NUM_DEFENSE_TEMPLATES; d++)

406 {

407 // Find root position H on top row

408 for (int root = 0; root < 4; root++)

409 if (HEX_DefenseTemplate[d][0][root * 2] == 'H')

410 break;

411 if

412 (

413 root>=4 // no root found

414 \|\|

415 root==0 && !(Last.i==0 && Last.j==0) // acute corner no good

416 \|\|

417 root==3 && !(Last.i==N-1 && Last.j==0) // obtuse corner no good

418 )

419 continue;

420

421 // Check whether rest of template matches board position

422 bool valid = true;

423

424 int reentrant = 0;

425

426 for (int j = 0; j < 2 && valid; j++)

427 for (int c = 0; c < 4 && valid; c++)

428 {

429 int i = Last.i - root + c;

430 char ch = HEX_DefenseTemplate[d][j][c * 2];

431

432 if (ch == 'V' && !Board[j][i])

433 move = Coord(i, j);

434 else if (ch == 'V' && Board[j][i])

435 valid = false;

436 else if (ch == 'h' && Board[j][i] != HORZ)

437 valid = false;

438 else if (ch == 'v' && Board[j][i] != VERT)

439 valid = false;

440 else if (ch == 'x' && !Board[j][i])

441 valid = false;

442 else if (ch == '.' && Board[j][i])

443 valid = false;

444 else if (ch == 'r')

445 {

446 if (Board[j][i] == VERT)

447 valid = false;

448 else

449 {

450 move = Coord(Last);

451 reentrant = (i < root) ? -1 : 1; // is reentrant move

452 }

453 }

454 }

455

456 if (!valid)

457 continue; // invalid template

458

459 if (move.i == -1 \|\| move.j == -1)

460 continue; // no valid reply found

461

462 if (reentrant)

463 {

464 if (reentrant > 0)

465 {

466 // Find reentrant block above

467 while (move.i < N - 1)

468 {

469 if (!Board[0][move.i])

470 return true; // adjacent block above

471

472 if (!Board[1][move.i])

473 {

474 move = Coord(move.i, 1);

475 return true; // reentrant block above

476 }

477 move.i++;

478 }

479 }

480 else

481 {

482 // Find reentrant block below

483 while (move.i >= 0)

484 {

485 if (!Board[0][move.i])

486 return true; // adjacent block above

487

488 if (!Board[1][move.i - 1])

489 {

490 move = Coord(move.i - 1, 1);

491 return true; // reentrant block above

492 }

493 move.i--;

494 }

495 }

496 return false; // no reentrant block found

497 }

498 return true; // good move found!

499 }

500 return false;

501 }

502

503

504 // Determines best spare move. There will ALWAYS be a spare move somewhere.

505 //

506 void HEX_Game::SpareMove(Coord& move) const

507 {

508 // Look for urgent moves on the blind row

509 move.j = 0;

510 for (move.i = 0; move.i < N; move.i++)

511 if

512 (

513 !Board[0][move.i]

514 &&

515 (

516 move.i < N - 1 && Board[0][move.i + 1] == HORZ

517 &&

518 (

519 Board[1][move.i] == VERT

520 \|\|

521 move.i > 0 && !Board[1][move.i] && Board [1][move.i-1]==HORZ

522 )

523 \|\|

524 move.i > 0 && Board[0][move.i - 1] == HORZ

525 &&

526 (

527 Board[1][move.i - 1] == VERT

528 \|\|

529 !Board[1][move.i] && Board[1][move.i + 1 ] == HORZ

530 )

531 )

532 )

533 return;

534

535 // If top obtuse corner is empty, take it

536 if (!Board[0][N - 1])

537 {

538 move = Coord(N - 1, 0);

539 return;

540 }

541

542 // Block any reentrant point on row 1

543 move.j = 1;

544 for (move.i = 0; move.i < N - 1; move.i++) // skip move.i = = N - 1

545 if

546 (

547 !Board[1][move.i]

548 &&

549 (

550 Board[0][move.i] == HORZ && Board[0][move.i + 1] != HORZ

551 \|\|

552 Board[0][move.i + 1] == HORZ && Board[0][move.i] != HORZ

553 )

554 )

555 return;

556

557 // Block any point adjacent to White on row 0

558 move.j = 0;

559 for (move.i = 0; move.i < N; move.i++)

560 if

561 (

562 !Board[0][move.i]

563 &&

564 (

565 move.i > 0 && Board[0][move.i - 1] == HORZ

566 \|\|

567 move.i < N - 1 && Board[0][move.i + 1] == HORZ

568 )

569 )

570 return;

571

572 // Take any point an empty point away from Black on row 0

573 move.j = 0;

574 for (move.i = 0; move.i < N; move.i++)

575 if

576 (

577 !Board[0][move.i]

578 &&

579 (

580 move.i > 1 && !Board[0][move.i-1] && Board[0][mo ve.i-2]==VERT

581 \|\|

582 move.i < N-2 && !Board[0][move.i+1] && Board[0][ move.i+2]==VERT

583 )

584 )

585 return;

586

587 // Take any empty point from top obtuse corner down (must be at least on e)

588 for (move.j = 0; move.j < N; move.j++)

589 for (move.i = N-1; move.i >= 0; move.i--)

590 if (!Board[move.j][move.i])

591 return;

592

593 move = Coord(-1, -1); // bad result

594 }

595

596

597 ///////////////////////////////////////////////////////////////////////////////

598

599 void main(int argc, char* argv[])

600 {

601 cout << "Hex Maniac v1.2" << endl;

602 cout << "Cameron Browne 5/10/2000" << endl << endl;

603 cout << "You are horizontal (H), computer is vertical (V)" << endl;

604

605 int n = 11;

606 if (argc == 2)

607 {

608 n = atoi(argv[1]);

609 if (n < MIN_N)

610 n = MIN_N;

611 else if (n > MAX_N)

612 n = MAX_N;

613 }

614

615 HEX_Game game(n);

616 while (game.Play());

617 }

OLD	NEW

« no previous file with comments | « experimental/hex/hex.js ('k') | experimental/hex/hex_icon.png » ('j') | no next file with comments »