An official website of the United States government
This paper proposes a new mixed-integer programming (MIP) formulation to optimize split rule selection in the decision tree induction process and develops an efficient search algorithm that is able to solve practical instances of the MIP model faster than commercial solvers. The formulation is novel for it directly maximizes the Gini reduction, an effective split selection criterion that has never been modeled in a mathematical program for its nonconvexity. The proposed approach differs from other optimal classification tree models in that it does not attempt to optimize the whole tree; therefore, the flexibility of the recursive partitioning scheme is retained, and the optimization model is more amenable. The approach is implemented in an open-source R package named bsnsing. Benchmarking experiments on 75 open data sets suggest that bsnsing trees are the most capable of discriminating new cases compared with trees trained by other decision tree codes including the rpart, C50, party, and tree packages in R. Compared with other optimal decision tree packages, including DL8.5, OSDT, GOSDT, and indirectly more, bsnsing stands out in its training speed, ease of use, and broader applicability without losing in prediction accuracy. History: Accepted by RamRamesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by the National Science Foundation Division of Civil, MechanicalandManufacturing Innovation [Grant 1944068]. Supplemental Material: Data are available at https://doi.org/10.1287/ijoc.2022.1225 .
more »
« less
A hybrid search agent in pommerman
In this paper, we explore the possibility of search-based agents in games with resource-intensive forward models. We implemented a player agent in the Pommerman framework and put it against the baseline agent to measure its performance. We implemented a heuristic agent and improved it by enabling depth-limited tree search in specific gameplay moments. We also compared different node selection methods during depth-limited tree search. Our result shows that depth-limited tree search is still viable when presented with inefficient forward models and exploitation-driven selection method is the most efficient in this specific domain.
more »
« less
- Award ID(s):
- 1717324
- PAR ID:
- 10132605
- Date Published:
- Journal Name:
- FDG '18: Proceedings of the 13th International Conference on the Foundations of Digital Game
- Page Range / eLocation ID:
- 1 to 4
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Pior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10 ⊆ NC^11). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.more » « less
-
Bonchi, Filippo; Puglisi, Simon J. (Ed.)We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL ∩ co-UL), which is contained in AC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10 ⊆ NC^11). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.more » « less
-
Endriss, U.; Nowé, A.; Dignum, F.; Lomuscio, A. (Ed.)Sabre is a narrative planner—a centralized, omniscient decision maker that solves a multi-agent storytelling problem. The planner has an author goal it must achieve, but every action taken by an agent must make sense according to that agent’s individual intentions and limited, possibly wrong beliefs. This paper describes the implementation of Sabre, which supports a rich action syntax and imposes no arbitrary limit on the depth of theory of mind. We present a search procedure for generating plans that achieve the author goals while ensuring all agent actions are explained, and we report the system’s performance on several narrative planning benchmark problems.more » « less
-
Thue, David; Ware, Stephen G. (Ed.)Sabre is a narrative planner—a centralized, omniscient decision maker that solves a multi-agent storytelling problem. The planner has an author goal it must achieve, but every action taken by an agent must make sense according to that agent’s individual intentions and limited, possibly wrong beliefs. This paper describes the implementation of Sabre, which supports a rich action syntax and imposes no arbitrary limit on the depth of theory of mind. We present a search procedure for generating plans that achieve the author goals while ensuring all agent actions are explained, and we report the system’s performance on several narrative planning benchmark problems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3235765.3235812
