Documentation ¶
Index ¶
- Constants
- func BoardPos(col, row BitboardPos) string
- func Col(i BitboardPos) int
- func CreateRunes(char rune, length int) []rune
- func ExplainCardSlice(cards []Card) string
- func FetchMetrics(maxDepth int)
- func GenCardConfigs(selection []Card) (configs [][]Card)
- func InfinityBranch(st *State) bool
- func NewGame() (st State, game Game)
- func OrganizePathsByFirstMove(paths [][]Move) (branches [][][]Move)
- func RemoveDuplicates(paths [][]Move, blues bool) (forced [][]Move)
- func Row(i BitboardPos) int
- func SearchExhaustive(cards []Card, targetDepth uint64) (metrics []DepthMetric, winPaths *MoveNode, duration time.Duration)
- func SearchExhaustiveInfinityPaths(cards []Card, targetDepth uint64, limitHits int) (paths [][]Move, duration time.Duration)
- func SplitMovesIntoBlueAndBrownWins(paths [][]Move) (blues, browns [][]Move)
- type Bitboard
- func CompactBoardToBitBoard(compact Bitboard) (board Bitboard)
- func CurrentMasterBitboard(st *State) Bitboard
- func FlipHorizontal(b Bitboard) Bitboard
- func FlipVertical(b Bitboard) Bitboard
- func MakeCompactBoard(board Bitboard) (compact Bitboard)
- func MakeCompactBoardFast(board Bitboard) Bitboard
- func MakeSemiCompactBoard(board Bitboard) Bitboard
- func Merge(boards []Bitboard) (b Bitboard)
- func OtherMasterBitboard(st *State) Bitboard
- func OtherPiecesBitboard(st *State) Bitboard
- func RemoveMSB(x Bitboard) Bitboard
- func RotateBoard(b Bitboard) Bitboard
- type BitboardHeatmap
- type BitboardPos
- type ByNilMoves
- type Card
- type DepthMetric
- type Game
- type Key
- type Move
- func (m Move) Action() Number
- func (m Move) BoardIndex() Number
- func (m Move) Card(playerIndex Number, cardsBeforeMove []Card) Card
- func (m Move) CardIndex() Number
- func (m *Move) Encode(st *State, fromIndex, toIndex, cardIndex BitboardPos)
- func (m Move) From() BitboardPos
- func (m Move) HostileBoardIndex() Number
- func (m Move) Pass() bool
- func (m Move) PieceType() Piece
- func (m *Move) Reset()
- func (m Move) String() string
- func (m Move) To() BitboardPos
- func (m Move) Win() bool
- func (m Move) WinByTemple() bool
- type MoveNode
- type MoveStack
- type Number
- type Piece
- type Stack
- type State
- func (st *State) ApplyMove(move Move)
- func (st *State) CreateGame(cards []Card)
- func (st *State) Depth() Number
- func (st *State) GenerateMoves()
- func (st *State) IsParentCacheKey(k Key) bool
- func (st *State) MoveHistory() []Move
- func (st *State) Moves() []Move
- func (st *State) MovesLen() int
- func (st *State) NextPlayer() uint8
- func (st *State) Reset()
- func (st State) String() string
- func (st *State) UndoMove()
- type StateDecoder
- type StateEncoder
Constants ¶
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 )
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 )
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 )
const CacheableSubTreeMinHeight = 7
const HighestNrOfMoves = 4
HighestNrOfMoves holds teh highest number of moves on any card
const (
MaskKeyBoards uint64 = 0x1ffffff
)
const MaxDepth = oniconst.MaxDepth
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.
const NrOfActiveCards = 5
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 ExplainCardSlice ¶
func FetchMetrics ¶
func FetchMetrics(maxDepth int)
func GenCardConfigs ¶
GenCardConfigs generates all possible unique card configurations that respects the ordered set ({a1, a2}, {a3, a4}, a5)
func InfinityBranch ¶
func RemoveDuplicates ¶
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
Types ¶
type Bitboard ¶
type Bitboard = uint64
func CompactBoardToBitBoard ¶
func CurrentMasterBitboard ¶
func FlipHorizontal ¶
FlipHorizontal Flip a bitboard horizontally
func MakeCompactBoard ¶
MakeCompactBoard takes a bitboard and compresses it into 25 bits
func MakeCompactBoardFast ¶
MakeCompactBoard takes a bitboard and compresses it into 25 bits using ASM
func MakeSemiCompactBoard ¶
MakeSemiCompactBoard takes a bitboard and compresses it into 34 bits
func OtherMasterBitboard ¶
func OtherPiecesBitboard ¶
func RotateBoard ¶
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
type ByNilMoves ¶
type ByNilMoves struct {
// contains filtered or unexported fields
}
func (ByNilMoves) Less ¶
func (s ByNilMoves) Less(i, j int) bool
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 ¶
CardConfig create a card configuration with awareness of which players holds which cards and what the idle card is.
func DrawCards ¶
func DrawCards() (selection []Card)
DrawCards draws five random cards from the original 16 card deck
func (Card) Heatmap ¶
func (c Card) Heatmap() (b BitboardHeatmap)
type DepthMetric ¶
type DepthMetric struct { StudentsKilled uint64 MastersKilled uint64 TemplesTaken uint64 NonViolentMoves uint64 Depth uint8 ActivePlayer uint8 GeneratedMoves uint64 }
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) Encode ¶
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
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) BoardIndex ¶
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 (Move) To ¶
func (m Move) To() BitboardPos
func (Move) WinByTemple ¶
type 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 ¶
type Number ¶
type Number = uint64
const ( BrownPlayer Number = iota BluePlayer NrOfPlayers Number = BluePlayer + 1 OppositePlayer = BrownPlayer )
type State ¶
type State struct {
// contains filtered or unexported fields
}
func (*State) CreateGame ¶
CreateGame
cards[0-1]: brown player (opponent) cards[2-3]: blue player (current) cards[4-4]: idle card
func (*State) GenerateMoves ¶
func (st *State) GenerateMoves()
func (*State) IsParentCacheKey ¶
func (*State) MoveHistory ¶
func (*State) NextPlayer ¶
type StateDecoder ¶
type StateDecoder interface {
Decode(*State)
}
type StateEncoder ¶
type StateEncoder interface {
Encode(*State)
}