onitamago

package module
v0.0.0-...-8d4fee9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 26, 2019 License: GPL-3.0 Imports: 14 Imported by: 0

README

Onitamago

Go package to calculate onitama moves N steps ahead. Features:

  • Caching
  • Terminates branch exploration on wins
  • Metrics
  • Infinity branch detection
  • Heatmap generation for cards and pieces on the board
  • Iterative depth first search

Also holds benchmarks for several concepts. Also benchmarks of exhaustive search done for with and without caching, with and without metrics fetching.

Missing heuristics to make educated guesses about best moves, alpha-beta pruning, min-max/nega-max.

Build tags

  • onitama_cache
  • onitama_metrics
  • onitama_noinfinity (currently depends on onitama_cache)

Documentation

Index

Constants

View Source 
const (
	BitboardCenterPos BitboardPos = 27

	// Board mask is the actual area of the Board type that is used by the players
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	45	44	43	42	41	_  R5
	//  _	_	37	36	35	34	33	_  R4
	//  _	_	29	28	27	26	35	_  R3
	//  _	_	21	20	19	18	17	_  R2
	//  _	_	13	12	11	10	09	_  R1
	//  _	_	_	_	_	_	_	_
	BoardMask Bitboard = 0x3e3e3e3e3e00

	// rows and columns
	// rows starts at the bottom, going up, just like chess
	// and columns starts left, going right, just like chess
	R1Mask Bitboard = 0x3e00
	R2Mask Bitboard = R1Mask << 8
	R3Mask Bitboard = R2Mask << 8
	R4Mask Bitboard = R3Mask << 8
	R5Mask Bitboard = R4Mask << 8

	AMask Bitboard = 0x202020202000
	BMask Bitboard = AMask >> 1
	CMask Bitboard = BMask >> 1
	DMask Bitboard = CMask >> 1
	EMask Bitboard = DMask >> 1

	// BoardMaskOffset ...
	BoardMaskOffset BitboardPos = 0x9

	TempleTop    Bitboard = 0x80000000000
	TempleBottom Bitboard = 0x800

	StudentsTop    Bitboard = 0x360000000000
	StudentsBottom Bitboard = 0x3600

	MasterTop    Bitboard = TempleTop
	MasterBottom Bitboard = TempleBottom
)
View Source 
const (
	DeckOriginal = iota
	DeckSenseisPath

	// CardOffset is how many bit position the initial card masks are shifted
	// remember that offset is number of bit positions. Note that every card
	// has their center at bit position 45.
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	45	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	//  _	_	_	_	_	_	_	_
	CardOffset BitboardPos = 45
)
View Source 
const (
	NrOfPieceTypes   uint64 = 3 // student, master, temple. temples cannot move
	NrOfPlayerPieces uint64 = 5

	StudentsIndex uint64 = 0
	MasterIndex   uint64 = 1
	TrashIndex    uint64 = 2

	Student Piece = 0
	Master  Piece = 1
)
View Source 
const CacheableSubTreeMinHeight = 7
View Source 
const HighestNrOfMoves = 4

HighestNrOfMoves holds teh highest number of moves on any card

View Source 
const (
	MaskKeyBoards uint64 = 0x1ffffff
)
View Source 
const MaxDepth = oniconst.MaxDepth
View Source 
const MoveUndo = ^Move(0)

TypeUndoMove can be used to signify the state should undo the current move may it be to go backwards in a game tree or for other reasons.

View Source 
const NrOfActiveCards = 5
View Source 
const NrOfPlayerCards = 2

Variables

This section is empty.

Functions

func BoardPos 

func BoardPos(col, row BitboardPos) string

func Col 

func Col(i BitboardPos) int

func CreateRunes 

func CreateRunes(char rune, length int) []rune

func ExplainCardSlice 

func ExplainCardSlice(cards []Card) string

func FetchMetrics 

func FetchMetrics(maxDepth int)

func GenCardConfigs 

func GenCardConfigs(selection []Card) (configs [][]Card)

GenCardConfigs generates all possible unique card configurations that respects the ordered set ({a1, a2}, {a3, a4}, a5)

func InfinityBranch 

func InfinityBranch(st *State) bool

func NewGame 

func NewGame() (st State, game Game)

func OrganizePathsByFirstMove 

func OrganizePathsByFirstMove(paths [][]Move) (branches [][][]Move)

func RemoveDuplicates 

func RemoveDuplicates(paths [][]Move, blues bool) (forced [][]Move)

func Row 

func Row(i BitboardPos) int

func SearchExhaustive 

func SearchExhaustive(cards []Card, targetDepth uint64) (metrics []DepthMetric, winPaths *MoveNode, duration time.Duration)

SearchExhaustive uses Depth first search to goes through the entire game tree generated from the card configuration until the target Depth is reached. However, when a parent generates children moves that causes a win, that parent branch is no longer explored as it's assumed the player prioritizes a win instead of continuing the game.

Build tags - onitama_store_wins will populate winPaths

func SearchExhaustiveInfinityPaths 

func SearchExhaustiveInfinityPaths(cards []Card, targetDepth uint64, limitHits int) (paths [][]Move, duration time.Duration)

SearchExhaustiveInfinityPaths looks through a card configuration to detect if a infinity branch exists within the given search space. Note that pruning for wins are turned off so this has a larger search space then the SearchExhaustive function. Required build tags: - onitama_cache: to store the parent states as unique keys for look ups

func SplitMovesIntoBlueAndBrownWins 

func SplitMovesIntoBlueAndBrownWins(paths [][]Move) (blues, browns [][]Move)

Types

type Bitboard 

type Bitboard = uint64

func CompactBoardToBitBoard 

func CompactBoardToBitBoard(compact Bitboard) (board Bitboard)

func CurrentMasterBitboard 

func CurrentMasterBitboard(st *State) Bitboard

func FlipHorizontal 

func FlipHorizontal(b Bitboard) Bitboard

FlipHorizontal Flip a bitboard horizontally

func FlipVertical 

func FlipVertical(b Bitboard) Bitboard

FlipVertical Flip a bitboard vertically

func MakeCompactBoard 

func MakeCompactBoard(board Bitboard) (compact Bitboard)

MakeCompactBoard takes a bitboard and compresses it into 25 bits

func MakeCompactBoardFast 

func MakeCompactBoardFast(board Bitboard) Bitboard

MakeCompactBoard takes a bitboard and compresses it into 25 bits using ASM

func MakeSemiCompactBoard 

func MakeSemiCompactBoard(board Bitboard) Bitboard

MakeSemiCompactBoard takes a bitboard and compresses it into 34 bits

func Merge 

func Merge(boards []Bitboard) (b Bitboard)

func OtherMasterBitboard 

func OtherMasterBitboard(st *State) Bitboard

func OtherPiecesBitboard 

func OtherPiecesBitboard(st *State) Bitboard

func RemoveMSB 

func RemoveMSB(x Bitboard) Bitboard

RemoveMSB removes most significant bit

func RotateBoard 

func RotateBoard(b Bitboard) Bitboard

type BitboardHeatmap 

type BitboardHeatmap [5][5]uint // y, x

func (*BitboardHeatmap) AddBoard 

func (b *BitboardHeatmap) AddBoard(board Bitboard)

func (*BitboardHeatmap) AddCard 

func (b *BitboardHeatmap) AddCard(card Card)

func (*BitboardHeatmap) Merge 

func (b *BitboardHeatmap) Merge(m *BitboardHeatmap)

func (*BitboardHeatmap) Render 

func (b *BitboardHeatmap) Render(options ...interface{}) (img *image.NRGBA)

func (*BitboardHeatmap) RenderOneCard 

func (b *BitboardHeatmap) RenderOneCard() (img *image.NRGBA)

type BitboardPos 

type BitboardPos = Bitboard

func BoardToIndex 

func BoardToIndex(x Bitboard) BitboardPos

func LSB 

func LSB(x Bitboard) BitboardPos

LSB Least Significant Bit

func NLSB 

func NLSB(x *Bitboard, i BitboardPos) BitboardPos

NLSB Next Least Significant Bit

type ByNilMoves 

type ByNilMoves struct {
	// contains filtered or unexported fields
}

func (ByNilMoves) Len 

func (m ByNilMoves) Len() int

func (ByNilMoves) Less 

func (s ByNilMoves) Less(i, j int) bool

func (ByNilMoves) Swap 

func (m ByNilMoves) Swap(i, j int)

type Card 

type Card Bitboard

//go:generate stringer -type=Card 

const (
	// Tiger card
	//  _  _  X  _  _
	//  _  _  _  _  _
	//  _  _  O  _  _
	//  _  _  X  _  _
	Tiger        Card = 0x2000202000000000
	TigerRotated Card = 0x20200020000000

	// Dragon card
	//  _  _  _  _  _
	//  X  _  _  _  X
	//  _  _  O  _  _
	//  _  X  _  X  _
	//  _  _  _  _  _
	Dragon        Card = 0x88205000000000
	DragonRotated Card = 0x50208800000000

	// Frog card
	//  _  _  _  _  _
	//  _  X  _  _  _
	//  X  _  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Frog        Card = 0x40A01000000000
	FrogRotated Card = 0x40281000000000

	// Rabbit card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  O  _  X  _
	//  X  _  _  _  _
	//  _  _  _  _  _
	Rabbit        Card = 0x10284000000000
	RabbitRotated Card = 0x10A04000000000

	// Crab card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  X  _  O  _  X
	//  _  _  _  _  _
	//  _  _  _  _  _
	Crab        Card = 0x20a80000000000
	CrabRotated Card = 0xa82000000000

	// Elephant card
	//  _  _  _  _  _
	//  _  X  _  X  _
	//  _  X  O  X  _
	//  _  _  _  _  _
	//  _  _  _  _  _
	Elephant        Card = 0x50700000000000
	ElephantRotated Card = 0x705000000000

	// Goose card
	//  _  _  _  _  _
	//  _  X  _  _  _
	//  _  X  O  X  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Goose        Card = 0x40701000000000
	GooseRotated Card = Goose

	// Rooster card
	//  _  _  _  _  _
	//  _  _  _  X  _
	//  _  X  O  X  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Rooster        Card = 0x10704000000000
	RoosterRotated Card = Rooster

	// Monkey card
	//  _  _  _  _  _
	//  _  X  _  X  _
	//  _  _  O  _  _
	//  _  X  _  X  _
	//  _  _  _  _  _
	Monkey        Card = 0x50205000000000
	MonkeyRotated Card = Monkey

	// Mantis card
	//  _  _  _  _  _
	//  _  X  _  X  _
	//  _  _  O  _  _
	//  _  _  X  _  _
	//  _  _  _  _  _
	Mantis        Card = 0x50202000000000
	MantisRotated Card = Crane

	// Horse card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  X  O  _  _
	//  _  _  X  _  _
	//  _  _  _  _  _
	Horse        Card = 0x20602000000000
	HorseRotated Card = Ox

	// Ox card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  _  O  X  _
	//  _  _  X  _  _
	//  _  _  _  _  _
	Ox        Card = 0x20302000000000
	OxRotated Card = Horse

	// Crane card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  _  O  _  _
	//  _  X  _  X  _
	//  _  _  _  _  _
	Crane        Card = 0x20205000000000
	CraneRotated Card = Mantis

	// Boar card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  X  O  X  _
	//  _  _  _  _  _
	//  _  _  _  _  _
	Boar        Card = 0x20700000000000
	BoarRotated Card = 0x702000000000

	// Eel card
	//  _  _  _  _  _
	//  _  X  _  _  _
	//  _  _  O  X  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Eel        Card = 0x40304000000000
	EelRotated Card = Cobra

	// Cobra card
	//  _  _  _  _  _
	//  _  _  _  X  _
	//  _  X  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Cobra        Card = 0x10601000000000
	CobraRotated Card = Eel
)

DeckOriginal cards 

const (
	// Turtle card
	//  _  _  _  _  _
	//  _  _  _  _  _
	//  X  _  O  _  X
	//  _  X  _  X  _
	//  _  _  _  _  _
	Turtle        Card = 0xa85000000000
	TurtleRotated Card = Pheonix

	// Pheonix card
	//  _  _  _  _  _
	//  _  X  _  X  _
	//  X  _  O  _  X
	//  _  _  _  _  _
	//  _  _  _  _  _
	Pheonix        Card = 0x50a80000000000
	PheonixRotated Card = Turtle

	// Otter card
	//  _  _  _  _  _
	//  _  X  _  _  _
	//  _  _  O  _  X
	//  _  _  _  X  _
	//  _  _  _  _  _
	Otter        Card = 0x40281000000000
	OtterRotated Card = 0x40a01000000000

	// Iguana card
	//  _  _  _  _  _
	//  X  _  X  _  _
	//  _  _  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Iguana        Card = 0xa0201000000000
	IguanaRotated Card = 0x40202800000000

	// Sable card
	//  _  _  _  _  _
	//  _  _  _  X  _
	//  X  _  O  _  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Sable        Card = 0x10a04000000000
	SableRotated Card = 0x10284000000000

	// Panda card
	//  _  _  _  _  _
	//  _  _  X  X  _
	//  _  _  O  _  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Panda        Card = 0x30204000000000
	PandaRotated Card = 0x10206000000000

	// Bear card
	//  _  _  _  _  _
	//  _  X  X  _  _
	//  _  _  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Bear        Card = 0x60201000000000
	BearRotated Card = 0x40203000000000

	// Fox card
	//  _  _  _  _  _
	//  _  _  _  X  _
	//  _  _  O  X  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Fox        Card = 0x10301000000000
	FoxRotated Card = Dog

	// Giraffe card
	//  _  _  _  _  _
	//  X  _  _  _  X
	//  _  _  O  _  _
	//  _  _  X  _  _
	//  _  _  _  _  _
	Giraffe        Card = 0x88202000000000
	GiraffeRotated Card = 0x20208800000000

	// Kirin card
	//  _  X  _  X  _
	//  _  _  _  _  _
	//  _  _  O  _  _
	//  _  _  _  _  _
	//  _  _  X  _  _
	Kirin        Card = 0x5000200020000000
	KirinRotated Card = 0x2000200050000000

	// Rat card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  X  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Rat        Card = 0x20601000000000
	RatRotated Card = 0x40302000000000

	// Tanuki card
	//  _  _  _  _  _
	//  _  _  X  _  X
	//  _  _  O  _  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Tanuki        Card = 0x28204000000000
	TanukiRotated Card = 0x1020a000000000

	// Mouse card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  _  O  X  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Mouse        Card = 0x20304000000000
	MouseRotated Card = 0x10602000000000

	// Viper card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  X  _  O  _  _
	//  _  _  _  X  _
	//  _  _  _  _  _
	Viper        Card = 0x20a01000000000
	ViperRotated Card = 0x40282000000000

	// Sea Snake card
	//  _  _  _  _  _
	//  _  _  X  _  _
	//  _  _  O  _  X
	//  _  X  _  _  _
	//  _  _  _  _  _
	SeaSnake        Card = 0x20284000000000
	SeaSnakeRotated Card = 0x10a02000000000

	// Dog card
	//  _  _  _  _  _
	//  _  X  _  _  _
	//  _  X  O  _  _
	//  _  X  _  _  _
	//  _  _  _  _  _
	Dog        Card = 0x40604000000000
	DogRotated Card = Fox
)

DeckSenseisPath cards

func CardConfig 

func CardConfig(blue [2]Card, brown [2]Card, idle Card) []Card

CardConfig create a card configuration with awareness of which players holds which cards and what the idle card is.

func Deck 

func Deck(deckTypes ...uint) (cards []Card)

func DrawCards 

func DrawCards() (selection []Card)

DrawCards draws five random cards from the original 16 card deck

func (Card) Bitboard 

func (c Card) Bitboard() Bitboard

func (Card) Heatmap 

func (c Card) Heatmap() (b BitboardHeatmap)

func (Card) Name 

func (c Card) Name() string

func (*Card) Rotate 

func (c *Card) Rotate()

func (Card) Rotated 

func (c Card) Rotated() Card

func (Card) String 

func (c Card) String() string

type DepthMetric 

type DepthMetric struct {
	StudentsKilled  uint64
	MastersKilled   uint64
	TemplesTaken    uint64
	NonViolentMoves uint64

	Depth          uint8
	ActivePlayer   uint8
	GeneratedMoves uint64
}

func SearchExhaustiveForForcedWins 

func SearchExhaustiveForForcedWins(cards []Card, targetDepth uint64) (metrics []DepthMetric, paths [][]Move, duration time.Duration)

func SearchForTempleWins 

func SearchForTempleWins(cards []Card, targetDepth uint64) (metrics []DepthMetric, paths [][]Move, duration time.Duration)

SearchForTempleWins Stores paths of moves whenever a win by temple is achieved

func (*DepthMetric) Increment 

func (m *DepthMetric) Increment(metric *DepthMetric)

func (*DepthMetric) Reset 

func (m *DepthMetric) Reset()

func (DepthMetric) String 

func (m DepthMetric) String() string

type Game 

type Game struct {
	// game tree with Depth of 40
	// one Depth at the time... same as chess
	Tree [HighestNrOfMoves * NrOfPlayerPieces * MaxDepth]Move
}

type Key 

type Key uint64

Key represents all the pieces, current player, relative cards. move history is discarded.

Note! this will not function for states with missing masters and as such should not 

be calculated on leaf nodes.

func (Key) Decode 

func (k Key) Decode(st *State)

Deprecated Does not work with the new encoder

func (*Key) Encode 

func (k *Key) Encode(st *State)

Encode converts a State into a uint64 key that can be used in caching and other situations to compare states. Note that the key is not unique across card configurations and assumes that interacting keys uses the same card configuration as its base.

Assumptions/requirements:

  • The state has both masters
  • At least one blue piece exists

func (Key) String 

func (k Key) String() string

String pretty print the binary version where segments and card indexes are separated. 

eg. the key 8093039719199539215 is pretty printed as
    011.100.000|1|01000|00100|0000101111|1011110000000001000000000000001111

type Move 

type Move uint16

Move holds from, to, actions, the player, and which card index was used. 

const MoveMaskAction Move = 0x7 << 12
const MoveMaskCardIndex Move = 0x1 << 15
const MoveMaskFrom Move = MovePositionMask << 6
const MoveMaskTo Move = MovePositionMask << 0
const MovePassBase Move = 2 << 12 // action: master move

MovePassBase is the base to build a pass move. A Pass move is simply a normal move where the master piece, the piece that will always exist when a player can move, has the same from as to value; meaning they do not relocate. The card index must be set. Since you must create a pass situation for each card there must exist at least two pass moves when _no_ normal move can be executed. 

const MovePositionMask Move = 0x3f

func (Move) Action 

func (m Move) Action() Number

func (Move) BoardIndex 

func (m Move) BoardIndex() Number

func (Move) Card 

func (m Move) Card(playerIndex Number, cardsBeforeMove []Card) Card

func (Move) CardIndex 

func (m Move) CardIndex() Number

func (*Move) Encode 

func (m *Move) Encode(st *State, fromIndex, toIndex, cardIndex BitboardPos)

func (Move) From 

func (m Move) From() BitboardPos

func (Move) HostileBoardIndex 

func (m Move) HostileBoardIndex() Number

func (Move) Pass 

func (m Move) Pass() bool

func (Move) PieceType 

func (m Move) PieceType() Piece

func (*Move) Reset 

func (m *Move) Reset()

func (Move) String 

func (m Move) String() string

func (Move) To 

func (m Move) To() BitboardPos

func (Move) Win 

func (m Move) Win() bool

func (Move) WinByTemple 

func (m Move) WinByTemple() bool

type MoveNode 

type MoveNode struct {
	Instances uint64
	Depth     uint8
	Paths     map[Move]*MoveNode
	Parent    *MoveNode
}

first node is considered root. You can think of it as it requires no moves to reach it, since it is the starting point.

func ConvertPathsToTree 

func ConvertPathsToTree(paths [][]Move) (tree *MoveNode, nrOfNodes uint)

type MoveStack 

type MoveStack interface {
	Pop() Move
	Push(Move)
}

type Number 

type Number = uint64
const (
	BrownPlayer Number = iota
	BluePlayer
	NrOfPlayers Number = BluePlayer + 1

	OppositePlayer = BrownPlayer
)

type Piece 

type Piece uint8 // to simplify move extraction

type Stack 

type Stack struct {
	// contains filtered or unexported fields
}

func (*Stack) Pop 

func (s *Stack) Pop() Move

func (*Stack) Push 

func (s *Stack) Push(m Move)

func (*Stack) PushMany 

func (s *Stack) PushMany(m []Move)

func (*Stack) Size 

func (s *Stack) Size() int

type State 

type State struct {
	// contains filtered or unexported fields
}

func NewState 

func NewState() State

func (*State) ApplyMove 

func (st *State) ApplyMove(move Move)

func (*State) CreateGame 

func (st *State) CreateGame(cards []Card)

CreateGame 

cards[0-1]: brown player (opponent)
cards[2-3]: blue player (current)
cards[4-4]: idle card

func (*State) Depth 

func (st *State) Depth() Number

func (*State) GenerateMoves 

func (st *State) GenerateMoves()

func (*State) IsParentCacheKey 

func (st *State) IsParentCacheKey(k Key) bool

func (*State) MoveHistory 

func (st *State) MoveHistory() []Move

func (*State) Moves 

func (st *State) Moves() []Move

func (*State) MovesLen 

func (st *State) MovesLen() int

func (*State) NextPlayer 

func (st *State) NextPlayer() uint8

func (*State) Reset 

func (st *State) Reset()

func (State) String 

func (st State) String() string

func (*State) UndoMove 

func (st *State) UndoMove()

type StateDecoder 

type StateDecoder interface {
	Decode(*State)
}

type StateEncoder 

type StateEncoder interface {
	Encode(*State)
}

Source Files

View all Source files

Directories

Path Synopsis
perft
cmd
calculations

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.