fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. import java.util.ArrayList;
  8.  
  9. class Node {
  10.  
  11.     boolean isMin;
  12.     boolean isMax;
  13.     boolean isTerminal;
  14.     int value;
  15.     int depth;
  16.     ArrayList <Node> children = new ArrayList <Node>();
  17.  
  18. }
  19. class AlphaBeta {
  20.  
  21.  
  22.     static Node alphaBetaSearch(Node state){
  23.  
  24.         state.value = max_value(state,-99999,99999);
  25.  
  26.         System.out.println(state.value);
  27.  
  28.     return null;
  29.     } 
  30.  
  31.  
  32.     static int max_value(Node state, int alpha, int beta){
  33.  
  34.  
  35.         if (state.isTerminal){
  36.             System.out.println("visited leaf with value " + state.value);
  37.             return state.value;
  38.         }
  39.  
  40.         state.value = -99999;
  41.  
  42.         for (Node a: state.children){
  43.  
  44.             state.value = Math.max(state.value , min_value(a, alpha, beta));
  45.             if (state.value >= beta){
  46.  
  47.                 return state.value;                
  48.             }
  49.             alpha = Math.max(alpha, state.value);
  50.         }
  51.         return state.value;
  52.     }
  53.  
  54.     static int min_value(Node state, int alpha, int beta){
  55.  
  56.  
  57.         if (state.isTerminal) 
  58.             return state.value;
  59.  
  60.         state.value = 99999;
  61.  
  62.         for (Node a: state.children){
  63.  
  64.             state.value = Math.min(state.value, max_value(a, alpha, beta));
  65.             if (state.value >= alpha){
  66.  
  67.                 return state.value;
  68.  
  69.             }
  70.             beta = Math.min(beta, state.value);
  71.         }
  72.         return state.value;
  73.     }
  74.  
  75.  
  76.     public static void main(String[] args) {
  77.  
  78.         Node t1 = new Node();
  79. //            t1.value = 4; 
  80.             t1.value = 3;
  81.             t1.depth =2;
  82.             t1.isTerminal = true;
  83.  
  84.         Node t2 = new Node();
  85. //             t2.value = 8;
  86.              t2.value = 12;
  87.              t2.depth=2;
  88.              t2.isTerminal= true;
  89.  
  90.         Node t3 = new Node();
  91.             // t3.value = 7;
  92.              t3.value = 8;
  93.              t3.depth=2;
  94.              t3.isTerminal= true;
  95.  
  96.         Node min1 = new Node();
  97.              min1.isTerminal=false;
  98.              min1.depth=1;
  99.              min1.isMin=true;
  100.              min1.children.add(t1);
  101.              min1.children.add(t2);
  102.              min1.children.add(t3);
  103.  
  104.         Node t4 = new Node();
  105. //            t4.value = 5;
  106.             t4.value = 2;
  107.             t4.depth =2;
  108.             t4.isTerminal = true;
  109.  
  110.         Node t5 = new Node();
  111.              //t5.value = 2;
  112.              t5.value =3;
  113.              t5.depth=2;
  114.              t5.isTerminal= true;
  115.  
  116.         Node t6 = new Node();
  117. //             t6.value = 1;
  118.              t6.value=9;
  119.              t6.depth=2;
  120.              t6.isTerminal= true;
  121.  
  122.         Node min2 = new Node();
  123.              min2.isMin=true;
  124.              min2.isTerminal=false;
  125.              min2.depth=1;
  126.              min2.children.add(t4);
  127.              min2.children.add(t5);
  128.              min2.children.add(t6);  
  129.  
  130.  
  131.         Node t7 = new Node();
  132. //             t7.value = 1; 
  133.              t7.value=14;
  134.              t7.depth =2;
  135.              t7.isTerminal = true;
  136.  
  137.         Node t8 = new Node();
  138. //             t8.value = 6;
  139.              t8.value=1;
  140.              t8.depth=2;
  141.              t8.isTerminal= true;
  142.  
  143.         Node t9 = new Node();
  144. //             t9.value = 0;
  145.              t9.value=8;
  146.              t9.depth=2;
  147.              t9.isTerminal= true;
  148.  
  149.         Node min3 = new Node();
  150.              min3.isMin=true;
  151.              min3.isTerminal=false;
  152.              min3.depth=1;
  153.              min3.children.add(t7);
  154.              min3.children.add(t8);
  155.              min3.children.add(t9);
  156.  
  157.          Node max1 = new Node();
  158.               max1.isMax=true;
  159.               max1.isTerminal=false;
  160.               max1.depth=0;
  161.               max1.children.add(min1);
  162.               max1.children.add(min2);
  163.               max1.children.add(min3);
  164.  
  165.  
  166.  
  167.               alphaBetaSearch (max1);
  168.  
  169.  
  170.  
  171.     }
  172. }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
visited leaf with value 3
visited leaf with value 2
visited leaf with value 3
visited leaf with value 9
visited leaf with value 14
14
https://ideone.com/s6uKYL
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!