0

Lets work out a game tree for Tic-Tac-Toe. How would one compute this result in Prolog:

Taking the 8 symmetries into account, and assuming computer (X) starts and plays deterministic, then only 49 table entries are needed!

  • 1 entry for empty board
  • 5 entries for 2 pieces
  • 21 entries for 4 pieces
  • 18 entries for 6 pieces
  • 4 entries for 8 pieces

https://stackoverflow.com/a/61298546/502187

  • 1
    Do you understand what is meant by "computer plays deterministic"? That it always takes the exact same move given the same move by the opponent? – TA_intern Jan 19 '21 at 07:37
  • 1
    It isn't clear to me, for example, what would be the first move of the computer. It must be obvious for the person who wrote the linked answer; to me it seems there are 3 possible moves, so which one is the "perfect" move? Reading the comments, it must be "corner", is that right? – TA_intern Jan 19 '21 at 07:43
  • Yes, since the computer (X player) always plays the same, no need to save those. – TA_intern Jan 19 '21 at 11:24

2 Answers2

1

Using an adaptation of the algorithm here, I get
a shorter solution with only 37 game positions:

?- init(X), best(X, x, L, W), 
   findall(Z, inside(L, Z), A), 
   sort(A, B), length(B, N).
B = [[[-, -, -], [-, x, -], [-, -, -]], [[x, -, o], 
[-, x, -], [-, -, -]], [[x, -, o], [-, x, x], [-, -, o]], 
[[x, o, -], [-, x, -], [-, -, -]], [[x, o, -], [-, x, -], 
[-, o, x]], [[x, o, -], [-, x, -], [x, -, o]], [[x, o, -], 
[-, x, o], [-, -, x]], [[x, o, -], [-, x, x], [o, -, -]], 
[[x, o, -], [o, x, -], [-, -, x]], [[x, o, o], [-, x, -], 
[-, -, x]], [[x, o, o], [-, x, -], [x, -, -]], [[x, o, o], 
[-, x, o], [x, -, x]], [[x, o, o], [-, x, x], [-, -, -]], 
[[x, o, o], [-, x, x], [o, x, -]], [[x, o, o], [-, x, x], 
[x, o, -]], [[x, o, x], [-, x, -], [o, x, o]], [[x, o, x], 
[-, x, -], [x, o, o]], [[x, o, x], [o, x, -], [o, -, x]], 
[[x, o, x], [o, x, -], [x, -, o]], [[x, x, -], [-, x, o], 
[o, o, x]], [[x, x, -], [-, x, o], [o, x, o]], [[x, x, -], 
[o, x, -], [o, x, o]], [[x, x, -], [o, x, o], [o, -, x]], 
[[x, x, o], [-, x, -], [o, -, -]], [[x, x, o], [-, x, -], 
[o, o, x]], [[x, x, o], [-, x, -], [o, x, o]], [[x, x, o], 
[-, x, o], [-, o, x]], [[x, x, o], [-, x, o], [o, x, -]], 
[[x, x, o], [o, x, -], [-, x, o]], [[x, x, o], [o, x, -], 
[o, x, -]], [[x, x, o], [o, x, o], [-, x, -]], [[x, x, o], 
[o, x, o], [x, o, x]], [[x, x, o], [o, x, x], [o, x, o]], 
[[x, x, o], [o, x, x], [x, o, o]], [[x, x, o], [x, x, o], 
[o, o, x]], [[x, x, x], [o, x, -], [o, -, o]], 
[[x, x, x], [o, x, o], [o, x, o]]],
N = 37

But since best/4 uses random_member/2 to make the choice
deterministic, by rerunning, one gets also longer results.

Prolog code for the tic-tac-toe game
score via findall, return random winning strategy
reduce number of moves through symmetry
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac4-pl

0

It's a vague question with an incorrect premise:

assuming computer (X) starts and plays deterministic

OK

5 entries for 2 pieces

If the X starts in the center (deterministic), then there are only two distinct 2-piece positions:

_ _ _
O X _    
_ _ _

O _ _
_ X _    
_ _ _

HTH

MWB
  • 11,740
  • 6
  • 46
  • 91