{-
	Copyright (C) 2018 Dr. Alistair Ward

	This file is part of BishBosh.

	BishBosh is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	BishBosh is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with BishBosh.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Searches for the optimal /move/ from those currently available.
-}

module BishBosh.Search.Search(
-- * Types
-- ** Data-types
	Result (
--		MkResult,
		getSearchState,
		getQuantifiedGames,
		getNPliesEvaluated
	),
-- * Constants
	showsSeparator,
-- * Functions
	search
--	calculateBranchingFactor,
-- ** Constructor
--	mkResult
 ) where

import			Control.Arrow((&&&))
import qualified	BishBosh.Component.Move					as Component.Move
import qualified	BishBosh.Data.Exception					as Data.Exception
import qualified	BishBosh.Evaluation.PositionHashQuantifiedGameTree	as Evaluation.PositionHashQuantifiedGameTree
import qualified	BishBosh.Evaluation.QuantifiedGame			as Evaluation.QuantifiedGame
import qualified	BishBosh.Input.SearchOptions				as Input.SearchOptions
import qualified	BishBosh.Model.Game					as Model.Game
import qualified	BishBosh.Notation.MoveNotation				as Notation.MoveNotation
import qualified	BishBosh.Search.AlphaBeta				as Search.AlphaBeta
import qualified	BishBosh.Search.EphemeralData				as Search.EphemeralData
import qualified	BishBosh.Search.SearchState				as Search.SearchState
import qualified	BishBosh.State.TurnsByLogicalColour			as State.TurnsByLogicalColour
import qualified	BishBosh.Text.ShowList					as Text.ShowList
import qualified	BishBosh.Types						as T
import qualified	Control.DeepSeq
import qualified	Control.Exception
import qualified	Control.Monad.Reader
import qualified	Data.Maybe

-- | The type returned by 'search'.
data Result x y positionHash criterionValue weightedMean	= MkResult {
	Result x y positionHash criterionValue weightedMean
-> SearchState x y positionHash criterionValue weightedMean
getSearchState		:: Search.SearchState.SearchState x y positionHash criterionValue weightedMean,
	Result x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
getQuantifiedGames	:: [Evaluation.QuantifiedGame.QuantifiedGame x y criterionValue weightedMean],	-- ^ The optimal path down the /positionHashQuantifiedGameTree/.
	Result x y positionHash criterionValue weightedMean -> NPlies
getNPliesEvaluated	:: Component.Move.NPlies							-- ^ The total number of nodes in the /positionHashQuantifiedGameTree/ which were analysed.
}

instance Control.DeepSeq.NFData weightedMean => Control.DeepSeq.NFData (Result x y positionHash criterionValue weightedMean) where
	rnf :: Result x y positionHash criterionValue weightedMean -> ()
rnf MkResult { getQuantifiedGames :: forall x y positionHash criterionValue weightedMean.
Result x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
getQuantifiedGames = [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames }	= [QuantifiedGame x y criterionValue weightedMean] -> ()
forall a. NFData a => a -> ()
Control.DeepSeq.rnf [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames	-- CAVEAT: don't evaluate the search-state, since this contains the PositionHashQuantifiedGameTree !

-- | Used to format output.
showsSeparator :: ShowS
showsSeparator :: ShowS
showsSeparator	= String -> ShowS
showString String
" -> "

instance (Enum x, Enum y, Real criterionValue, Real weightedMean) => Notation.MoveNotation.ShowNotationFloat (Result x y positionHash criterionValue weightedMean) where
	showsNotationFloat :: MoveNotation
-> (Double -> ShowS)
-> Result x y positionHash criterionValue weightedMean
-> ShowS
showsNotationFloat MoveNotation
moveNotation Double -> ShowS
showsDouble result :: Result x y positionHash criterionValue weightedMean
result@MkResult {
		getQuantifiedGames :: forall x y positionHash criterionValue weightedMean.
Result x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
getQuantifiedGames	= [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames,
		getNPliesEvaluated :: forall x y positionHash criterionValue weightedMean.
Result x y positionHash criterionValue weightedMean -> NPlies
getNPliesEvaluated	= NPlies
nPliesEvaluated
	} = ShowS
-> (QuantifiedGame x y criterionValue weightedMean -> ShowS)
-> [QuantifiedGame x y criterionValue weightedMean]
-> ShowS
forall a. ShowS -> (a -> ShowS) -> [a] -> ShowS
Text.ShowList.showsFormattedList ShowS
showsSeparator (
		MoveNotation
-> (Double -> ShowS)
-> QuantifiedGame x y criterionValue weightedMean
-> ShowS
forall a.
ShowNotationFloat a =>
MoveNotation -> (Double -> ShowS) -> a -> ShowS
Notation.MoveNotation.showsNotationFloat MoveNotation
moveNotation Double -> ShowS
showsDouble
	 ) [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"; selected after analysing " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NPlies -> ShowS
forall a. Show a => a -> ShowS
shows NPlies
nPliesEvaluated ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" nodes" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (
		if [QuantifiedGame x y criterionValue weightedMean] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames Bool -> Bool -> Bool
|| NPlies
nPliesEvaluated NPlies -> NPlies -> Bool
forall a. Eq a => a -> a -> Bool
== NPlies
0
			then ShowS
forall a. a -> a
id
			else String -> ShowS
showString String
" (branching-factor" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
Text.ShowList.showsAssociation ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> ShowS
showsDouble (Result x y positionHash criterionValue weightedMean -> Double
forall branchingFactor x y positionHash criterionValue
       weightedMean.
Floating branchingFactor =>
Result x y positionHash criterionValue weightedMean
-> branchingFactor
calculateBranchingFactor Result x y positionHash criterionValue weightedMean
result) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
')'
	 )

-- | Smart constructor.
mkResult :: (
	Enum	x,
	Enum	y,
	Ord	x,
	Ord	y,
	Show	x,
	Show	y
 )
	=> Search.SearchState.SearchState x y positionHash criterionValue weightedMean
	-> [Evaluation.QuantifiedGame.QuantifiedGame x y criterionValue weightedMean]
	-> Component.Move.NPlies
	-> Result x y positionHash criterionValue weightedMean
mkResult :: SearchState x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
-> NPlies
-> Result x y positionHash criterionValue weightedMean
mkResult SearchState x y positionHash criterionValue weightedMean
searchState [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames NPlies
nPliesEvaluated
	| [QuantifiedGame x y criterionValue weightedMean] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames	= Exception -> Result x y positionHash criterionValue weightedMean
forall a e. Exception e => e -> a
Control.Exception.throw (Exception -> Result x y positionHash criterionValue weightedMean)
-> (String -> Exception)
-> String
-> Result x y positionHash criterionValue weightedMean
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkNullDatum (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.mkResult:\tnull quantifiedGames; " (String -> Result x y positionHash criterionValue weightedMean)
-> String -> Result x y positionHash criterionValue weightedMean
forall a b. (a -> b) -> a -> b
$ Game x y -> ShowS
forall a. Show a => a -> ShowS
shows Game x y
game String
"."
	| NPlies
nPliesEvaluated NPlies -> NPlies -> Bool
forall a. Ord a => a -> a -> Bool
< NPlies
0	= Exception -> Result x y positionHash criterionValue weightedMean
forall a e. Exception e => e -> a
Control.Exception.throw (Exception -> Result x y positionHash criterionValue weightedMean)
-> (String -> Exception)
-> String
-> Result x y positionHash criterionValue weightedMean
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkOutOfBounds (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.mkResult:\tnPliesEvaluated=" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NPlies -> ShowS
forall a. Show a => a -> ShowS
shows NPlies
nPliesEvaluated ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" mustn't be negative; " (String -> Result x y positionHash criterionValue weightedMean)
-> String -> Result x y positionHash criterionValue weightedMean
forall a b. (a -> b) -> a -> b
$ Game x y -> ShowS
forall a. Show a => a -> ShowS
shows Game x y
game String
"."
	| Bool
otherwise		= MkResult :: forall x y positionHash criterionValue weightedMean.
SearchState x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
-> NPlies
-> Result x y positionHash criterionValue weightedMean
MkResult {
		getSearchState :: SearchState x y positionHash criterionValue weightedMean
getSearchState		= SearchState x y positionHash criterionValue weightedMean
searchState,
		getQuantifiedGames :: [QuantifiedGame x y criterionValue weightedMean]
getQuantifiedGames	= [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames,
		getNPliesEvaluated :: NPlies
getNPliesEvaluated	= NPlies
nPliesEvaluated
	}
	where
		game :: Game x y
game	= QuantifiedGame x y criterionValue weightedMean -> Game x y
forall x y criterionValue weightedMean.
QuantifiedGame x y criterionValue weightedMean -> Game x y
Evaluation.QuantifiedGame.getGame (QuantifiedGame x y criterionValue weightedMean -> Game x y)
-> (PositionHashQuantifiedGameTree
      x y positionHash criterionValue weightedMean
    -> QuantifiedGame x y criterionValue weightedMean)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> Game x y
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
Evaluation.PositionHashQuantifiedGameTree.getRootQuantifiedGame (PositionHashQuantifiedGameTree
   x y positionHash criterionValue weightedMean
 -> Game x y)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> Game x y
forall a b. (a -> b) -> a -> b
$ SearchState x y positionHash criterionValue weightedMean
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
SearchState x y positionHash criterionValue weightedMean
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
Search.SearchState.getPositionHashQuantifiedGameTree SearchState x y positionHash criterionValue weightedMean
searchState

-- | Initiates the recursive function 'Search.AlphaBeta.negaMax', then unpacks the results.
search :: (
	Enum	x,
	Enum	y,
	Eq	criterionValue,
	Ord	positionHash,
	Ord	x,
	Ord	y,
	Real	weightedMean,
	Show	x,
	Show	y
 )
	=> Input.SearchOptions.SearchDepth	-- ^ How deep down the tree to search.
	-> Search.SearchState.SearchState x y positionHash criterionValue weightedMean
	-> Input.SearchOptions.Reader (Result x y positionHash criterionValue weightedMean)
{-# SPECIALISE search :: Input.SearchOptions.SearchDepth -> Search.SearchState.SearchState T.X T.Y T.PositionHash T.CriterionValue T.WeightedMean -> Input.SearchOptions.Reader (Result T.X T.Y T.PositionHash T.CriterionValue T.WeightedMean) #-}
search :: NPlies
-> SearchState x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
search NPlies
0 SearchState x y positionHash criterionValue weightedMean
_	= Exception
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a e. Exception e => e -> a
Control.Exception.throw (Exception
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> (String -> Exception)
-> String
-> Reader (Result x y positionHash criterionValue weightedMean)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkOutOfBounds (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.search:\t" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
forall a. Show a => a -> ShowS
shows String
Input.SearchOptions.searchDepthTag ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" must be at least " (String
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> String
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a b. (a -> b) -> a -> b
$ NPlies -> ShowS
forall a. Show a => a -> ShowS
shows NPlies
Input.SearchOptions.minimumSearchDepth String
"."
search NPlies
searchDepth SearchState x y positionHash criterionValue weightedMean
searchState
	| Just GameTerminationReason
terminationReason <- Game x y -> Maybe GameTerminationReason
forall x y. Game x y -> Maybe GameTerminationReason
Model.Game.getMaybeTerminationReason Game x y
game	= Exception
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a e. Exception e => e -> a
Control.Exception.throw (Exception
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> (String -> Exception)
-> String
-> Reader (Result x y positionHash criterionValue weightedMean)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkInvalidDatum (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.search:\tthe game has already terminated; " (String
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> String
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a b. (a -> b) -> a -> b
$ GameTerminationReason -> ShowS
forall a. Show a => a -> ShowS
shows GameTerminationReason
terminationReason String
"."
	| Bool
otherwise								= do
		(MaybeRetireAfterNMoves
maybeRetireKillerMovesAfter, MaybeRetireAfterNMoves
maybeRetireTranspositionsAfter)	<- (SearchOptions -> (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves))
-> ReaderT
     SearchOptions
     Identity
     (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves)
forall r (m :: * -> *) a. MonadReader r m => (r -> a) -> m a
Control.Monad.Reader.asks ((SearchOptions
  -> (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves))
 -> ReaderT
      SearchOptions
      Identity
      (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves))
-> (SearchOptions
    -> (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves))
-> ReaderT
     SearchOptions
     Identity
     (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves)
forall a b. (a -> b) -> a -> b
$ SearchOptions -> MaybeRetireAfterNMoves
Input.SearchOptions.getMaybeRetireKillerMovesAfter (SearchOptions -> MaybeRetireAfterNMoves)
-> (SearchOptions -> MaybeRetireAfterNMoves)
-> SearchOptions
-> (MaybeRetireAfterNMoves, MaybeRetireAfterNMoves)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& SearchOptions -> MaybeRetireAfterNMoves
Input.SearchOptions.maybeRetireTranspositionsAfter

		let nPlies :: NPlies
nPlies	= TurnsByLogicalColour (Turn x y) -> NPlies
forall turn. TurnsByLogicalColour turn -> NPlies
State.TurnsByLogicalColour.getNPlies (TurnsByLogicalColour (Turn x y) -> NPlies)
-> TurnsByLogicalColour (Turn x y) -> NPlies
forall a b. (a -> b) -> a -> b
$ Game x y -> TurnsByLogicalColour (Turn x y)
forall x y. Game x y -> TurnsByLogicalColour x y
Model.Game.getTurnsByLogicalColour Game x y
game

		Result x y positionHash criterionValue weightedMean
searchResult	<- NPlies
-> SearchState x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
forall x y criterionValue positionHash weightedMean.
(Enum x, Enum y, Eq criterionValue, Ord positionHash, Ord x, Ord y,
 Real weightedMean, Show x, Show y) =>
NPlies
-> SearchState x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
Search.AlphaBeta.negaMax NPlies
searchDepth (SearchState x y positionHash criterionValue weightedMean
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> SearchState x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a b. (a -> b) -> a -> b
$ NPlies
-> MaybeRetireAfterNMoves
-> MaybeRetireAfterNMoves
-> SearchState x y positionHash criterionValue weightedMean
-> SearchState x y positionHash criterionValue weightedMean
forall a.
MaybeEphemeralData a =>
NPlies
-> MaybeRetireAfterNMoves -> MaybeRetireAfterNMoves -> a -> a
Search.EphemeralData.maybeEuthanise NPlies
nPlies MaybeRetireAfterNMoves
maybeRetireKillerMovesAfter MaybeRetireAfterNMoves
maybeRetireTranspositionsAfter SearchState x y positionHash criterionValue weightedMean
searchState

		case NPlies
-> Result x y positionHash criterionValue weightedMean
-> (DynamicMoveData x y positionHash, [Turn x y], NPlies)
forall x y positionHash criterionValue weightedMean.
NPlies
-> Result x y positionHash criterionValue weightedMean
-> (DynamicMoveData x y positionHash, [Turn x y], NPlies)
Search.AlphaBeta.extractSelectedTurns NPlies
nPlies Result x y positionHash criterionValue weightedMean
searchResult of
			(DynamicMoveData x y positionHash
dynamicMoveData, turns :: [Turn x y]
turns@(Turn x y
turn : [Turn x y]
_), NPlies
nPliesEvaluated)	-> let
				isMatch :: Turn x y
-> NodeLabel x y positionHash criterionValue weightedMean -> Bool
isMatch Turn x y
turn'	= (Turn x y -> Turn x y -> Bool
forall a. Eq a => a -> a -> Bool
== Turn x y
turn') (Turn x y -> Bool)
-> (NodeLabel x y positionHash criterionValue weightedMean
    -> Turn x y)
-> NodeLabel x y positionHash criterionValue weightedMean
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. QuantifiedGame x y criterionValue weightedMean -> Turn x y
forall x y criterionValue weightedMean.
QuantifiedGame x y criterionValue weightedMean -> Turn x y
Evaluation.QuantifiedGame.getLastTurn (QuantifiedGame x y criterionValue weightedMean -> Turn x y)
-> (NodeLabel x y positionHash criterionValue weightedMean
    -> QuantifiedGame x y criterionValue weightedMean)
-> NodeLabel x y positionHash criterionValue weightedMean
-> Turn x y
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NodeLabel x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
NodeLabel x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
Evaluation.PositionHashQuantifiedGameTree.getQuantifiedGame
			 in Result x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
forall (m :: * -> *) a. Monad m => a -> m a
return {-to Reader-monad-} (Result x y positionHash criterionValue weightedMean
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> Result x y positionHash criterionValue weightedMean
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a b. (a -> b) -> a -> b
$ SearchState x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
-> NPlies
-> Result x y positionHash criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
(Enum x, Enum y, Ord x, Ord y, Show x, Show y) =>
SearchState x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
-> NPlies
-> Result x y positionHash criterionValue weightedMean
mkResult (
				PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> DynamicMoveData x y positionHash
-> SearchState x y positionHash criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> DynamicMoveData x y positionHash
-> SearchState x y positionHash criterionValue weightedMean
Search.SearchState.mkSearchState (
					PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> Maybe
     (PositionHashQuantifiedGameTree
        x y positionHash criterionValue weightedMean)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall a. a -> Maybe a -> a
Data.Maybe.fromMaybe (
						Exception
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall a e. Exception e => e -> a
Control.Exception.throw (Exception
 -> PositionHashQuantifiedGameTree
      x y positionHash criterionValue weightedMean)
-> (String -> Exception)
-> String
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkIncompatibleData (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.search:\tBishBosh.Evaluation.PositionHashQuantifiedGameTree.reduce failed; " (String
 -> PositionHashQuantifiedGameTree
      x y positionHash criterionValue weightedMean)
-> String
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall a b. (a -> b) -> a -> b
$ Turn x y -> ShowS
forall a. Show a => a -> ShowS
shows Turn x y
turn String
"."
					) (Maybe
   (PositionHashQuantifiedGameTree
      x y positionHash criterionValue weightedMean)
 -> PositionHashQuantifiedGameTree
      x y positionHash criterionValue weightedMean)
-> Maybe
     (PositionHashQuantifiedGameTree
        x y positionHash criterionValue weightedMean)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall a b. (a -> b) -> a -> b
$ IsMatch (NodeLabel x y positionHash criterionValue weightedMean)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> Maybe
     (PositionHashQuantifiedGameTree
        x y positionHash criterionValue weightedMean)
forall x y positionHash criterionValue weightedMean.
IsMatch (NodeLabel x y positionHash criterionValue weightedMean)
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> Maybe
     (PositionHashQuantifiedGameTree
        x y positionHash criterionValue weightedMean)
Evaluation.PositionHashQuantifiedGameTree.reduce (Turn x y
-> IsMatch (NodeLabel x y positionHash criterionValue weightedMean)
forall x y positionHash criterionValue weightedMean.
(Eq x, Eq y) =>
Turn x y
-> NodeLabel x y positionHash criterionValue weightedMean -> Bool
isMatch Turn x y
turn) PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
positionHashQuantifiedGameTree
				) DynamicMoveData x y positionHash
dynamicMoveData
			 ) (
				(NodeLabel x y positionHash criterionValue weightedMean
 -> QuantifiedGame x y criterionValue weightedMean)
-> [NodeLabel x y positionHash criterionValue weightedMean]
-> [QuantifiedGame x y criterionValue weightedMean]
forall a b. (a -> b) -> [a] -> [b]
map NodeLabel x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
NodeLabel x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
Evaluation.PositionHashQuantifiedGameTree.getQuantifiedGame ([NodeLabel x y positionHash criterionValue weightedMean]
 -> [QuantifiedGame x y criterionValue weightedMean])
-> (Maybe [NodeLabel x y positionHash criterionValue weightedMean]
    -> [NodeLabel x y positionHash criterionValue weightedMean])
-> Maybe [NodeLabel x y positionHash criterionValue weightedMean]
-> [QuantifiedGame x y criterionValue weightedMean]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [NodeLabel x y positionHash criterionValue weightedMean]
-> Maybe [NodeLabel x y positionHash criterionValue weightedMean]
-> [NodeLabel x y positionHash criterionValue weightedMean]
forall a. a -> Maybe a -> a
Data.Maybe.fromMaybe (
					Exception
-> [NodeLabel x y positionHash criterionValue weightedMean]
forall a e. Exception e => e -> a
Control.Exception.throw (Exception
 -> [NodeLabel x y positionHash criterionValue weightedMean])
-> (String -> Exception)
-> String
-> [NodeLabel x y positionHash criterionValue weightedMean]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Exception
Data.Exception.mkSearchFailure (String -> Exception) -> ShowS -> String -> Exception
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
"BishBosh.Search.Search.search:\tEvaluation.PositionHashQuantifiedGameTree.traceRoute failed; " (String
 -> [NodeLabel x y positionHash criterionValue weightedMean])
-> String
-> [NodeLabel x y positionHash criterionValue weightedMean]
forall a b. (a -> b) -> a -> b
$ [Turn x y] -> ShowS
forall a. Show a => a -> ShowS
shows [Turn x y]
turns String
"."
				) (Maybe [NodeLabel x y positionHash criterionValue weightedMean]
 -> [QuantifiedGame x y criterionValue weightedMean])
-> Maybe [NodeLabel x y positionHash criterionValue weightedMean]
-> [QuantifiedGame x y criterionValue weightedMean]
forall a b. (a -> b) -> a -> b
$ (Turn x y
 -> IsMatch
      (NodeLabel x y positionHash criterionValue weightedMean))
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> [Turn x y]
-> Maybe [NodeLabel x y positionHash criterionValue weightedMean]
forall x y positionHash criterionValue weightedMean.
(Turn x y
 -> IsMatch
      (NodeLabel x y positionHash criterionValue weightedMean))
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
-> [Turn x y]
-> Maybe [NodeLabel x y positionHash criterionValue weightedMean]
Evaluation.PositionHashQuantifiedGameTree.traceRoute Turn x y
-> IsMatch (NodeLabel x y positionHash criterionValue weightedMean)
forall x y positionHash criterionValue weightedMean.
(Eq x, Eq y) =>
Turn x y
-> NodeLabel x y positionHash criterionValue weightedMean -> Bool
isMatch PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
positionHashQuantifiedGameTree [Turn x y]
turns
			 ) NPlies
nPliesEvaluated
			(DynamicMoveData x y positionHash, [Turn x y], NPlies)
_							-> Exception
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a e. Exception e => e -> a
Control.Exception.throw (Exception
 -> Reader (Result x y positionHash criterionValue weightedMean))
-> Exception
-> Reader (Result x y positionHash criterionValue weightedMean)
forall a b. (a -> b) -> a -> b
$ String -> Exception
Data.Exception.mkNullDatum String
"BishBosh.Search.Search.search:\tzero turns selected."
	where
		positionHashQuantifiedGameTree :: PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
positionHashQuantifiedGameTree	= SearchState x y positionHash criterionValue weightedMean
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
SearchState x y positionHash criterionValue weightedMean
-> PositionHashQuantifiedGameTree
     x y positionHash criterionValue weightedMean
Search.SearchState.getPositionHashQuantifiedGameTree SearchState x y positionHash criterionValue weightedMean
searchState
		game :: Game x y
game				= QuantifiedGame x y criterionValue weightedMean -> Game x y
forall x y criterionValue weightedMean.
QuantifiedGame x y criterionValue weightedMean -> Game x y
Evaluation.QuantifiedGame.getGame (QuantifiedGame x y criterionValue weightedMean -> Game x y)
-> QuantifiedGame x y criterionValue weightedMean -> Game x y
forall a b. (a -> b) -> a -> b
$ PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
forall x y positionHash criterionValue weightedMean.
PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
-> QuantifiedGame x y criterionValue weightedMean
Evaluation.PositionHashQuantifiedGameTree.getRootQuantifiedGame PositionHashQuantifiedGameTree
  x y positionHash criterionValue weightedMean
positionHashQuantifiedGameTree

-- | Calculate the geometric-mean of the number of plies evaluated at each node.
calculateBranchingFactor :: Floating branchingFactor => Result x y positionHash criterionValue weightedMean -> branchingFactor
calculateBranchingFactor :: Result x y positionHash criterionValue weightedMean
-> branchingFactor
calculateBranchingFactor MkResult {
	getQuantifiedGames :: forall x y positionHash criterionValue weightedMean.
Result x y positionHash criterionValue weightedMean
-> [QuantifiedGame x y criterionValue weightedMean]
getQuantifiedGames	= [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames,
	getNPliesEvaluated :: forall x y positionHash criterionValue weightedMean.
Result x y positionHash criterionValue weightedMean -> NPlies
getNPliesEvaluated	= NPlies
nPliesEvaluated
}
	| [QuantifiedGame x y criterionValue weightedMean] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames	= Exception -> branchingFactor
forall a e. Exception e => e -> a
Control.Exception.throw (Exception -> branchingFactor) -> Exception -> branchingFactor
forall a b. (a -> b) -> a -> b
$ String -> Exception
Data.Exception.mkNullDatum String
"BishBosh.Search.Search.calculateBranchingFactor:\tnull quantifiedGames."
	| NPlies
nPliesEvaluated NPlies -> NPlies -> Bool
forall a. Eq a => a -> a -> Bool
== NPlies
0	= Exception -> branchingFactor
forall a e. Exception e => e -> a
Control.Exception.throw (Exception -> branchingFactor) -> Exception -> branchingFactor
forall a b. (a -> b) -> a -> b
$ String -> Exception
Data.Exception.mkOutOfBounds String
"BishBosh.Search.Search.calculateBranchingFactor:\tzero plies analysed."
	| Bool
otherwise		= NPlies -> branchingFactor
forall a b. (Integral a, Num b) => a -> b
fromIntegral NPlies
nPliesEvaluated branchingFactor -> branchingFactor -> branchingFactor
forall a. Floating a => a -> a -> a
** branchingFactor -> branchingFactor
forall a. Fractional a => a -> a
recip (
		NPlies -> branchingFactor
forall a b. (Integral a, Num b) => a -> b
fromIntegral (NPlies -> branchingFactor) -> NPlies -> branchingFactor
forall a b. (a -> b) -> a -> b
$ [QuantifiedGame x y criterionValue weightedMean] -> NPlies
forall (t :: * -> *) a. Foldable t => t a -> NPlies
length [QuantifiedGame x y criterionValue weightedMean]
quantifiedGames	-- The search-depth.
	)