# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find solutions to perfectly played combinatorial games

Contributed by:
Brad Klee and Andrea Li

ResourceFunction["AlphaBetaSearch"][ returns a partial game graph for sufficiently determining the winner of a two player game. | |

ResourceFunction["AlphaBetaSearch"][ allows ordered searching through the sort function | |

ResourceFunction["AlphaBetaSearch"][ allows for games with more than two players by setting goals. |

Function *iterator* takes a game state as input, and outputs all valid next states.

Expression *init* is the unique starting configuration of the game.

Function *player* takes a state as input and returns the player whose turn it is. The default players are and .

The function *result* takes a terminal game state as input and returns a value for the position. The default values are assumed to be 1 when wins, -1 when wins and 0 for a draw.

Function *heuristic* can be used to sort potential next game states: *next*= *heuristic*[*iterator*[*state*]]. Most useful heuristics will be of the form *heuristic*=Function[SortBy[#,…]]. For statistical testing *heuristic*=RandomSample can also be useful.

Association *goals* links player symbols to game state values and describes how each player chooses a best next state. By default, player chooses by Max, and player chooses by Min. The form for each item of *goals* is *player *→ 〈| "Win" → *val*, "Choose" → *fun* |〉, which assumes that function *fun* when applied to a list of game state values will choose *val* if it occurs in the list.

AlphaBetaSearch accepts two options Method and PerformanceGoal.

Default Method "Loop" has extra cancellations, but alternative method "Recursive" is competitively performant.

Setting PerformanceGoal to "Quality" certifies the result with a post-check of the closure conditions.

The result of ResourceFunction["AlphaBetaSearch"] is always a subgraph of ResourceFunction["FixedPointGraph"][*iterator*, {*init*}].

The result of ResourceFunction["AlphaBetaSearch"] always satisfies a closure condition as shown in Properties and Relations.

A valid result is only guaranteed for a directed acyclic *iterator*. If *iterator* finds loops in the game graph, the algorithm can not be expected to succeed.

Solve a two-player nim game with three heaps:

In[1]:= |

Out[1]= |

Use the "nim-sum equals zero" heuristic to obtain a smaller solution:

In[2]:= |

Out[2]= |

Highlight solutions on the entire game graph:

In[3]:= |

Out[3]= |

Check that both solutions predict the same winner:

In[4]:= |

Out[4]= |

Find a solution to the independence game on a small RandomGraph:

In[5]:= |

Out[5]= |

Decorate the graph to see which branch would follow from an imperfect choice:

In[6]:= |

Out[6]= |

Define win conditions and choice functions for a three-player game:

In[7]:= |

Out[7]= |

One solution for a three-player vertex deletion game on a small RandomGraph:

In[8]:= |

Out[8]= |

Decorate the graph to see who wins and how:

In[9]:= |

Out[9]= |

Obtain a validated result for a simple arithmetic game:

In[10]:= |

Out[10]= |

Obtain solutions for a nim game using two different methods:

In[11]:= |

Out[11]= |

The solutions are different:

In[12]:= |

Out[12]= |

But both solutions predict the same winner by perfect play:

In[13]:= |

Out[13]= |

Compute a solution:

In[14]:= |

Out[14]= |

Expand one extra layer of vertices around the solution:

In[15]:= |

Out[15]= |

Losing positions must not have missing next steps:

In[16]:= |

Out[16]= |

Missing next steps must branch from winning positions:

In[17]:= |

Out[17]= |

These checks can be computed automatically:

In[18]:= |

Out[18]= |

A solution to the game tic-tac-toe:

In[19]:= |

Out[19]= |

Check that perfect play leads to a draw:

In[20]:= |

Out[20]= |

Wolfram Language 13.0 (December 2021) or above

- 1.0.0 – 24 May 2024

This work is licensed under a Creative Commons Attribution 4.0 International License