Calculating device, calculating system, and computer product

A calculating device comprising:

• a memory apparatus that stores a search space specified with a state set and an action set, and a presumed minimax having an arbitrary value;
• and
• a processor configured to:
• sequentially select an action from the action set in the search space stored in the memory apparatus, and sequentially select each state in the state set corresponding to the selected action;
• acquire and store into the search space, an evaluation value of the combination of the selected state and the selected action;
• identify a maximum evaluation value among the evaluation values acquired for each of the selected actions;
• select an unselected state for the selected action when an evaluation value of the combination of the selected action and the selected state is at most the presumed minimax, or terminate selection of an unselected state for the selected action, and select an unselected action when an evaluation value of the selected action and the selected state is greater than the presumed minimax;
• determine as a minimax candidate, a lowest evaluation value among the maximum evaluation values identified for an action for which selection has not been terminated;
• judge whether termination of selection has occurred for all the actions when no action to be selected is present;
• determine as a minimax, the minimax candidate determined for an action for which selection has not been terminated when any action for which state selection has not been terminated is present, or else enlarge the presumed minimax and retry the calculation;
• and
• output the action for which the minimax has been determined.

A calculating system comprising:

• a master calculating device having a first memory apparatus that has a memory area of a maximum evaluation value candidate and a maximum evaluation value for each action in a given action set;
• and
• a slave calculating device having a second memory apparatus that stores a search space specified with an action set and a state set, wherein
• the slave calculating device includes a processor configured to:
• receive from the master calculating device a start position specifying an action and a state among the actions and the states in the search space stored in the second memory apparatus and a presumed minimax having an arbitrary value,
• select actions sequentially from an action specified by the received start position and select states sequentially from a state specified by the start position for the selected action,
• acquire an evaluation value of the combination of the selected state and the selected action,
• identify a maximum evaluation value among the evaluation values acquired for the selected actions when the evaluation values concerning all the states in the state set are acquired,
• select an unselected state for a currently selected action when an evaluation value of the currently selected action and state is at most the presumed minimax, or terminate selection of an unselected state for the currently selected action, and select an unselected action when an evaluation value of the currently selected action and state is greater than the presumed minimax,
• identify, as a maximum evaluation value candidate for the currently selected action, a maximum values among those evaluation values acquired for the selected action when state selection of the selected action is terminated, and
• transmit to the master calculating device, a maximum evaluation value or the maximum evaluation value candidate identified for the currently selected action, and further transmit to the master calculating device, evaluation completion notification when at least any one among a maximum evaluation value of an action and the maximum evaluation value candidates of the actions are acquired,
• the master calculating device includes a processor configured to:
• set a start position in the search space, specified by an action and a state, and a presumed minimax having an arbitrary value that differs for each slave calculating device, and to further set a presumed minimax lower limit that is a lower limit of a presumed minimax using by the slave calculating devices and a presumed minimax upper limit that is an upper limit of the presumed minimax,
• deliver to each of the slave calculating devices, the respective start position and the respective presumed minimax set for the slave calculating device,
• write into a memory area of a corresponding action in the first memory apparatus, any one among a maximum evaluation value and a maximum evaluation value candidate transmitted from each of the slave calculating devices,
• detect evaluation completion notification from any one of the slave calculating devices,
• update upon detecting evaluation completion notification, the presumed minimax lower limit to the smallest value among the maximum evaluation value candidates stored in the first memory apparatus and update the presumed minimax upper limit to the smallest value among the maximum evaluation values stored in the first memory apparatus,
• determine whether the updated presumed minimax lower limit is greater than the updated presumed minimax upper limit,
• determine the updated presumed minimax upper limit as a minimax, upon determining that the presumed minimax lower limit is larger, and
• output the action having the determined minimax.

A non-transitory, computer-readable recording medium storing a search program that causes a calculating device having a memory apparatus that stores an action set including a plurality of actions and a state set including a plurality of states corresponding to the actions included in the action set, to execute a process comprising:

• selecting an action from the action set and selecting from the state set, a state corresponding to the selected action;
• acquiring an evaluation value by evaluating the combination of the selected action and the selected state;
• identifying for each selected action, a lowest evaluation value that is lowest among acquired evaluation values;
• determining the lowest evaluation value of evaluation values of all the states selected for each action as a minimax candidate, and determining, as a minimax, an evaluation value that is highest among the lowest evaluation values corresponding to the actions;
• at each time an evaluation value is acquired for a combination of a state and an action after the minimax candidate is determined, comparing the acquired evaluation value and the minimax candidate, and terminating selection of a state corresponding to the action when the evaluation value is lower than the minimax candidate and to select an action from unselected actions included in the action set;
• and
• outputting an action corresponding to the determined minimax.

A non-transitory, computer-readable recording medium storing a search program that causes a calculating device having a first memory apparatus that has a memory area of a maximum evaluation value candidate and a maximum evaluation value for each action in a given action set, to execute a process comprising:

• setting a start position in the search space, specified by an action and a state, and a presumed minimax having an arbitrary value that differs for each slave calculating device, and further setting a presumed minimax lower limit that is a lower limit of a presumed minimax of the slave calculating devices and a presumed minimax upper limit that is an upper limit of the presumed minimax,
• delivering to each of the slave calculating devices, the respective start position and the respective presumed minimax set for the slave calculating device,
• writing into a memory area of a corresponding action in the first memory apparatus, any one among a maximum evaluation value and a maximum evaluation value candidate transmitted from each of the slave calculating devices,
• detecting evaluation completion notification from any one of the slave calculating devices,
• updating upon detecting evaluation completion notification, the presumed minimax lower limit to the smallest value among the maximum evaluation value candidates stored in the memory apparatus and updating the presumed minimax upper limit to the smallest value among the maximum evaluation values stored in the first memory apparatus,
• determining whether the updated presumed minimax lower limit is greater than the updated presumed minimax upper limit,
• determining the updated presumed minimax upper limit as a minimax, upon determining that the presumed minimax lower limit is larger, and
• outputting the action having the determined minimax.