DecisionNode::traverseGameTree() - Code Metrics - Inspection of "WiP: Larger search space" - LucidTaZ/minimax - Measure and Improve Code Quality continuously with Scrutinizer

Test Failed

Pull Request — master (#7)

by Thijs

created 2017-07-26 18:10 UTC

DecisionNode::traverseGameTree() C

↳ Parent: DecisionNode

Complexity

Conditions	7
Paths	4

Size

Total Lines	30
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	30
rs	6.7272
c	0
b	0
f	0
cc	7
eloc	17
nc	4
nop	0

<?php

namespace lucidtaz\minimax\engine;

use lucidtaz\minimax\game\GameState;
use lucidtaz\minimax\game\Player;

/**
 * Node in the decision search tree
 * An object of this class can be queried for its ideal decision (and according
 * score) by calling the decide() method. It will recursively construct child
 * nodes and evaluate them using that method as well.
 */
class DecisionNode
{
    /**
     * @var Player The player to optimize for.
     */
    private $objectivePlayer;

    /**
     * @var GameState The current GameState to base future decisions on.
     */
    private $state;

    /**
     * @var int Limit on how deep we can continue to search, recursion limiter.
     */
    private $depthLeft;

    /**
     * @var NodeType Whether we are a min-node or a max-node. This enables the
     * caller to select either the most favorable or the least favorable
     * outcome.
     */
    private $type;

    /**
     * @var AlphaBeta Constraints for alpha-beta pruning
     */
    private $alphaBeta;

    /**
     * @param Player $objectivePlayer The Player to optimize for
     * @param GameState $state Current GameState to base decisions on
     * @param int $depthLeft Recursion limiter
     * @param NodeType $type Signifies whether to minimize or maximize the score
     * @param AlphaBeta $alphaBeta Range of potential scores to check
     */
    public function __construct(Player $objectivePlayer, GameState $state, int $depthLeft, NodeType $type, AlphaBeta $alphaBeta)
    {
        $this->objectivePlayer = $objectivePlayer;
        $this->state = $state;
        $this->depthLeft = $depthLeft;
        $this->type = $type;
        $this->alphaBeta = $alphaBeta;
    }

    /**
     * Determine the ideal move for this node
     * This means either the best or the worst possible outcome for the
     * objective player, based on who is actually playing. (If the objective
     * player is currently playing, we take the best outcome, otherwise we take
     * the worst. This reflects that the opponent also plays optimally.)
     */
    public function traverseGameTree(): TraversalResult
    {
        if ($this->depthLeft == 0) {
            return TraversalResult::withoutMove($this->makeLeafEvaluation());
        }

        /* @var $possibleMoves GameState[] */
        $possibleMoves = $this->state->getPossibleMoves();
        if (empty($possibleMoves)) {
            return TraversalResult::withoutMove($this->makeLeafEvaluation());
        }

        $idealMove = null;
        $idealMoveResult = null;
        foreach ($possibleMoves as $move) {
            if (!$this->alphaBeta->isPositiveRange()) {
                // Subtree became fruitless, return to caller asap
                break;
            }

            $moveResult = $this->getChildResult($move);
            $this->alphaBeta->update($moveResult->evaluation, $this->type);
            if ($idealMoveResult === null || $this->isIdealOver($moveResult->evaluation, $idealMoveResult->evaluation)) {
                $idealMove = $move;
                $idealMoveResult = $moveResult;
            }
        }

        return TraversalResult::create($idealMove, $idealMoveResult->evaluation);
/** @return stdClass|null */
function mayReturnNull() { }

function doesNotAcceptNull(stdClass $x) { }

// With potential error.
function withoutCheck() {
    $x = mayReturnNull();
    doesNotAcceptNull($x); // Potential error here.
}

// Safe - Alternative 1
function withCheck1() {
    $x = mayReturnNull();
    if ( ! $x instanceof stdClass) {
        throw new \LogicException('$x must be defined.');
    }
    doesNotAcceptNull($x);
}

// Safe - Alternative 2
function withCheck2() {
    $x = mayReturnNull();
    if ($x instanceof stdClass) {
        doesNotAcceptNull($x);
    }
}
    }

    /**
     * Formulate the evaluation, this node being a leaf node
     */
    private function makeLeafEvaluation(): Evaluation
    {
        $result = new Evaluation();
        $result->age = $this->depthLeft;
        $result->score = $this->state->evaluateScore($this->objectivePlayer);
        return $result;
    }

    /**
     * Recursively evaluate a child decision
     * Apply a move and evaluate the outcome
     * @param GameState $stateAfterMove The GameState that was created as a
     * result of a possible move.
     */
    private function getChildResult(GameState $stateAfterMove): TraversalResult
    {
        $nextPlayerIsFriendly = $stateAfterMove->getNextPlayer()->isFriendsWith($this->objectivePlayer);
        $nextDecisionPoint = new static(
            $this->objectivePlayer,
            $stateAfterMove,
            $this->depthLeft - 1,
            $nextPlayerIsFriendly ? NodeType::MAX() : NodeType::MIN(),
            clone $this->alphaBeta
        );
        return $nextDecisionPoint->traverseGameTree();
    }

    /**
     * Compare two evaluations
     * The meaning of "best" is decided by the "ideal" member variable
     * comparator
     */
    private function isIdealOver(Evaluation $a, Evaluation $b): bool
    {
        $ideal = $this->type == NodeType::MIN()
            ? Evaluation::getWorstComparator()
            : Evaluation::getBestComparator();
        $idealEvaluationResult = $ideal($a, $b);
        return $idealEvaluationResult > 0;
    }
}


1			<?php
2
3			namespace lucidtaz\minimax\engine;
4
5			use lucidtaz\minimax\game\GameState;
6			use lucidtaz\minimax\game\Player;
7
8			/**
9			* Node in the decision search tree
10			* An object of this class can be queried for its ideal decision (and according
11			* score) by calling the decide() method. It will recursively construct child
12			* nodes and evaluate them using that method as well.
13			*/
14			class DecisionNode
15			{
16			/**
17			* @var Player The player to optimize for.
18			*/
19			private $objectivePlayer;
20
21			/**
22			* @var GameState The current GameState to base future decisions on.
23			*/
24			private $state;
25
26			/**
27			* @var int Limit on how deep we can continue to search, recursion limiter.
28			*/
29			private $depthLeft;
30
31			/**
32			* @var NodeType Whether we are a min-node or a max-node. This enables the
33			* caller to select either the most favorable or the least favorable
34			* outcome.
35			*/
36			private $type;
37
38			/**
39			* @var AlphaBeta Constraints for alpha-beta pruning
40			*/
41			private $alphaBeta;
42
43			/**
44			* @param Player $objectivePlayer The Player to optimize for
45			* @param GameState $state Current GameState to base decisions on
46			* @param int $depthLeft Recursion limiter
47			* @param NodeType $type Signifies whether to minimize or maximize the score
48			* @param AlphaBeta $alphaBeta Range of potential scores to check
49			*/
50			public function __construct(Player $objectivePlayer, GameState $state, int $depthLeft, NodeType $type, AlphaBeta $alphaBeta)
51			{
52			$this->objectivePlayer = $objectivePlayer;
53			$this->state = $state;
54			$this->depthLeft = $depthLeft;
55			$this->type = $type;
56			$this->alphaBeta = $alphaBeta;
57			}
58
59			/**
60			* Determine the ideal move for this node
61			* This means either the best or the worst possible outcome for the
62			* objective player, based on who is actually playing. (If the objective
63			* player is currently playing, we take the best outcome, otherwise we take
64			* the worst. This reflects that the opponent also plays optimally.)
65			*/
66			public function traverseGameTree(): TraversalResult
67			{
68			if ($this->depthLeft == 0) {
69			return TraversalResult::withoutMove($this->makeLeafEvaluation());
70			}
71
72			/* @var $possibleMoves GameState[] */
73			$possibleMoves = $this->state->getPossibleMoves();
74			if (empty($possibleMoves)) {
75			return TraversalResult::withoutMove($this->makeLeafEvaluation());
76			}
77
78			$idealMove = null;
79			$idealMoveResult = null;
80			foreach ($possibleMoves as $move) {
81			if (!$this->alphaBeta->isPositiveRange()) {
82			// Subtree became fruitless, return to caller asap
83			break;
84			}
85
86			$moveResult = $this->getChildResult($move);
87			$this->alphaBeta->update($moveResult->evaluation, $this->type);
88			if ($idealMoveResult === null \|\| $this->isIdealOver($moveResult->evaluation, $idealMoveResult->evaluation)) {
89			$idealMove = $move;
90			$idealMoveResult = $moveResult;
91			}
92			}
93
94			return TraversalResult::create($idealMove, $idealMoveResult->evaluation);
			0 ignored issues – show Bug introduced 2017-07-26 18:12 UTC by Report Bug Copy Issue Report It seems like `$idealMove` defined by `null` on line `78` can be `null`; however, `lucidtaz\minimax\engine\TraversalResult::create()` does not accept `null`, maybe add an additional type check? Unless you are absolutely sure that the expression can never be null because of other conditions, we strongly recommend to add an additional type check to your code: /** @return stdClass\|null */ function mayReturnNull() { } function doesNotAcceptNull(stdClass $x) { } // With potential error. function withoutCheck() { $x = mayReturnNull(); doesNotAcceptNull($x); // Potential error here. } // Safe - Alternative 1 function withCheck1() { $x = mayReturnNull(); if ( ! $x instanceof stdClass) { throw new \LogicException('$x must be defined.'); } doesNotAcceptNull($x); } // Safe - Alternative 2 function withCheck2() { $x = mayReturnNull(); if ($x instanceof stdClass) { doesNotAcceptNull($x); } } Loading history...
95			}
96
97			/**
98			* Formulate the evaluation, this node being a leaf node
99			*/
100			private function makeLeafEvaluation(): Evaluation
101			{
102			$result = new Evaluation();
103			$result->age = $this->depthLeft;
104			$result->score = $this->state->evaluateScore($this->objectivePlayer);
105			return $result;
106			}
107
108			/**
109			* Recursively evaluate a child decision
110			* Apply a move and evaluate the outcome
111			* @param GameState $stateAfterMove The GameState that was created as a
112			* result of a possible move.
113			*/
114			private function getChildResult(GameState $stateAfterMove): TraversalResult
115			{
116			$nextPlayerIsFriendly = $stateAfterMove->getNextPlayer()->isFriendsWith($this->objectivePlayer);
117			$nextDecisionPoint = new static(
118			$this->objectivePlayer,
119			$stateAfterMove,
120			$this->depthLeft - 1,
121			$nextPlayerIsFriendly ? NodeType::MAX() : NodeType::MIN(),
122			clone $this->alphaBeta
123			);
124			return $nextDecisionPoint->traverseGameTree();
125			}
126
127			/**
128			* Compare two evaluations
129			* The meaning of "best" is decided by the "ideal" member variable
130			* comparator
131			*/
132			private function isIdealOver(Evaluation $a, Evaluation $b): bool
133			{
134			$ideal = $this->type == NodeType::MIN()
135			? Evaluation::getWorstComparator()
136			: Evaluation::getBestComparator();
137			$idealEvaluationResult = $ideal($a, $b);
138			return $idealEvaluationResult > 0;
139			}
140			}
141

LucidTaZ / minimax

Pull Request — master (#7)

DecisionNode::traverseGameTree() C

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like