games - main.go

     1  package main
     2  
     3  import (
     4  	"encoding/base64"
     5  	"flag"
     6  	"fmt"
     7  	"slices"
     8  	"strings"
     9  )
    10  
    11  type XO uint8
    12  
    13  const (
    14  	None XO = iota
    15  	X
    16  	O
    17  )
    18  
    19  func (xo XO) Switch() XO {
    20  	if xo == None {
    21  		return None
    22  	}
    23  
    24  	return 3 - xo
    25  }
    26  
    27  func (xo XO) String() string {
    28  	switch xo {
    29  	case None:
    30  		return "None"
    31  	case X:
    32  		return "X"
    33  	case O:
    34  		return "O"
    35  	}
    36  
    37  	return "Invalid"
    38  }
    39  
    40  type Position uint8
    41  
    42  func (p Position) RotateClockwise() Position {
    43  	return 2 - p/3 + 3*(p%3)
    44  }
    45  
    46  func (p Position) Flop() Position {
    47  	return 3*(p/3) + 2 - (p % 3)
    48  }
    49  
    50  var (
    51  	Positions = [...]Position{0, 1, 2, 3, 4, 5, 6, 7, 8}
    52  	wins      = [...][3]Position{
    53  		{0, 1, 2},
    54  		{3, 4, 5},
    55  		{6, 7, 8},
    56  		{0, 3, 6},
    57  		{1, 4, 7},
    58  		{2, 5, 8},
    59  		{0, 4, 8},
    60  		{2, 4, 6},
    61  	}
    62  )
    63  
    64  type Board uint32
    65  
    66  const emptyBoard Board = 0
    67  
    68  func (b Board) Get(pos Position) XO {
    69  	return XO(b>>(pos<<1)) & 3
    70  }
    71  
    72  func (b Board) Set(pos Position, xo XO) Board {
    73  	return (b & ^(3 << (pos << 1))) | (Board(xo) << (pos << 1))
    74  }
    75  
    76  func (b Board) Switch() Board {
    77  	c := emptyBoard
    78  
    79  	for _, p := range Positions {
    80  		c = c.Set(p, b.Get(p).Switch())
    81  	}
    82  
    83  	return c
    84  }
    85  
    86  func (b Board) Transform(flop bool, rotate uint8) Board {
    87  	c := emptyBoard
    88  
    89  	for _, p := range Positions {
    90  		v := b.Get(p)
    91  
    92  		if flop {
    93  			p = p.Flop()
    94  		}
    95  
    96  		for r := uint8(0); r < rotate; r++ {
    97  			p = p.RotateClockwise()
    98  		}
    99  
   100  		c = c.Set(p, v)
   101  	}
   102  
   103  	return c
   104  }
   105  
   106  func (b Board) HasWin() bool {
   107  	return b.hasXsInARow(3)
   108  }
   109  
   110  func (b Board) hasXsInARow(num int) bool {
   111  Loop:
   112  	for _, w := range wins {
   113  		xs := 0
   114  
   115  		for _, wn := range w {
   116  			switch b.Get(wn) {
   117  			case X:
   118  				xs++
   119  			case O:
   120  				continue Loop
   121  			}
   122  		}
   123  
   124  		if xs == num {
   125  			return true
   126  		}
   127  	}
   128  
   129  	return false
   130  }
   131  
   132  func (b Board) HasPossibleWin() bool {
   133  	return b.hasXsInARow(2)
   134  }
   135  
   136  func (b Board) String() string {
   137  	var sb strings.Builder
   138  
   139  	sb.WriteString("┌───┬───┬───┐\n")
   140  	for y := Position(0); y < 3; y++ {
   141  		if y > 0 {
   142  			sb.WriteString("├───┼───┼───┤\n")
   143  		}
   144  
   145  		for x := Position(0); x < 3; x++ {
   146  			sb.WriteString("│ ")
   147  			if p := b.Get(y*3 + x); p == None {
   148  				sb.WriteString(" ")
   149  			} else {
   150  				sb.WriteString(p.String())
   151  			}
   152  			sb.WriteString(" ")
   153  		}
   154  
   155  		sb.WriteString("│\n")
   156  	}
   157  	sb.WriteString("└───┴───┴───┘")
   158  
   159  	return sb.String()
   160  }
   161  
   162  type Result uint8
   163  
   164  const (
   165  	WillLose Result = iota
   166  	CanLose
   167  	Draw
   168  	CanWin
   169  	WillWin
   170  	FilledX
   171  	FilledO
   172  )
   173  
   174  func (r Result) String() string {
   175  	switch r {
   176  	case WillLose:
   177  		return "Will Lose"
   178  	case CanLose:
   179  		return "Can Lose"
   180  	case Draw:
   181  		return "Draw"
   182  	case CanWin:
   183  		return "Can Win"
   184  	case WillWin:
   185  		return "Will Win"
   186  	case FilledX:
   187  		return "Filled X"
   188  	case FilledO:
   189  		return "Filled O"
   190  	}
   191  
   192  	return "Invalid"
   193  }
   194  
   195  func (r Result) Switch() Result {
   196  	if r <= WillWin {
   197  		return WillWin - r
   198  	}
   199  
   200  	return r
   201  }
   202  
   203  type Results uint32
   204  
   205  func (rs Results) Get(p Position) Result {
   206  	return Result((rs >> (p * 3)) & 7)
   207  }
   208  
   209  func (rs Results) Set(p Position, r Result) Results {
   210  	return (rs & ^(7 << (p * 3))) | (Results(r) << (p * 3))
   211  }
   212  
   213  func (rs Results) SetState(b Result) Results {
   214  	return rs | (Results(b) << 27)
   215  }
   216  
   217  func (rs Results) GetState() Result {
   218  	return Result(rs >> 27)
   219  }
   220  
   221  func (rs Results) String() string {
   222  	var sb strings.Builder
   223  
   224  	sb.WriteString("Overall: ")
   225  	sb.WriteString(rs.GetState().String())
   226  	sb.WriteString("\n┌───┬───┬───┐\n")
   227  	for y := Position(0); y < 3; y++ {
   228  		if y > 0 {
   229  			sb.WriteString("├───┼───┼───┤\n")
   230  		}
   231  
   232  		for x := Position(0); x < 3; x++ {
   233  			sb.WriteString("│ ")
   234  			switch rs.Get(y*3 + x) {
   235  			case WillLose:
   236  				sb.WriteString("L")
   237  			case CanLose:
   238  				sb.WriteString("l")
   239  			case Draw:
   240  				sb.WriteString("D")
   241  			case CanWin:
   242  				sb.WriteString("w")
   243  			case WillWin:
   244  				sb.WriteString("W")
   245  			case FilledX:
   246  				sb.WriteString("X")
   247  			case FilledO:
   248  				sb.WriteString("O")
   249  			}
   250  			sb.WriteString(" ")
   251  		}
   252  
   253  		sb.WriteString("│\n")
   254  	}
   255  	sb.WriteString("└───┴───┴───┘")
   256  
   257  	return sb.String()
   258  }
   259  
   260  func (r Results) Encode() [3]byte {
   261  	var n uint32
   262  
   263  	pow := uint32(1)
   264  
   265  	for _, p := range Positions {
   266  		v := r.Get(p)
   267  
   268  		if v > CanLose {
   269  			v--
   270  		}
   271  
   272  		n += uint32(v) * pow
   273  
   274  		pow *= 6
   275  	}
   276  
   277  	return [3]byte{
   278  		byte(n >> 16),
   279  		byte(n >> 8),
   280  		byte(n),
   281  	}
   282  }
   283  
   284  type Brain map[Board]Results
   285  
   286  func NewBrain() Brain {
   287  	b := make(Brain)
   288  
   289  	b.move(emptyBoard)
   290  
   291  	return b
   292  }
   293  
   294  func (b Brain) move(board Board) Result {
   295  	if r, ok := b.getResults(board); ok {
   296  		return r.GetState()
   297  	}
   298  
   299  	var (
   300  		rs       Results
   301  		result   Result
   302  		hasEmpty bool
   303  	)
   304  
   305  	for _, p := range Positions {
   306  		if t := board.Get(p); t != None {
   307  			rs = rs.Set(p, FilledX+Result(t-1))
   308  			continue
   309  		}
   310  
   311  		hasEmpty = true
   312  
   313  		setBoard := board.Set(p, X)
   314  
   315  		var r Result
   316  
   317  		if setBoard.HasWin() {
   318  			r = WillWin
   319  		} else {
   320  			r = b.move(setBoard.Switch()).Switch()
   321  
   322  			if (r == Draw || r == CanLose) && setBoard.HasPossibleWin() {
   323  				r = CanWin
   324  			}
   325  		}
   326  
   327  		if r > result {
   328  			result = r
   329  		}
   330  
   331  		rs = rs.Set(p, r)
   332  	}
   333  
   334  	if !hasEmpty {
   335  		result = Draw
   336  	}
   337  
   338  	b[board] = rs.SetState(result)
   339  
   340  	return result
   341  }
   342  
   343  func (b Brain) getResults(board Board) (Results, bool) {
   344  	for i := uint8(0); i < 8; i++ {
   345  		if r, ok := b[board.Transform(i&4 != 0, i&3)]; ok {
   346  			return r, true
   347  		}
   348  	}
   349  
   350  	return 0, false
   351  }
   352  
   353  func main() {
   354  	var debug, js bool
   355  
   356  	flag.BoolVar(&debug, "d", false, "print all boards")
   357  	flag.BoolVar(&js, "j", false, "print brain wrapped in JS")
   358  
   359  	flag.Parse()
   360  
   361  	b := NewBrain()
   362  
   363  	boards := make([]Board, 0, len(b))
   364  
   365  	for board := range b {
   366  		boards = append(boards, board)
   367  	}
   368  
   369  	slices.Sort(boards)
   370  
   371  	if debug {
   372  		for _, board := range boards {
   373  			results := b[board]
   374  			b := strings.Split(board.String(), "\n")
   375  			r := strings.Split(results.String(), "\n")
   376  
   377  			fmt.Println("             ", r[0])
   378  
   379  			for n, rs := range r[1:] {
   380  				fmt.Println(b[n], rs)
   381  			}
   382  
   383  		}
   384  
   385  		fmt.Printf("%d boards\n", len(b))
   386  	} else {
   387  		var sb strings.Builder
   388  
   389  		w := base64.NewEncoder(base64.StdEncoding, &sb)
   390  
   391  		for _, board := range boards {
   392  			v := b[board].Encode()
   393  
   394  			w.Write(v[:])
   395  		}
   396  
   397  		w.Close()
   398  
   399  		if js {
   400  			fmt.Printf("export default %q;", sb.String())
   401  		} else {
   402  			fmt.Println(sb.String())
   403  		}
   404  	}
   405  }
   406