Package ai.nettogrof.battlesnake.treesearch

Class AbstractBestFirstSearch

java.lang.Object

ai.nettogrof.battlesnake.treesearch.AbstractSearch

ai.nettogrof.battlesnake.treesearch.AbstractBestFirstSearch

All Implemented Interfaces:

Runnable

Direct Known Subclasses:

AbstractMCTS

public abstract class AbstractBestFirstSearch
extends AbstractSearch

This abstract BestFirst search, provide basic method use in any search using Best First type of search

Version:

Spring 2021

Author:

carl.lajeunesse

Field Summary

Fields inherited from class ai.nettogrof.battlesnake.treesearch.AbstractSearch

cont, height, root, rules, startTime, timeout, width

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractBestFirstSearch()	Sole constructor.

Method Summary

Modifier and Type	Method	Description
private void	fillList(gnu.trove.list.array.TFloatArrayList upward, gnu.trove.list.array.TFloatArrayList down, gnu.trove.list.array.TFloatArrayList left, gnu.trove.list.array.TFloatArrayList right, AbstractNode node)	This method fill 4 list (one for each direction ) with the score of each node based on the move direction
AbstractNode	getBestChild(AbstractNode node)	This method find and return the best leaf node
protected float	getbestChildValue(gnu.trove.list.array.TFloatArrayList upward, gnu.trove.list.array.TFloatArrayList down, gnu.trove.list.array.TFloatArrayList left, gnu.trove.list.array.TFloatArrayList right)	This method return the scoreRatio of the best choice based on payoff Matrix
protected List<AbstractNode>	getBestPath(AbstractNode node)	This method is use to find the next leaf node to explore using MCTS algo
private AbstractNode	getWinnerChild(AbstractNode node)	Get the best child/winner from a node
protected void	mergeList(List<AbstractNode> tree, List<AbstractNode> branch)	This method just merge two lists and remove the duplicate node
protected void	updateFullListNode(List<AbstractNode> tree)	This method updateScore from each node
protected List<AbstractNode>	updateListNode(List<AbstractNode> branch)	This method get a branch, update score starting from the leaf.

Methods inherited from class ai.nettogrof.battlesnake.treesearch.AbstractSearch

addMove, checkHeadToHead, createSnakeInfo, freeSpace, generateChild, generateChild, generateSnakeInfoDestination, getSmallestChild, kill, merge, moveSnake, stopSearching

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Runnable

run

Constructor Detail

AbstractBestFirstSearch

protected AbstractBestFirstSearch()

Sole constructor. (For invocation by subclass constructors, typically implicit.)

Method Detail

mergeList

protected void mergeList(List<AbstractNode> tree,
                         List<AbstractNode> branch)

This method just merge two lists and remove the duplicate node

Parameters:

tree - List of node from root to branch

branch - List of node from branch to leaf

updateFullListNode

protected void updateFullListNode(List<AbstractNode> tree)

This method updateScore from each node

Parameters:

tree - List of node to update

updateListNode

protected List<AbstractNode> updateListNode(List<AbstractNode> branch)

This method get a branch, update score starting from the leaf. if a node score have changed, remove the node from the list.

Parameters:

branch - List of node of that branch

Returns:

list of node that score doesn't have changed.

getBestPath

protected List<AbstractNode> getBestPath(AbstractNode node)

This method is use to find the next leaf node to explore using MCTS algo

Parameters:

node - The root node

Returns:

List of node from the leaf to the root

getWinnerChild

private AbstractNode getWinnerChild(AbstractNode node)

Get the best child/winner from a node

Parameters:

node - the parent node

Returns:

the winner/best child

fillList

private void fillList(gnu.trove.list.array.TFloatArrayList upward,
                      gnu.trove.list.array.TFloatArrayList down,
                      gnu.trove.list.array.TFloatArrayList left,
                      gnu.trove.list.array.TFloatArrayList right,
                      AbstractNode node)

This method fill 4 list (one for each direction ) with the score of each node based on the move direction

Parameters:

upward - float array list

down - float array list

left - float array list

right - float array list

node - parent node

getbestChildValue

protected float getbestChildValue(gnu.trove.list.array.TFloatArrayList upward,
                                  gnu.trove.list.array.TFloatArrayList down,
                                  gnu.trove.list.array.TFloatArrayList left,
                                  gnu.trove.list.array.TFloatArrayList right)

This method return the scoreRatio of the best choice based on payoff Matrix

Parameters:

upward - float array list

down - float array list

left - float array list

right - float array list

Returns:

score float

getBestChild

public AbstractNode getBestChild(AbstractNode node)

This method find and return the best leaf node

Parameters:

node - Parent node

Returns:

AbstractNode best leaf node